[Python] 백준 풀기 1874 - 스택 수열

파이썬 백준 1874번

실버2

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

1874번: 스택 수열

 

 

 

 

 

문제 보기

분류: 자료 구조, 스택

 

 

 

 

 

문제 풀기

문제를 풀기에 앞서 무슨 소리를 하는지 이해하는데 시간이 걸렸다. 결국은 검색을 통해 문제가 이야기하고자 하는 것의 방향성을 잡을 수 있었는데 그분들도 문제를 이해하는데 어려움이 있었다고 한다;;;

 

 

여하튼 문제에서 말하고자 하는 것은

 

stack 이 1, 2, 3 ... 순차적으로 쌓여갈 때 주어진 행렬의 index 0 의 value 와 같은 값이 있으면 pop 을 하고, 다음 index 의 value 와 같은 값이 있으면 pop 또는 push 를 계속적으로 해나가면서 주어진 행렬을 만들어 가는 것이다.

 

 

push 나 pop 을 하여도 주어진 행렬을 만들 수 없는 경우라면 "NO" 를 프린트한다.

 

 

 

코드의 진행은 숫자의 개수 n 을 입력받고 주어진 수들로 배열 저장한 후 fnCreatingSequenceWithAscendingStack(given_sequence) 함수에 넣어 push, pop, NO 를 찾는다.

 

 

주어진 수열의 list 를 원소 하나하나 빼내어 1, 2, 3, ... 으로 증가하는 stack_count 또는 stacking_box[-1] 와 비교하여 push, pop 에 해당하는 "+", "-" 를 순차적으로 저장한다.

 

    stacking_box = []
    pushpop = []
    stack_count = 1

    for seq in given_sequence:
        while stack_count <= seq:
            stacking_box.append(stack_count)
            pushpop.append("+")
            stack_count += 1
        if seq == stacking_box[-1]:
            stacking_box.pop()
            pushpop.append("-")

 

 

모든 for seq in given_sequence: 에 대해 결과가 반영되면 return pushpop 을 한다.

 

 

만약 반복문을 도는 중에 수열 list 의 원소가 while 과 if 문을 모두 지나치면 return "N" 을 해준다.

 

 

return 된 결과 result 를 프린트해준다.

 

    for r in result:
        if r == "N":
            print("NO")
        else:
            print(r)

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnCreatingSequenceWithAscendingStack(given_sequence):
    stacking_box = []
    pushpop = []
    stack_count = 1
    for seq in given_sequence:
        # print(f'seq: {seq}')          # test print
        
        while stack_count <= seq:
            # print(f'stack_count: {stack_count}')            # test print
            
            stacking_box.append(stack_count)
            # print(f'pushed_stacking_box: {stacking_box}')         # test print
            pushpop.append("+")
            stack_count += 1
            
        if seq == stacking_box[-1]:
            stacking_box.pop()
            # print(f'popped_stacking_box: {stacking_box}')         # test print
            pushpop.append("-")
        else:
            return "N"
            
    # print(f'pushpop: {pushpop}')          # test print
    return pushpop


if __name__ == "__main__":
    n = int(inputdata().strip())
    given_sequence = []
    for _ in range(n):
        given_sequence.append(int(inputdata().strip()))
    
    # print(given_sequence)           # test print
    
    result = fnCreatingSequenceWithAscendingStack(given_sequence)
    for r in result:
        if r == "N":
            print("NO")
        else:
            print(r)

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline

def fnCreatingSequenceWithAscendingStack(given_sequence):
    stacking_box = []
    pushpop = []
    stack_count = 1
    for seq in given_sequence:
        print(f'seq: {seq}')          # test print
        
        while stack_count <= seq:
            print(f'stack_count: {stack_count}')            # test print
            
            stacking_box.append(stack_count)
            print(f'pushed_stacking_box: {stacking_box}')         # test print
            pushpop.append("+")
            stack_count += 1
            
        if seq == stacking_box[-1]:
            stacking_box.pop()
            print(f'popped_stacking_box: {stacking_box}')         # test print
            pushpop.append("-")
        else:
            return "N"
            
    print(f'pushpop: {pushpop}')          # test print
    return pushpop


if __name__ == "__main__":
    n = int(inputdata().strip())
    given_sequence = []
    for _ in range(n):
        given_sequence.append(int(inputdata().strip()))
    
    print(given_sequence)           # test print
    
    result = fnCreatingSequenceWithAscendingStack(given_sequence)
    for r in result:
        if r == "N":
            print("NO")
        else:
            print(r)



# 8
# 4
# 3
# 6
# 8
# 7
# 5
# 2
# 1

# [4, 3, 6, 8, 7, 5, 2, 1]

# seq: 4
# stack_count: 1
# pushed_stacking_box: [1]
# stack_count: 2
# pushed_stacking_box: [1, 2]
# stack_count: 3
# pushed_stacking_box: [1, 2, 3]
# stack_count: 4
# pushed_stacking_box: [1, 2, 3, 4]
# popped_stacking_box: [1, 2, 3]

# seq: 3
# popped_stacking_box: [1, 2]

# seq: 6
# stack_count: 5
# pushed_stacking_box: [1, 2, 5]
# stack_count: 6
# pushed_stacking_box: [1, 2, 5, 6]
# popped_stacking_box: [1, 2, 5]

# seq: 8
# stack_count: 7
# pushed_stacking_box: [1, 2, 5, 7]
# stack_count: 8
# pushed_stacking_box: [1, 2, 5, 7, 8]
# popped_stacking_box: [1, 2, 5, 7]

# seq: 7
# popped_stacking_box: [1, 2, 5]

# seq: 5
# popped_stacking_box: [1, 2]

# seq: 2
# popped_stacking_box: [1]

# seq: 1
# popped_stacking_box: []

# pushpop: ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-', '-', '-', '-']

# +
# +
# +
# +
# -
# -
# +
# +
# -
# +
# +
# -
# -
# -
# -
# -