글 읽기 - [파이썬] 1874번 어느 부분이 틀렸는지 감이 오지 않습니다.

ljh98 1년 전 0

제 코드입니다. stack을 활용해보았으나 어느 부분이 틀렸는지 감을 못잡겠어서 질문을 남깁니다.

혹시 어느 부분이 틀렸는지 아시겠다면 답변 달이주시면 감사하겠습니다.

또한, 코드에서 부족한 부분이나 더 나은 방향이 있다면 함께 조언 부탁드립니다.

읽어주셔서 감사합니다.

import sys

n = int(sys.stdin.readline())
sequence = []
stack =[]
consequence = []
for i in range(n):
    sequence.append(int(sys.stdin.readline())) # ex)예제 테스트 케이스 1번 [4,3,6,8,7,5,2,1,]

while(True):
    for i in range(1,n+1):
        stack.append(i)
        consequence.append('+') # 1. stack에 1부터 값을 push 합니다.

        while(True):
            if(len(stack) != 0 and stack[-1] == sequence[0]): #stack에 데이터가 있을 경우, sequence의 먼저 나와야 하는 값이 스택에 마지막에 위치하면 pop() 합니다.
                stack.pop()
                sequence.pop(0)
                consequence.append('-')
            else:
                break

    if(len(stack) != 0): #만약 stack에 1~n까지의 값이 다 들어갔는데도 불구하고, 아직 스택에 값이 남아있는 경우를 처리합니다.
        while(True):
            if(len(stack) == 0): 
                break
            if(stack[-1] == sequence[0]):  #위의 동작과 같은 원리 입니다.
                stack.pop()
                sequence.pop(0)
                consequence.append('-')
            else:
                print('No')
                sys.exit(0)

    for i in consequence: #마지막 스택이 말끔히 비워졌다면 결과 값을 출력합니다.
        print(i)
    break

jeonggu223 1년 전 0

불가능한 경우 NO를 출력한다.

오타가 현재 있습니다.. 소문자가 아니에요!

그리고 따로 코드를 손보자면 아마 sequcne.pop(0) 연산을 진행하셨는데 이는 시간초과의 위험성이 존재합니다.

리스트에서 0번째의 인덱스를 빼게 되면 1~n-1번째 인덱스는 모두 한 칸씩 땡겨지는 shift연산이 일어나게 됩니다. 즉 n번의 연산이 이루어진다는 것이죠.

최악의 경우에는 n이 10만이고, 10만부터 내림차순으로 입력값이 주어진다면 엄청난 shift연산이 일어나겠죠?

이 경우를 개선해보시면 좋을 것 같아요.

ljh98 1년 전 0

헉.. 너무 민망하네요..

거기서 틀렸을거라고는 생각 못했고, 몇번의 검토에서도 눈에 들어오지 않았네요 ㅠㅠㅠ

다음부터 제대로 검토하고 올리겠습니다 부끄럽네요..

조언해주신 sequence 부분은 다시 고민해보겠습니다. 그 부분까지는 미처 고려하지 못했네요.

pop()을 하는 방식이 아닌 임의로 index를 지정하거나, 혹은 더 좋은 방법이 있는지 고려해보겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 1874번 어느 부분이 틀렸는지 감이 오지 않습니다.

ljh98 1년 전 0

jeonggu223 1년 전 0

ljh98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말