문제 개요
숫자로 가득 찬 큐(queue)가 있다고 가정해 보겠습니다. 이때 큐에 있는 인접한 요소들이 쌍(pair) 단위로 연속적인지 확인해야 합니다. 즉, 두 요소씩 짝을 지었을 때 각 쌍의 차이가 정확히 1이 되어야 한다는 의미입니다.
예를 들어 입력이 que = [3, 4, 6, 7, 8, 9]라면, (3, 4), (6, 7), (8, 9)로 묶였을 때 각 쌍의 차이가 모두 1이므로 출력은 True가 됩니다.
해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 큐를 생성하고 주어진 리스트의 모든 요소를 큐에 삽입합니다.
- 임시 리스트
temp를 만들고, 큐가 빌 때까지 큐의 앞(front) 요소를temp로 옮깁니다. - 또 다른 임시 리스트
temp2를 만들고,temp가 빌 때까지 마지막 요소를 하나씩 옮겨 순서를 뒤집습니다. result를True로 초기화합니다.temp2의 크기가 1보다 큰 동안 다음을 반복합니다.temp2에서 마지막 두 요소x와y를 꺼냅니다.|x − y|가 1이 아니면result를False로 설정합니다.x와y를 다시 원래 큐q에 삽입합니다.
- 반복이 끝난 후
temp2에 요소가 하나 남아 있다면 그 요소를 큐에 다시 넣습니다. result를 반환합니다.
이 알고리즘의 핵심은 큐의 요소들을 두 번 뒤집어 원래 순서를 복원한 뒤, 앞에서부터 두 개씩 짝지어 검사한다는 점입니다. 검사가 끝난 요소들은 다시 큐에 넣어 원래 상태를 유지하므로, 함수 실행 후에도 큐의 내용이 보존됩니다.
구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
import queue
def solve(que):
q = queue.Queue()
for i in que:
q.put(i)
temp = []
while q.qsize() != 0:
temp.append(q.queue[0])
q.get()
temp2 = []
while len(temp) != 0:
temp2.append(temp[len(temp) - 1])
temp.pop()
result = bool(True)
while len(temp2) > 1:
x = temp2[len(temp2) - 1]
temp2.pop()
y = temp2[len(temp2) - 1]
temp2.pop()
if abs(x - y) != 1:
result = False
q.put(x)
q.put(y)
if len(temp2) == 1:
q.put(temp2[len(temp2) - 1])
return result
que = [3, 4, 6, 7, 8, 9]
print(solve(que))
입력
[3, 4, 6, 7, 8, 9]
출력
True
복잡도 분석
시간 복잡도: O(n) — 큐의 모든 요소를 상수 번 순회하므로 선형 시간이 걸립니다.
공간 복잡도: O(n) — 임시 리스트 두 개와 큐 저장 공간이 추가로 필요합니다.
마무리 팁
실무 환경에서는 큐를 직접 조작하기보다 리스트나 collections.deque를 활용해 인접 요소를 두 개씩 슬라이싱하며 차이를 비교하는 방식이 더 간단하고 직관적입니다. 하지만 위 코드처럼 "표준 큐 자료구조만 사용해야 한다"는 제약이 있는 문제(코딩 테스트, 자료구조 학습 등)에서는 이 접근 방식이 유용하게 활용될 수 있습니다.