[Python] 백준 1874 스택 수열

문제 바로가기

   문제분석   

# 스택은 자료를 넣는(push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나온다. (LIFO, Last in First out) 

# 스택에 push하는 순서는 반드시 오름차순이다.

# 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

# 스택에 넣었다가 뽑아 늘어 놓는것은 pop으로 뽑아낸 순서가 입력값 순이라는 뜻.

# push하는 순서는 오름차순이므로 가장 작은 수에서부터 큰 수로 진행된다.

# 스택을 이용해 해당 수열을 만들 수 없을때는 no를 출력한다.

입력값에 따른 출력값 example

1 2 3 4 + + + + 4까지 쌓임
1 2 (3 4) - - 4, 3 순으로 빠진다
1 2 5 6 + + 5, 6이 추가됨
1 2 5 (6) - 6이 빠짐
1 2 5 7 8 + + 7, 8이 추가됨
1 2 5 7 (8) - 8이 빠짐
1 2 5 (7) - 7이 빠짐
(1 2 5) - - - 5, 2, 1 순으로 빠짐

 

 

 

   문제풀이   

num = int(input())
count = 0
result = []  # +,- 담을 리스트(결과값으로 출력)
stack = []  # 넣고 빠지는 숫자 담을 리스트
no_message = True

for _ in range(num):    # 입력값만큼 반복한다.
    input_data = int(input())   # n개의 줄에 수열을 이루는 1이상 n 이하의 정수가 하나씩 순서대로 주어진다.

    while count < input_data:   # 입력값이 카운트보다 더 클때는 push 해줘야 하니까
        count += 1
        stack.append(count)  # 스택에 1 들어가고
        result.append("+")  # push 했으니까 결과에 + 추가

    if stack[-1] == input_data:
        stack.pop()
        result.append("-")
    else:   # 연산이 불가능한 경우
        no_message = False
        break

if no_message == False:
    print("NO")
else:
    print("\n".join(result))

# 입력값으로 수열의 개수인 n개를 받고, n은 반복문의 범위가 된다.

# 오름차순으로 push해줘야 하니까 입력값과 비교할 변수 count를 초기화한다.

# 연산을 담을 리스트와 연산의 대상이 되는 수를 담을 리스트를 각각 초기화한다.

# 그 다음 입력값으로 n개의 줄에 수열을 만들기 위해 필요한 정수를 한개씩 받는다.

•  count가 입력값보다 작다면 count를 하나 올려주고
• 스택과 연산리스트에 각각 +를 추가한다.
• 만약 스택의 마지막 인덱스와 입력값이 같다면 빼줘야하므로 pop을 하고 연산리스트에 -를 추가한다.
• 그렇지 않을경우라면 연산일 불가능 하므로 break로 반복문을 탈출하고

# if문과 else문으로 no를 출력하거나, 줄바꿈을 해서 연산리스트의 결과값을 출력한다.