[BOJ] 1874번 스택 수열 / 사용언어 : 파이썬(python)

※ 문제링크 

1874번: 스택 수열

※ 기본문제

[BOJ] 10828번 스택 / 사용언어 : 파이썬(python)

※ 문제풀이

import sys
input = sys.stdin.readline
N = int(input())
check_list = []
for _ in  range(N):
    check_list.append(int(input()))
number_list, res_list = [], [] 
# 숫자를 담을 리스트 생성, push와 pop 실행 내용을 담을 리스트 생성
i = 0
number = 1
while i < N: # pop명령실행횟수가 N과 같아지면 반복문을 종료
    if len(number_list) < 1: # 스택을 쌓을 리스트가 비어있으면 스택명령 실행
        number_list.append(number)
        number += 1
        res_list.append('+')
    if number_list[-1] == check_list[i]:
        number_list.pop()
        res_list.append('-')
        i += 1 # pop명령 실행횟수를 기록 - pop명령실행횟수가 N과 같아지면 반복문을 종료
    else: # 숫자의 크기가 
        if number <= N:
            number_list.append(number)
            number += 1
            res_list.append('+')
        elif number == N + 1: 
            # 값을 끝까지 담고 조건에 맞지않아서 pop을 실행하지 못하면 'NO'저장 및 반복문 종료
            res_list = ['NO']
            break
for i in range(len(res_list)):
    if i == len(res_list) - 1:
        sys.stdout.write(f'{res_list[i]}')
    else:
        sys.stdout.write(f'{res_list[i]}\n')

 

해당 문제는 스택을 활용하여 풀어야 하는 문제였다. 처음 문제를 읽었을 때 정확히 이해가 안가서 애를 먹었는데, 간단하게 문제에 대해서 설명하면 아래와 같다. 해당 문제를 이해하려면 pop함수에 대한 기본적인 이해가 필요하다.

(pop함수 : 리스트의 마지막 변수 값을 출력하고 그 값을 리스트에서 제거)

예시 : push를 3번 하게 되면 리스트는 [1, 2, 3]이 된다.

이 상태에서 pop을 1번하게 되면 리스트의 마지막 변수인 3은 리스트에서 제거되고, 3을 출력해준다. 즉,  1~3까지의 숫자를 3 2 1로 출력하려면 push push push pop pop pop이라는 명령이 필요한 것이다. 해당 개념을 기반으로 문제를 해결한 과정은 아래와 같다.

1. 입력받은 숫자를 빈 리스트에 저장(check_list) / 1부터 N까지의 숫자로 이루어진 리스트 생성(number_list)

2. 1부터 N까지의 숫자를 차례대로 number_list에 쌓으면서 check_list와 비교를 통해 조건 만족시 pop 실행

3. pop을 실행할때마다 명령실행횟수를 기록하여 N과 명령실행횟수가 동일해지면 반복문 종료 후 결과 출력

+ N까지 numer_list전부 쌓았는데 명령이 무한루프에 빠지면 결과값으로 NO를 부여하고 반복문 종료

추가적으로 print문을 반복해서 사용하게 되면 시간이 오래걸리기 때문에 sys함수를 사용하여 출력을 해주었다. sys함수를 쓸때에는 반드시 개행문자를 기록해야하고, 마지막 출력문에는 개행문자가 없어야 통과가 가능하기에 해당 조건을 반영하여 출력을 하게끔 하였다.

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.