백준 1874 문제 링크: https://www.acmicpc.net/problem/1874
📑 문제 설명
이번 문제는 이해하기 어려웠다...😥
우선 stack을 사용하여 수열대로 pop, 그렇게 할 수 없다면 "NO"를 출력하는 프로그램 작성이다.
예를 들어, 8개의 숫자로 구성된 수열을 확인하고 싶다면!
8 # 원하는 숫자의 개수
4 # 여기부터
3
6
8
7
5
2
1 # 마지막까지 수열
즉, 8개의 숫자를 사용하여 4,3,6,8,7,5,2,1 순서대로 POP을 할 수 있는가(있으면 +/-로 표시), 없는가(NO)를 판단하는 문제이다.
오름차순으로 PUSH를 해야하기 때문에
[1][2][3][4]
[+][+][+][+]
여기까지 push(+)를 하고 수열 맨 첫번째 4 를 마주쳤기 때문에 pop을 진행한다.
[1][2][3][+][+][+][+][-]
pop을 한 후 다시 수열을 확인하고 두번째 3 을 마주쳤기 때문에 pop을 진행한다.
[1][2]
[+][+][+][+][-][-]
위에 과정을 반복한다.
입력: 원하는 수열의 개수, 수열
출력: 오름차순을 유지하여 stack에 push, pop 이 가능하다면 +,- 조합 출력 / 오름차순을 유지할 수 없다면 "NO" 출력
💡 문제 해결 방법
- 내가 많이 헤맸던 포인트
- 반복문 종결 조건
- 인덱스 설정 방법
위에 두 가지를 먼저 설정한다면 코드 짜는 시간이 배로 단축될 것 같다.
- 변수 설정
- seq_list: 순열
- pp_list: push/pop 을 의미하는 +/-를 저장할 리스트
- n: 순열 개수
- cnt: seq_list index
- i: stack에 입력되는 n까지의 수
-
종결 조건
순열 모든 원소 하나하나를 보기 전까지 반복 -
예외 처리
- stack에 아무것도 없을 때 => 무조건 push
- stack에 1개 이상 있을 때
- stack 마지막 원소가 순열 순서에 다가왔다면 => pop
- i가 이미 n보다 크다면 "NO"와 함께 함수 종료
- I가 아직 n보다 작다면 push
- stack 마지막 원소가 순열 순서와 다르다면 => push
- stack 마지막 원소가 순열 순서에 다가왔다면 => pop
💻 코드
def check_sequence(n,num_list):
seq_list = list()
pp_list = list()
for i in range(n):
seq_list.append(i)
temp_stack = list()
cnt = 0
i = 1
while (cnt < n):
if (len(temp_stack) == 0):
temp_stack.append(i)
pp_list.append("+")
# print('+')
i = i + 1
else:
if (temp_stack[-1] != num_list[cnt]):
if (i>n):
pp_list.append("NO")
break
else:
temp_stack.append(i)
pp_list.append("+")
# print('+')
i = i + 1
else:
temp_stack.pop()
pp_list.append("-")
# print('-')
cnt = cnt + 1
return pp_list
if __name__ == '__main__':
n = int(input())
num_list = list()
for i in range (n):
num = int(input())
num_list.append(num)
check = check_sequence(n, num_list)
if(check[-1] == "NO"):
print("NO")
else:
for i in range(len(check)):
print(check[i])
💟 추가적으로 알게 된 점
- 설계의 중요성: 무조건 들이박기보다는 입력과 출력, 예외 처리, 종결 조건 정리하기
