[BAEKJOON] 1874 | 스택 수열

🔎 1874 | 스택 수열

https://www.acmicpc.net/problem/1874

---

💡 Solution

✍🏻

Logic

1. 해당 수열을 만들기 위해서는 먼저 목표로하는 수열의 수까지 스택에 수를 넣어준다.

2. 이후, 스택의 top 원소가 목표로 하는 수와 같으면 pop 해준다.

3. 위의 과정을 반복하며, 만약 1번 과정을 마친 후 2번 과정의 조건이 충족이 안되면 수열을 만들 수 없다.

import sys
input =  sys.stdin.readline

n = int(input())
num_list = [int(input()) for _ in range(n)]

def findNumList(n, num_list) :
    stack = []
    result = []
    
    i = 0
    m = 1
    for i in range(n) :
        num = num_list[i]
        
        while m <= num :
            stack.append(m)
            result.append('+')
            m += 1
        
        if stack[-1] == num :
            stack.pop()
            result.append('-')
        else :
            return 0
            
    return result
    
result = findNumList(n, num_list)

if result :
    for d in result :
        print(d)
else :
    print('NO')

---

import sys
input =  sys.stdin.readline

n = int(input())
num_list = [int(input()) for _ in range(n)]

def findNumList(num_list) :
    stack = []
    result = []
    
    i = 0
    m = 1
    max_num = max(num_list)
    while m <= max_num : 
        if m <= num_list[i] :
            stack.append(m)
            result.append('+')
            m += 1
            
        while stack and stack[-1] == num_list[i]:
            stack.pop()
            result.append('-')
            i += 1
            if i >= len(num_list):  # 리스트 끝까지 도달하면 중단
                break
    
    if len(stack) == 0:
        return result
    else:
        return 0
        
result = findNumList(num_list)

if result :
    for d in result :
        print(d)
else :
    print('NO')

▶ 📌 Note

∙ 시간초과 문제로 많이 애쓴 문제

1. 수열을 찾지 못하는 경우의 else 처리를 잘못해서 무한루프를 돌게 됨.

2. 예를 들어 5,3 수열이라면 이미 '5'에서 m은 5까지 간 후 5를 pop 했기 때문에 stack의 top은 4, m은 5이기에 두번째 수인 3보다는 크므로 계속해서 조건이 번갈아가며 체크되지만 break를 할 수 없음.

📍참고 : https://www.acmicpc.net/board/view/152451