[boj] 1874 - 스택 수열

문제

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

풀이

스택을 이용하여 수열을 완성해야 하는 문제이다. 기본적인 스택 사용법을 아는지에 대해 묻는 문제로, 약간의 생각을 필요로 하는 문제였다.

해당 문제에서의 핵심은 문제의 이해이다. 필자도 처음에는 문제 자체를 이해하는데 약간의 시간이 걸렸는데, 이후 스택을 어떤 식으로 사용하라는 말인지 이해한 후에는 쉽게 문제를 풀 수 있었다.

필자는 isstackable이라는 함수를 이용하여 문제를 풀이하였는데, 그 이유는 결과값이 불가능한 경우, NO를, 가능한 경우 어떤 연산을 진행했는지 순서대로 출력해야 하기 때문에, 함수 내부에서 리턴 값을 이용하여 불가능한 경우에는 "NO"라는 원소 하나를 가진 리스트로, 가능한 경우에는 연산 리스트를 리턴하도록 했다. 그리고 해당 값을 이터레이터를 이용하여 순차적으로 출력하는 과정을 통해 출력을 용이하게 할 수 있도록 풀이하였다.

함수의 내부 동작 원리는 우선 기본 숫자 배열을 만든다. 이후 두 개의 인덱스를 이용하여 하나는 기본 숫자 배열을 가리키고, 하나는 입력값 숫자 배열을 가리키도록 이용하여 스택의 가장 위 값과 입력값 숫자 배열의 인덱스 위치의 원소가 일치하지 않을 경우 기본 숫자 배열의 값을 스택에 넣고 다음 인덱스로 넘어가는 식으로 구성하였으며, 스택이 비어 있는 경우에는 무조건 스택에 원소를 넣도록 구현하였다.

이후 과도한 오버헤드를 방지하기 위해 기본 숫자 배열의 마지막 원소까지 1차적으로 확인이 끝났으면 이제 남은 원소는 모두 스택 안에 존재하는 것이기 때문에 스택의 모든 값을 빼내고, 새롭게 만들어진 배열과 처음에 입력받은 배열이 서로 같은지 확인을 통해 스택을 통해 해당 배열을 만드는 것이 가능한지 확인하고, 결과값에 따라 리턴하였다.

해당 문제는 디버그 과정에서 약간 시간을 썼는데, 처음에는 마지막 스택을 완전히 마무리하는 과정에서 연산자 리스트에 pop했다는 내용을 넣어주지 않아서 틀린 결과가 나왔었다. 결국 디버깅이 알고리즘 연습의 시간을 좌우한다는 생각이 들었으며, 하나하나 차근차근히 디버깅하는 습관을 가지면 어떤 문제든 해결할 수 있을 것이라고 믿는다.

코드

import sys

N = int(input())

final_data = [int(sys.stdin.readline()) for i in range(N)]


def isstackable(final_data):
    data = [i for i in range(1, N + 1)]
    op_list = []
    stack = []
    my_data = []
    idx = 0
    idx2 = 0
    while idx2 < len(data):
        if len(stack) == 0:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
            continue
        if stack[-1] != final_data[idx]:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
        else:
            idx += 1
            my_data.append(stack.pop(-1))
            op_list.append("-")
    for i in stack[::-1]:
        my_data.append(i)
        op_list.append("-")
    if my_data == final_data:
        return op_list
    else:
        return ["NO"]


ans = isstackable(final_data)
for i in ans:
    print(i)