백준 1874번: 스택 수열

본 문제는 백준에서 제공된 문제입니다.

1874번: 스택 수열

반복해서 말하지만 항상 문제를 풀기 전에 생각해야 하는 것은 이 문제에서 결국 어떤 것을 구해야 하는지, 그것을 구하기 위해선 어떤 방식을 택해야 하는지 이다. 일단 이 문제에서 원하는 것은 '스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지'이다. 즉, 만들 수 있으면 push와 pop 연산 반환, 없다면 없다고 반환하는 것이다. 그럼 이 문제는 어떤 방식으로 풀어야 할까? 이번엔 제목에 나와있는 대로 그냥 스택을 사용하면 된다고 판단이 될 것이다. 그럼 코드를 들어가기 전, 중요하게 생각해야 될 부분은 어느 부분일까? 바로, '이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자'이다. 문제를 풀다보면 깨닫겠지만, 사실 이 부분이 해당 수열을 만들 수 없는지, 있는지에 대한 판단 기준이 된다. 이제 코드를 살펴보자.

---

n = int(input())
order = [] # 수열의 순서를 저장
stack = [] # 스택
result = [] # +,- 의 결과 순서를 저장

for i in range(n): # 입력부분
    order.append(int(input()))

num = 1 # stack에 오름차순으로 들어가기 위한 변수, 스택에 추가할 때마다 +1
for i in order: # 해당 수열의 순서대로 탐색
    if not stack: # stack이 비어있다면 뺄 수 있는 수가 없기에 
        stack.append(num) # 일단 추가해줌. 뺄 상황이 왔을 때 비교를 위해서
        num += 1 # stack에 값이 추가됐으므로 +1
        result.append('+') #push 기록
    while stack[-1] < i and num <= n: #해당 수열이 정해진 범위를 벗어나지 않으면서
                                      # 스택의 맨위 값이 비교대상보다 적을 동안    
        stack.append(num) # 비교 대상의 수에 만족하기 위해 더해줌
        num += 1 # 스택에 값을 추가했으므로 +1
        result.append('+') #push 기록
    if stack[-1] == i: # 스택의 맨 위 값과 비교대상이 같다면 
        stack.pop() # 빼냄. (조건에 만족한 상황)
        result.append('-') #pop 기록
    else: # elif stack[-1] > i: #(중요!) 그나머지 경우 => 즉 스택의 상단값이 비교대상보다 크다면
        result = [] #지금까지의 기록을 지우고
        break # 끝냄

if not result: # 기록된 값이 없다면 -> 불가능한 수열
    print('NO') # NO
else: # 기록된 값이 있다면 -> 가능한 수열
    for i in result: # 출력
        print(i)

초반에 말했 듯이 오름차순으로 저장된다라는 조건이 핵심이라는 것을 상기하면서 코드를 확인하면 된다. 중요한 부분에 대한 설명을 덧붙이자면, 스택이 비었을 때는 그 후에 비교를 위해서 일단 값을 추가해 준다. 그 후 해당 수열의 값과 같을 때까지 스택에 값을 더해주고 같아지면 빼준다. 이를 반복하는데, 가장 중요한 부분은 결국 스택의 최상단값이 탐색하고자 하는 수열의 값보다 커질 때이다. 스택은 오름차순으로 저장하기에 스택의 최상단 값이 내가 찾고자 하는 수열의 수보다 크다는 뜻은 결국 해당 수열을 찾기 위해서 수열보다 큰 값들을 pop 해줘야 된다는 뜻이다. 그렇게 pop 된 스택의 값들은 결국 나중에 그 값의 수열이 온다 해도 찾을 수가 없기 때문에 불가능한 수열이 된다.

---

이문제는 어떤 결과를 내야하는지, 그 결과를 내기 위해서 어떤 방식을 택해야 하는지에 대한 정보를 모두 제공한 문제이다. 그래서 어떻게 생각하면 쉬울 수 있지만, 결론적으로 그 세부적인 부분들을 직접 생각해 내야 된다는 점에서 어려운 문제라고 생각한다. '가능한 수열인지 아닌지에 대한 판단 기준을 어떻게 세우느냐'가 결국 이 문제를 풀 수 있냐 없냐의 판단 기준이라 생각한다.