TIL 32 | 스택 수열 (백준 1874 python)

문제 바로가기

코데풀님 영상의 도움을 받았다.
BOJ 1874번 스택 수열 - 유튜브 영상

문제파악

입력 값 중 첫번째 값(n)을 제외한 나머지 숫자로 구성된 수열을 1부터 n까지 오름차순으로 주어지는 정수들을 이용하여 완성해야 한다. 이 수들을 처음 주어진 수열의 모습으로 만들기 위해 push, pop이 실행되는 순서를 +, -로 표현해야 한다.

접근방식

1부터 n까지 오름차순으로 주어지는 수를 스택에 저장하다가 수열 값과 일치하는 숫자가 나오면 pop한다.

• 1부터 n까지 주어지는 수는 같은 값이 중복해서 나오지 않는다.
• 주어지는 수로 만들 수 없는 수열인 경우에 No를 출력한다.

전체코드

def stack_sequence(n,sequence):
    stack = []
    num = 1
    sequence_idx = 0
    result = []

    while True:
        if len(stack)==0:
            stack.append(num)
            result.append(+)
            num += 1
        
        elif sequence[sequence_idx] == stack[-1]:
            stack.pop()
            result.append('-')
            sequence_idx +=1 #기존 idx의 수열이 충족됐기때문에 다음 idx로 넘어간다.
            if sequence_idx == n: # n = 수열을 구성하는 수의 개수
                break
        else:
            if n < num: #주어진 수열을 만들 수 없는 경우이다. (수열은 1~n 사이 수로 구성)
                print("NO")
                break
            stack.append(num)
            result.append('+')
            num +=1
    if len(stack) == 0:
        for char in result:
            print(char)

sequence = list()
n = int(input())
for _ in range(n):
    sequence.append(int(input()))
stack_sequence(n, sequence)

코드풀이

1. 스택에 저장된 수가 없어 길이가 0인 경우 .append를 이용하여 num을 저장한다. 문제에서 말하는 push에 해당하므로 result에 '+'를 저장한다. 주어진 수가 저장되었으므로 num+=1을 하여 다음 숫자가 오도록한다.
2. sequence[sequence_idx]는 입력받은 수열안에 있는 수를 의미한다. 이 값이 스택에 가장 최근에 저장된 수를 의미하는 stack[-1]과 일치한다면 이 값을 .pop()해오고 result에는 '-'를 추가한다. 수열 안에 있는 수 중 같은 수를 이미 찾은 것이므로 sequence_idx +=1을 해줌으로써 수열 안에서도 다음 순서에 있는 수와 비교할 수 있게 한다. 만약 이 인덱스 값이 수열을 구성하는 수의 개수인 n과 일치한다면 수열 내에 있는 수를 모두 비교했다는 것이므로 loop를 종료시킨다.
3. 주어지는 수들로 수열을 만들 수 없는 경우이다. 수열을 구성하는 수는 1부터 n까지의 수이다. num이 n을 초과할 때까지 수열이 완성되지 않았다면 성립이 불가능한 수열이라는 것이므로 'NO'를 출력하고 loop를 종료한다. 그렇지 않다면 계속해서 num을 스택에 저장하고 result에는 '+'를 기록해준다.

반복문에서 나왔을 때 스택에 남아있는 수가 없다면 수열이 만들어진 것이므로 result에 저장된 +와 -를 for문으로 한 줄씩 출력한다.