[ 백준 1874] ( python ) 스택 수열

 

📚 스택 수열

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

82817

30106

21281

35.983%

문제

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

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

입력

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

출력

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

예제 입력 1

8
4
3
6
8
7
5
2
1

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

 

예제 입력 2 

5
1
2
5
3
4

예제 출력 2 

NO

 

 

 

 

✍ 접근

1~8까지의 수를 하나씩 세면서 원하는 수열을 만들어내기 위해

처음 for문으로 원하는 수열의 값을 하나씩 x로 가져오고,

그 안에서 다른 for문을 돌려서

1~8까지의 수가 들어있는 배열을 하나씩 세면서 x와 수를 비교하여

비교한 정보에 따라 stack에 수를 넣고, 빼고

res에 +, - 를 하나씩 넣고 빼며 결과를 출력하려 했지만

 

1. for문을 한번에 두번 다 brake할 수 없다

2. for 안에 다른 for문을 집어넣었기 때문에 원하는 수에서부터 시작할 수 없고 항상 1에서부터(설정해둔 숫자로부터 시작해야 한다)

=> 2번은 pointer이라는 새로운 값을 변동시키는 방법으로 해결할 수 있었지만 이보다 더 효율적인 방법을 찾고 싶었다.

 

 

 

정답 코드

n = int(input())
stack=[] 
res=''
cur = 1 
for _ in range(n):
    x = int(input())
    while cur < x :
        stack.append(cur)
        cur+=1
        res+='+'
    if cur == x :
        res+='+-'
        cur+=1
    elif cur > x:
        if stack.pop() == x:
            res+='-'
        else:
            print('NO')
            cur = 0
            break
if cur != 0:
    print(*res, sep="\n")

그렇게 해서 찾은 방법

for문을 두번 돌리지 않고

cur이라는 숫자를 if문에 따라 하나씩 추가해가면서 n까지의 숫자를 세고

이 숫자의 변동 값과 x값을 비교하였다.

 

 

 

 

⭐ 배움

• 문제가 있을 때 간단하게 for문을 돌리는 것으로 해결하려 하지 말자
• 문제를 '어떻게 풀지'부터 생각하지 말고 문제 자체를 들여다보자
  => 1~n까지의 숫자를 도는 것이 본질이 아니라 어찌되었든 숫자를 증가시키면서 확인하면 되는 문제였다.
• print(*res, sep="\n") 방법으로 한 줄에 하나씩 간단하게 출력할 수 있다