[백준] 1874번: 스택 수열

1. 백준 1874번 스택 수열

[백준] 1874번: 스택 수열

 

2. 오늘의 회고

 

0. 문제 분석

 

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

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

 

: 문제를 통해 스택 자료구조에 대한 개념을 한번 더 익힐 수 있는 좋은 문제이다. 문제에 나와있듯이 스택은 자료를 넣은 입구와 자료를 뽑는 입구가 같은 자료구조로, 택배 상하차 박스 쌓기에 빗대어 말한다. 보통 최근 값만 확인해야 하는 알고리즘 문제를 풀 때 사용한다.

 

1. 입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

: 같은 숫자가 나오는 일은 없다는 것을 캐치하고 간다.

 

2. 출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

: 입력된 수열을 만드는 과정을 + 와 - 로 표현해야 한다.

 

3. 문제 접근

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

 

문제를 이해하는 과정이 필요하다. 1부터 n까지 수를 오름차순으로 push 할 수 있고, pop은 상관없다.

 

예를 들어 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]를 얻을 수 있다.

while 반복문을 활용하여 1부터 빈 배열에 push를 하고 그 값(= 배열의 마지막 원소)을 입력받은 수열의 첫 원소 4와 비교한다. 원소가 같을 시, 또 다른 빈 배열에 추가하고 pop 한다. 아닐 시 +1 하여 push 한다.

 

얕은 복사 깊은 복사

얕은 복사: 원본객체의 최상위 레벨만 복사한다. 원본 객체의 하위 객체만 복사되므로, 복사본의 하위 객체를 수정하면 원본 객체에도 영향을 미친다. 예를 들어 아래는 nlist의 얕은 복사를 통해 rlist를 생성했다. nlist는 중첩된 리스트가 아니기 때문에 rlist가 nlist의 최상위 요소들을 그대로 복사하니 얕은 복사를 해도 문제는 되지 않는다.

rlist = nlist[:]

 

얕은 복사: 원본 리스트의 모든 하위 객체까지 완전히 새로운 객체로 복사된다. 모든 하위 요소를 재귀적으로 복사하는 방법이다. 중첩된 리스트나 객체가 포함된 경우에는 깊은 복사를 사용해야 한다.

import copy

nlist = [[1, 2], [3, 4]]
rlist = copy.deepcopy(nlist)

 

while 종료조건 설정

반복문이 무한 루프에 빠지지 않도록 종료조건을 잘 설정해줘야 한다.

 

정답코드

n = int(input())
nlist = []
alist = []
blist = []
cnt = 0
result = []
for i in range(n):
    a = int(input())
    nlist.append(a)

rlist = nlist[:] # 얕은 복사를 하지않으면 원본리스트가 변할때 복사본도 함께 변하게 된다
while cnt < n: # 루프를 강제 종료하는 조건을 잘 설정! 반복문이 무한 루프에 빠지지 않게 관리하는 조건
    if alist and alist[-1] == nlist[0]:
        alist.pop()
        blist.append(nlist[0])
        nlist.pop(0)
        result.append("-")
    else:
        cnt = cnt+1
        alist.append(cnt)
        result.append("+")

while alist: # 자료가 남아있을때까지 처리하는 패턴 while 리스트:
    blist.append(alist.pop())
    result.append("-")

if rlist == blist:
    print(*result, sep='\n')
else:
    print("NO")