[BJ1874] 스택 수열

백준 알고리즘

🚩 문제 설명

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

1874번: 스택 수열

BJ1874

◾ 백준 1874번 스택수열

◾ 스택 기초 문제

◾ 임의의 수열이 주어졌을 때, 스택을 사용해서 해당 수열을 만들 수 있는지 아닌지 확인하고

◾ 만약 만들 수 있다면 어떤 순서로 push, pop을 해야하는지 계산하는 문제

즉, 1 ~ N 까지의 수를 해당 수열의 형태로 push, pop 할 수 있는지를 묻는 문제
1 ~ N 까지의 수는 오름차순으로 넣어야하는 것을 유의

◾ 흠 문제가 처음에는 잘 이해가 되지 않았음 😪

◾ 그러니까 아래와 같음

n까지의 수	만들어야하는 스택수열
1 2 3 4 5 6 7 8	4 3 6 8 7 5 2 1

n	stack	ans
1 2 3 4		+ + + +
1 2 3	4	+ + + + -
1 2	4 3	+ + + + - -
1 2 5	4 3	+ + + + - - +
1 2 5 6	4 3	+ + + + - - + +
1 2 5	4 3 6	+ + + + - - + + -
1 2 5 7	4 3 6	+ + + + - - + + - +
1 2 5 7 8	4 3 6	+ + + + - - + + - + +
1 2 5 7	4 3 6 8	+ + + + - - + + - + + -
	4 3 6 8 7 5 2 1	+ + + + - - + + - + + - - - - -

 

 

---

 

 

✅ 입출력

✔️ 예제 1

8
4
3
6
8
7
5
2
1

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

✔️ 예제 2

5
1
2
5
3
4

NO

 

 

---

 

 

📑 문제 풀이

with Python (파이썬)

ans = ''  # 결과값 저장
n = int(input())  # 요소 갯수
inputs = [int(input()) for _ in range(n)]  # 입력 수열 저장 배열
stack = []  # 1부터 오름차순으로 숫자가 들어갈 배열
flag = True

cnt = 0  # 오름차순으로 들어가는 숫자
for i in inputs:
    while cnt < i:
        cnt += 1
        stack.append(cnt)
        ans += '+'

    if stack[-1] == i:
        stack.pop()
        ans += '-'
    else:
        flag = False
        break

if flag == False:
    print("NO")
else:
    print("\n".join(ans))

💬 Point

➡️  stack 사용
➡️  stack[-1] == i
➡️  join() 문자열 함수
➡️  flag 사용

◾ 우선 input() 함수를 이용해서 inputs 배열을 받는다.

• inputs 배열은 입력된 정수를 저장하는 배열이다.
• N의 갯수만큼 입력이 되므로 for문을 사용해서 배열을 입력받았다.

◾ 그리고 inputs 배열을 돈다.

◾ cnt를 이용해서 push 해야하는 숫자를 넣어준다.

• 만약 push 해야하는 숫자가 4 라면 + + + + 총 4번이 돌아야한다.
• cnt 보다 inputs의 요소가 작다면 while문을 돌게된다.
• cnt를 이용하여 stack에 숫자를 추가한다.
• cnt는 1씩 증가하므로 1부터 숫자가 들어간다.

◾ 만약 stack에 쌓인 숫자들 중에서 마지막 숫자가 inputs의 요소와 같다면 pop 한다.

◾ ans = NO인 경우

• 숫자를 pop 해서 꺼내야하는데 꺼낼 수 없는 경우
• 예를 들면, 3 4 5가 stack에 쌓여진 상태인데 5가 있는데도 4를 꺼내야하는 상황이다.
• 이는 stack의 마지막 숫자와 inputs의 요소와 같지 않는 경우다.
• flag를 False로 만들어준다.

◾ ans를 출력해준다.

• ans는 한개씩 출력해야하므로 이를 유의하자.
• join 함수는 "문자열".join(리스트) 의 형식으로 쓸 수 있다.
• 문자열을 기준으로 리스트의 요소들을 붙일 수 있다.

 

 

 

 

 

 

 

 

 

---