백준 1874

문제

https://www.acmicpc.net/problem/1874

코드

문제를 이해하는 데 시간이 조금 걸렸다.
내가 이해한 바로는,
사용자 입력 n에 대해 1부터 n까지의 정수가 stack에 저장될 수 있는 숫자이다. (중복 X)

그리고 사용자 입력 수열을,
1부터 n까지의 정수와 stack의 operation인 push, pop으로 만들 수 있는가를 물어보는 문제이다.

예를 들어,
n = 5이고, 사용자 입력 수열이 [1, 2, 5, 3, 4]라고 하자.

그러면 우리가 쓸 수 있는 숫자는 1, 2, 3, 4, 5 이다.

처음에 stack = []이므로, 1을 push 해야 한다.
stack = [1]에서는 1을 pop 해야 한다.
그리고 다음 element인 2를 위해서는 숫자 2를 push 해야 한다.
stack = [2]에서는 2를 pop 해야 한다.
다음 element는 5이기 때문에 숫자 3, 4, 5를 push 해야 한다.
stack = [3, 4, 5]에서 5를 pop 하자.
stack = [3, 4]인데, 다음 element는 3이다.
stack은 LIFO 구조이기 때문에 3이 4보다 먼저 나올 수 없다.
따라서 [1, 2, 5, 3, 4]라는 수열은 만들 수 없다.

처음 푼 코드는 다음과 같다.

import sys

n = int(sys.stdin.readline())

sequences = []
stack = [0]
operations = []
used_nums = []

for i in range(n):
    sequences.append(int(sys.stdin.readline()))
    
# print(sequences)

for i in range(1, sequences[0] + 1):
    stack.append(i)
    operations.append("+")

for sequence in sequences:
    if sequence == stack[-1]:
        used_nums.append(stack.pop())
        operations.append("-")
    elif sequence > stack[-1]:
        for i in range(stack[-1] + 1, sequence + 1):
            if i not in used_nums:
                stack.append(i)
                operations.append("+")
                        
        used_nums.append(stack.pop())
        operations.append("-")
    elif sequence < stack[-1]:
        print("NO")
        break
    
#    print("sequences:   ", sequences)
#    print("operations:  ", operations)
#    print("stack:       ", stack)
#    print("used_nums:   ", used_nums)
#    print("---------------")
else:
    for operation in operations:
        print(operation)

나름 많이 고민해서 풀었는데, 시간초과가 떴다.
찾아보니 시간초과는 시간 초과가 뜨기 전까지는 정답이지만 이것이 모든 케이스에 대한 정답인지는 알 수 없는 것 같다.

어쨌든 위의 코드를 수정하면서 느낀 점은,
1) 파이썬에서 들여쓰기(indentation)는 매우 중요하다.
2) 디버깅 할 때, print() 함수를 이용해서 중간 중간 결과를 확인하는 것은 좋은 방법이다.

이후 다른 사람의 풀이를 2개 정도 찾아봤고,
아래와 같이 코드를 다시 짰다.

import sys

n = int(sys.stdin.readline())

count = 0
stack = []
operations = []

for _ in range(n):
    sequence = int(sys.stdin.readline())
    
    while sequence > count:
        count += 1
        stack.append(count)
        operations.append("+")
        
    if sequence == stack[-1]:
        stack.pop()
        operations.append("-")
    else:
        print("NO")
        break
else:
    print("\n".join(operations))

수정된 코드를 짜면서 느낀 점은..
문제를 복잡하게 생각하지 말고, 일차적으로는 단순하게 접근할 필요가 있다는 점..?

처음 코드에서는 stack에 정수를 넣을 때 그 정수가 pop() 된 정수인지 확인하기 위해 used_nums라는 리스트를 추가로 할당했는데,
여기서는 count라는 변수로 해결할 수 있었다.

즉, 어차피 1부터 n까지의 정수는 stack에 순차적으로 들어간다.
이미 stack에 들어간 정수가 pop() 되었는지는 상관 없이 우리는 그냥 count 이후부터 sequence까지의 정수를 다시 stack에 append() 해주면 되는 것이다.

그리고 sequence == stack[-1]이 아니라면, 무조건 NO를 출력하는데,
아직 stack에 어떤 숫자가 남아있다는 것은 수열에서 아직 나오지 않았다는 의미이고, 수열이 끝나기 전에는 반드시 나올 숫자이기 때문에 다른 숫자를 위해 pop()을 하면 안 된다.
그런데 현재 sequence가 stack[-1]이 아니라면 결국 stack[-1]을 pop()하고 그 앞의 숫자로 가서 다시 pop()을 한다는 의미가 되기 때문에, sequence == stack[-1]이 아니라면 무조건 수열을 만들 수 없는 경우라고 할 수 있다.

기타

그래도 고민하면서 푸니까 재밌는 것 같다.