[백준/파이썬] AC

문제 링크

---

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

5430번: AC

실패한 첫 코드

from collections import deque
import re

t=int(input())

for _ in range(t):
    p=input()
    p=list(p) #함수를 쪼개서 리스트로 넣기
    n=int(input())
    num=input()
    #num=re.sub('[|,|]','',num)
    if num=='[]':
        print('error')
        continue
    num=num.replace('[','')
    temp=''
    q=deque()
    for i in num:
        if i==',' or i==']':
            q.append(int(temp))
            temp=''
        else:
            temp+=i
    #정수 배열로 쪼개서 리스트로 넣기

    for i in range(len(p)):
        if p[i]=='D':
            if len(q)==0:
                print('error')
                break
            else:
                q.popleft()
        elif p[i]=='R':
            q.reverse()
        if i==len(p)-1:
            print(list(q))

이거 풀려고 별의 별 짓을 다한 것 같다.

…

정답 코드

from collections import deque
import sys

t=int(sys.stdin.readline())

for _ in range(t):
    p=sys.stdin.readline().strip()
    p=list(p)
    n=int(sys.stdin.readline())
    num=sys.stdin.readline().strip()
    if num=='[]':
        if 'D' in p:
            print('error')
        else:
            print(num)
        continue

    num=num.replace('[','')
    temp=''
    q=deque()
    for i in num:
        if i==',' or i==']':
            q.append(temp)
            temp=''
        else:
            temp+=i
    
    cnt=0
    for i in range(len(p)):
        if p[i]=='D':
            if len(q)==0:
                print('error')
                break
            else:
                if cnt%2==0:
                    q.popleft()
                else:
                    q.pop()
        elif p[i]=='R':
            cnt+=1
        if i==len(p)-1:

            if cnt%2==0:
                print("["+",".join(list(q))+"]")
            else:
                q=list(q)
                q=q[::-1]
                print("["+",".join(q)+"]")

처음에 나는 이 문제를 간단하게 생각해서 음 reverse()쓰고~ 큐를 이용하고, 각자 문자열 잘라서 넣고 popleft() 써서 풀면 되겠지 정도로 생각했다.

근데 시간초과가 발생했다.

큐를 사용해도 시간초과가 발생한다고?

 

찾아보니 reverse()를 사용하면 시간복잡도 O(N)이 걸리기 때문에 포문 안에서 reverse()를 사용하면 매번 포문 안에서 배열의 숫자만큼 연산을 돌게 되기 때문에 시간초과가 날 수밖에 없었다.

그래서 reverse()와 [::-1] 둘 다 사용하지 않고 뒤집는 것이 필요했는데…

아무리 생각해도 방법이 생각나지 않아서 질문 게시판을 계속 뒤적거렸다.

그렇게 해서 찾게 된 것은 R을 발견할 때마다 카운트해줘서 홀수일 때는 뒤집어서 출력하고 짝수일 때는 그대로 출력하면 된다.

그렇게 고쳤는데도 오답처리됐다.

이번에도 어디서 틀렸는지를 찾지 못해서 질문 게시판을 뒤적거렸는데, 출력에서 나는 리스트 그대로 출력해서 [1, 2] 이런식으로 숫자 사이에 공백이 들어가서 출력이 됐다. 정답은 [1,2] 이렇게 공백없이 출력되어야 한다. 그래서 join을 사용해서…출력을 해야 한다.

그리고… 빈 배열인 []를 입력받았을 때 D가 있으면 error를 출력하고 없으면 빈 배열 []를 그대로 출력하는 처리 또한 필요했다.

 

그래서 내가 문제에서 놓친 부분은 다음 세 가지였다.

1. 원소를 뒤집는 부분에서 reverse()를 사용하면 시간 초과가 발생하기 때문에, R을 발견하면 카운트를 세서, D 연산을 할 때 홀수라면 뒤집힌 상태에서 첫 번째 원소를 지워야 하기 때문에 pop() 으로 오른쪽을 지운다. 짝수라면 뒤집히지 않은 상태에서 첫 번째 원소를 지워야 하기 때문에 popleft()로 왼쪽을 지운다. 출력할 때도 카운트가 홀짝일 때 나눠서 각각 뒤집어서 출력, 그대로 출력 한다.
2. 출력할 때 공백이 없어야 하기 때문에, join을 사용해서 출력해야 한다.
3. 빈 배열인 []을 입력받았을 때 D가 있으면 error를 출력하고, 없으면 빈 배열 []을 그대로 출력해야 한다.

 

항상 문자열을 사용하는 문제는 어려운 것 같다. 여기서 시간복잡도도 생각해서 풀려니 막힌 부분이 있었다.

앞으로도 열심히 공부해야 겠다...