백준 1874번. 스택수열

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

1874번: 스택 수열

문제설명 : 

ex ) 4 3 6 8 7 5 2 1 을 입력했을때 수열을 만들 수 있는지 수열이 되는지 확인해보는 문제이다.

스택으로 문제를 풀어본다.

* 4 : 4까지 스택에 push(총 4번) 해준다. 그럼 스택은 LIFO 이기 때문에 스택의 TOP는 4가 될 것 그리고 찾아야 할 숫자 4 같으면 pop 해준다.

* 3 : 3은 4가 pop된 이후 top가 3이 되었다 그렇기 때문에 pop만 해주면 된다.

* 6 : 숫자는 이제 5부터 다시 push를 시작해 6이 될때까지 2번의 push을 진행한다. 스택의 top이 6이 되었으며 찾아야 될 수가 6이기 때문에 pop

* 8 : 7부터 다시 push을 해주며 8까지 해준다. 스택의 top이 8이 되었으며 찾아야 될 수가 8이기 때문에 pop

* 7 : 스택의 top이 7이 되었으므로 pop만 진행한다.

* 5,2,1 : 스택엔 top 부터 5 2 1 이 남아있어 순차적으로 같으므로 pop만 해주면 된다.

    while i < num:
        if str(i+1) not in rember_num:
            print(i+1)
            stack.append(i+1)
            print("push", "+")
       i = i + 1

* 찾아야될 숫자가 4인데 스택에 그 번호까지 없다면 그 번호에 다 다를때까지 스택에 추가하며 push 하는 코드이다.

   4를 찾기위해 1,2,3,4까지 push 하는 것

stack = []
rember_num = ''
for num in nums:
    i = 0
    if stack:
        if stack[-1] > num and stack[-1] == num:
            rember_num = rember_num + str(stack.pop())
            print("pop", "-")
            continue
        i = stack[-1]
        print("rem = ", rember_num)

 

* nums = [ 4,3,6,8,7,5,2,1 ]

* 스택을 만들어 줬다.

* for문을 돌려 값을 하나하나 가져왔다.

* 만약 스택에 데이터가 있으면 stack[-1] 즉 top 과 비교해야할 num 을 비교하여 같으면 pop 한다.

   이때, 제거되는 숫자 4는 rember_num에 기록했다.

 * stack[-1] < num 인 경우 i 의 자리를 가장 끝(top)으로 재배치 해주어야 한다.i 의 값을 바꿔준다

 

    if num == stack[-1]:
        rember_num = rember_num + str(stack.pop())
        print("pop", "-")

* 만약 pop이 될 수와 찾아야될 수가 같으면 pop을 해준다.

* 삭제된 숫자는 rember_num에 기록해준다.

 

실행결과..! 

nums = [1,2,5,3,4]

 

이 케이스의 경우 실패했다!

원인 1,2,5까지 push, pop이 동작했지만 남아있는 3,4,를 처리해줄 코드가 없다!

 

pop을 할때 rember_num에 기록을 계속해야하는가에 대한 의문이 생겼다.

rember_num을 기록한 이유는 반복문을 돌리면 i=0이 되기때문에 어디까지 stack에 기록했는지 초기화 된다.

그렇기 때문에 rember_num에 기록하여 가장 마지막에 있는 숫자를 가져와 i에 대입하려 했다. 마치 기록장과 같은 역할..!

 

또한, 다음 코드가 중복해서 들어갔다. 이것을 처리 할 방법이 없을까? 

        if num == stack[-1]:
            rember_num = rember_num + str(stack.pop())
            print("pop", "-")

 

우선 i는 for문 밖으로 뺀다 그럼 다시 반복문을 돌아도 어디까지 push을 했는지 위치가 저장되어있다

i => cur로 변경

cur = 1
for num in nums:
    while cur <= num:
        stack.append(cur)
        answer.append("+")
        #print("push +")
        cur = cur+1

    if num == stack[-1]:
        stack.pop()
        answer.append("-")
        #print("pop -")

중복되는 if문은 밑에서 처리하기로 했다. 처음에 바로 처리하면 스택이 비어있을때 stack[-1]가 없다!

    else:
        #print("NO")
        answer.clear()
        answer.append("NO")
        return answer

위와 연결되는 if-else문인데 두 값이 같지않다면 만약 찾아야 될 수가 5인데 stack의 top이 8이라고 가정하자

그럼 스택에는 1~8까지 push pop을 해왔을것 그렇기 때문에 5를 찾을 수 없다. 

그래서 NO만 리턴해줄 것

 

실행코드

start = time.time()

for i in stack_sequence_2(nums):
    print(i, end=" ")

print()
end = time.time()
print("실행 시간 =", end-start)