[백준/Python] 1874 : 스택 수열

 

처음에 문제 설명만 읽고 바로 이해하기엔 조금 시간이 걸렸던 문제인데,

스택을 어떤 용도로, 몇 개를 생성하여 적절하게 활용하는 지가 중요했던 것 같다.

 

 

예시를 통해 이해하는 것이 가장 빠르므로, 첫 번째 예시로 설명해보겠다.

 

첫 번째 줄에는 이후 입력될 정수들의 수인 N이 입력되고 두 번째줄부터 숫자 입력이 시작된다.

 

4 // [1, 2, 3, 4]
3 // [1, 2, 3]
6 // [1, 2, 5, 6]
8 // [1, 2, 5, 7, 8]

 

스택에 push하는 순서는 오름차순이며, 처음에 4를 입력 받았으니 1부터 4까지 차례로 먼저 스택에 삽입한다.

stack : [1, 2, 3, 4]
operator : [+, +, +, +]

이후 입력된 수열 4을 만들수 있으므로 4를 출력하기 위해 pop(-)을 한다.

stack : [1, 2, 3]
operator : [+, +, +, +, -]

 

다음으로 3을 입력받았을 때 스택의 가장 위에 있는 것이 3으로 동일하므로 바로 pop(-)

stack : [1, 2]
operator : [+, +, +, +, -, -]

 

다음으로 6을 입력받으면 해당 수열을 만들기 위해 계속 이어서 5와 6을 스택에 push(+)한 뒤, 마침내 6을 출력하기 위해 pop(-)까지 해주면 다음과 같다.

stack : [1, 2, 5]
operator : [+, +, +, +, -, -, +, +, -]

 

그 다음에 8을 입력받았을 때도 마찬가지로 7과 8을 먼저 스택에 push(+), 그 뒤 8을 출력하기 위해 pop(-)

stack : [1, 2, 5, 7]
operator : [+, +, +, +, -, -, +, +, -, +, +, -]

 

위와 같은 과정을 마지막 입력값까지 이어준다.

 

마지막 과정까지 완료된 후 stack이 비어있다면 수열을 완성할 수 있는 것이므로 operator 리스트에 있는 값들을 차례로 출력하고, 만약 비어있지 않다면 수열 생성이 불가능한 경우이므로 NO를 출력해주면 된다.

 

 

 

<풀이 코드1>

cnt = 1
stack = [] # 1, 2, 3, 4, ... 오름차순 저장 
op = [] # 연산자(push/pop)

N = int(input())
for i in range(N):
    num = int(input())
    while cnt <= num:
        stack.append(cnt)
        op.append('+')
        cnt += 1
    if num == stack[-1]:
        stack.pop()
        op.append('-')

if stack != []:
    print("NO")
else:
    for i in op:
        print(i)

 

앞서 설명했던 원리를 코드로 그대로 구현한 것이다.

N을 입력받고 N번 만큼 숫자 num을 입력 받은 뒤, 앞서 생성한 stack 과 op 연산자 스택 두 개를 활용하여 push/pop 기능을 구현한다.

마지막에는 스택이 차있다면 NO, 비어있다면 for문으로 op 스택에 있는 연산자들을 차례로 출력한다.

 

 

<풀이 코드2>

cnt = 1
stack = [] # 1, 2, 3, 4, ... 오름차순 저장 
op = [] # 연산자(push/pop)

N = int(input())
for i in range(N):
    num = int(input())
    while cnt <= num:
        stack.append(cnt)
        op.append('+')
        cnt += 1
    if num == stack[-1]:
        stack.pop()
        op.append('-')
    else:
        print("NO")
        exit(0)

for i in op:
    print(i)

 

이 코드는 앞선 코드와 거의 동일한데, 시간 단축을 위해 NO를 출력하고 프로그램을 종료(exit)하는 부분을 첫 번째 for문 안에 집어넣어본 코드 (그런데 채점 결과를 보니 오히려 1번 코드보다 시간이 더 걸려있어서 이유는 잘 모르겠다..)