[알고리즘] 백준 1847번 python

bluejoy·2022년 1월 13일

알고리즘

목록 보기

3/4

쓰게 된 계기

계절학기를 하고 왔더니 알고리즘이 하나도 기억이 안난다. 자신감을 찾기 위해 쉬워 보이는 문제를 골라서 풀어보려했는데... 너무 어려웠다. 스스로 반성할 겸 과정을 천천히 적어보려 한다.

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

문제 요약

문제 조건은 매우 단순했다. 1부터 n까지의 수가 차례대로 스택에 push된다. 그 사이에 pop을 끼워넣어서 입력 수열을 어떻게 만드나이다.

첫 풀이

코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
goal = deque([0] * n)
for i in range(n):
    goal[i] = int(input())

stk =[0] # 조건의 스택. 아무것도 없을때의 오류를 막기 위해 0을 넣어뒀다.
cur_num = 1 # 현재 숫자
cur_match = goal.popleft() # 현재 일치 목표
result = []

while cur_num < n + 1 and stk: 
    stk.append(cur_num)
    result.append('+')
    if stk[-1] == cur_match:
        while stk[-1] == cur_match:
            try:
                cur_match = goal.popleft()
            except:
                pass
            stk.pop()
            result.append('-')
        cur_num += 1
        continue
    if stk[-1] > cur_match:
        break
    cur_num += 1

if len(result) < 2 * n - 1:
    print('NO')
else:
    print('\n'.join(result))

설명

처음에는 그냥 조건을 생각나는대로 구현하려고 했다.

수를 하나 스택에 담는다.
스택의 최상단 값과 현재 pop되야 하는 값의 일치 여부를 판별한다.
일치할 경우 pop하고 2번 반복
만약 현재 스택 최상단의 값이 목표 값보다 크다면 목표 수열을 만들 수 없으므로 break
답이 맞다면 result의 길이는 n*2여야 한다. (pop연산의 수와 push 연산의 수가 동일해야 하므로)

그런데 코드가 너무 더러운거임~

개선사항

목표 배열 goal은 현재 목표하는 값만이 영향을 미치므로 매번 입력 받고 찾아도 된다. 이 값을 cur_match_goal이라고 하자.
cur_match_goal은 stk의 최상단에 존재해야한다. 존재하지 않는다면 cur_num을 1씩 증가해가며 존재할 때까지 push해야한다.
stk에 들어가는 값이 cur_match_goal보다 커졌다면 더 이상 조건을 만족할 수 없으므로 그만 찾는다.

개선된 풀이

코드

import sys
input = sys.stdin.readline
n = int(input())
stk =[0]
cur_num = 1
result = []
for i in range(n):
    cur_match_goal = int(input()) # 현재 목표

    while stk[-1] < cur_match_goal:
        stk.append(cur_num)
        result.append('+')
        cur_num += 1

    if stk[-1] > cur_match_goal:
        break
    stk.pop()
    result.append('-')

if len(result) < 2 * n - 1:
    print('NO')
else:
    print('\n'.join(result))