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

알고리즘

python 백준 스택 수열(1874)

 

1. 문제

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

 

2. 풀이

• 숫자를 넣어줄 stack과 정답이 들어갈 answer list를 만들어 준다
• while문에 조건을 걸어 입력한 수를 만날 때 까지 오름차순으로 push를 한다
• 수에 맞게 stack을 쌓고 answer list에도 오른 숫자만큼 +를 추가해준다
• 입력한 수를 만나면 while문을 탈출하고 if문을 만나 입력한 수가 stack의 top과 같으면 스택의 top을 꺼내고 answer에 -를 추가해준다
• stack의 top이 입력한 수와 다르면 스택을 만들 수 없기 때문에 NO를 프린트한다
• 최종적으로 flag가 0이면 answer를 for문을 돌려 하나씩 출력해준다

n = int(input())
stack = []
answer = []
cur = 1
flag = 0

for i in range(n):
    num = int(input())
    while cur <= num:  # 입력한 수를 만날 때 까지 오름차순으로 push
        stack.append(cur)
        answer.append('+')
        cur += 1
        # 입력한 수를 만나면 while문 탈출. cur = num일 때 까지 while문을 돌아 스택을 쌓는다.

    if stack[-1] == num:  # stack의 TOP이 입력한 숫자와 같으면
        stack.pop()         # 스택의 TOP을 꺼내 수열을 만들어 준다.
        answer.append("-")
    else:                   # stack의 TOP이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
        print("NO")         # 왜냐하면 12345 처럼 오름차순으로 스택이 입력되는데
        flag = 1            # TOP이 num보다 크면 num은 TOP보다 더 아래에 쌓여있기 때문이다.
        break
if flag == 0:
    for i in answer:
        print(i)

 

[새로 배운내용]

스텍의 개념

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. Last In First Out(LIFO)
• 예시 ) 컴퓨터의 되돌리기(Ctrl + z)

스텍의 구현

• push(data) : 맨 앞에 데이터 넣기
• pop() : 맨 앞의 데이터 뽑기
• peek() : 맨 앞의 데이터 보기
• isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

 

[느낀점]

• 스텍이라는 자료구조를 배우고 응용해볼 수 있는 문제였다. 개념 자체는 어렵지 않지만 머리에 손에 익힐려면 연습을 많이 해봐야겠다.