숫자로 이루어진 스택이 주어졌을 때, 스택 안의 값들이 쌍(pair) 단위로 연속되어 있는지 확인해야 하는 문제를 생각해 봅시다. 여기서 각 쌍은 값이 증가하거나 감소하는 형태 모두 가능합니다. 만약 스택에 홀수 개의 값이 들어 있다면, 맨 위(top)에 있는 요소는 쌍을 이루지 못하므로 검사 대상에서 제외됩니다. 또한 중요한 조건은, 검사가 끝난 후에도 원래 스택의 내용을 그대로 유지해야 한다는 점입니다.
이 문제는 스택의 기본 연산인 push, pop, 그리고 스택이 비어 있는지 확인하는 연산만을 사용하여 해결할 수 있습니다.
예를 들어 입력이 stk = [5, 6, -4, -5, 12, 11, 6, 7, 22]라고 해 보겠습니다. 맨 위 요소인 22를 제외하면 나머지 값들은 쌍으로 묶여 [(5, 6), (-4, -5), (12, 11), (6, 7)]이 되며, 모든 쌍이 서로 1씩 차이 나므로 결과는 True입니다.
문제 해결 접근 방식
- 임시 스택(temp)을 준비하고, 원본 스택(stk)에서 요소를 하나씩 pop하여 temp에 push합니다.
- 원본 스택 stk를 비웁니다.
- 결괏값을 저장할 flag를 True로 초기화합니다.
- temp의 크기가 1보다 클 동안 다음을 반복합니다.
- temp의 위쪽 두 요소를 꺼내 item_first와 item_second에 저장합니다.
- 두 요소 차이의 절댓값이 1이 아니라면 flag를 False로 설정합니다.
- 꺼낸 두 요소를 다시 원본 스택 stk에 push하여 원래 순서를 복원합니다.
- 반복이 끝난 후 temp에 요소가 하나 남아 있다면(홀수 개였던 경우), 그 요소를 stk에 push합니다.
- flag 값을 반환합니다.
예제 코드
def solve(stk):
temp = stk[::-1]
stk.clear()
flag = True
while len(temp) > 1:
item_first = temp[-1]
temp.pop()
item_second = temp[-1]
temp.pop()
if abs(item_first - item_second) != 1:
flag = False
stk.append(item_first)
stk.append(item_second)
if len(temp) == 1:
stk.append(temp[-1])
return flag
stk = [5, 6, -4, -5, 12, 11, 6, 7, 22]
print(solve(stk))입력
[5, 6, -4, -5, 12, 11, 6, 7, 22]
출력
True
이 알고리즘은 스택의 모든 요소를 한 번씩 처리하므로 시간 복잡도는 O(n)이며, 임시 스택을 사용하기 때문에 공간 복잡도 역시 O(n)입니다. 검사 과정에서 요소들을 원본 스택으로 되돌려 놓기 때문에 함수 호출이 끝난 뒤에도 원래 스택 상태가 그대로 보존된다는 점이 특징입니다.