[알고리즘 문제 풀이][파이썬] 백준 1874번: 스택 수열

백준 1874 문제 링크: https://www.acmicpc.net/problem/1874

📑 문제 설명

이번 문제는 이해하기 어려웠다...😥
우선 stack을 사용하여 수열대로 pop, 그렇게 할 수 없다면 "NO"를 출력하는 프로그램 작성이다.
예를 들어, 8개의 숫자로 구성된 수열을 확인하고 싶다면!
8 # 원하는 숫자의 개수
4 # 여기부터
3
6
8
7
5
2
1 # 마지막까지 수열
즉, 8개의 숫자를 사용하여 4,3,6,8,7,5,2,1 순서대로 POP을 할 수 있는가(있으면 +/-로 표시), 없는가(NO)를 판단하는 문제이다.
오름차순으로 PUSH를 해야하기 때문에
[1][2][3][4]
[+][+][+][+]
여기까지 push(+)를 하고 수열 맨 첫번째 4 를 마주쳤기 때문에 pop을 진행한다.
[1][2][3][+][+][+][+][-]
pop을 한 후 다시 수열을 확인하고 두번째 3 을 마주쳤기 때문에 pop을 진행한다.
[1][2]
[+][+][+][+][-][-]
위에 과정을 반복한다.

입력: 원하는 수열의 개수, 수열
출력: 오름차순을 유지하여 stack에 push, pop 이 가능하다면 +,- 조합 출력 / 오름차순을 유지할 수 없다면 "NO" 출력

💡 문제 해결 방법

• 내가 많이 헤맸던 포인트
  - 반복문 종결 조건
  - 인덱스 설정 방법
  위에 두 가지를 먼저 설정한다면 코드 짜는 시간이 배로 단축될 것 같다.

1. 변수 설정

• seq_list: 순열
• pp_list: push/pop 을 의미하는 +/-를 저장할 리스트
• n: 순열 개수
• cnt: seq_list index
• i: stack에 입력되는 n까지의 수

2. 종결 조건
   순열 모든 원소 하나하나를 보기 전까지 반복

3. 예외 처리

• stack에 아무것도 없을 때 => 무조건 push
• stack에 1개 이상 있을 때
  • stack 마지막 원소가 순열 순서에 다가왔다면 => pop
    • i가 이미 n보다 크다면 "NO"와 함께 함수 종료
    • I가 아직 n보다 작다면 push
  • stack 마지막 원소가 순열 순서와 다르다면 => push

💻 코드

def check_sequence(n,num_list):
    seq_list = list()
    pp_list = list()
    for i in range(n):
        seq_list.append(i)

    temp_stack = list()
    cnt = 0
    i = 1
    while (cnt < n):
        if (len(temp_stack) == 0):
            temp_stack.append(i)
            pp_list.append("+")
            # print('+')
            i = i + 1
        else:
            if (temp_stack[-1] != num_list[cnt]):
                if (i>n):
                    pp_list.append("NO")
                    break
                else:
                    temp_stack.append(i)
                    pp_list.append("+")
                    # print('+')
                    i = i + 1
            else:
                temp_stack.pop()
                pp_list.append("-")
                # print('-')
                cnt = cnt + 1


    return pp_list




if __name__ == '__main__':
    n = int(input())
    num_list = list()
    for i in range (n):
        num = int(input())
        num_list.append(num)
    check = check_sequence(n, num_list)
    if(check[-1] == "NO"):
        print("NO")
    else:
        for i in range(len(check)):
            print(check[i])

💟 추가적으로 알게 된 점

• 설계의 중요성: 무조건 들이박기보다는 입력과 출력, 예외 처리, 종결 조건 정리하기