[CodingTest] 백준 #5430 AC

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

5430번: AC

 

문제 자체가 어려운 건 아니었는데 시간 초과 때문에 좀 해맸다. 

그래도 스스로 풀어서 다행쓰 

---

시도 1 - 시간 초과

from collections import deque
T = int(input())
for i in range(T):
    p = input()
    n = int(input())
    line=input()
    if len(line)!=2:
        arr = deque(map(int,line[1:-1].split(',')))
    else:
        arr=[]
    flag=0
    for item in p:
        if item=='R':
            arr.reverse()
            
        elif item=='D':
            if arr:
                arr.popleft()
            else:
                flag=1
                print('error')
                break
    if flag==0:
        print('['+','.join(map(str,list(arr)))+']')

덱을 사용했고, 받은 배열형태의 문자열을 split해서 arr 리스트에 넣어주었다.

R이면 arr을 뒤집었고, D이면 첫번째 원소를 삭제하는 방법을 사용했다. 

시간초과 이유가 reverse가 시간 복잡도가 O(n) 이기 때문인 것 같아서 개선을 위해 다른 방법을 시도했다.

 

---

시도 2 - 시간 초과

from collections import deque
import sys
T = int(sys.stdin.readline())
for i in range(T):
    p = sys.stdin.readline()
    n = int(sys.stdin.readline())
    line=sys.stdin.readline().strip()
    if len(line)!=2:
        arr = deque(map(int,line[1:-1].split(',')))
    else:
        arr=[]
    flag=0
    count=0
    i=0
    isReverse=False
    while True:
        
        if p[i]=='R':
            #O(N)
            count+=1
            while i!=n-1:
                
                if p[i+1]=='R':
                    count+=1
                    i+=1
                if p[i+1]=='D':
                    i+=1
                    break;
            
            
            if count%2==1:
                if i>=len(p)-1:
                    flag=1
                    arr.reverse()
                    print('['+','.join(arr)+']')
                    break
                else:
                    isReverse=True
    
        if p[i]=='D':
            if arr:
                if isReverse==False:
                    arr.popleft()
                else:
                    arr.pop()
                i+=1
            
            else:
                flag=1
                print('error')
                i+=1
                break
        if i>=len(p)-1:
            break
    if flag==0:
        print('[',end='')
        for i in range(len(list(arr))):
            if i!=len(list(arr))-1:
                print(arr[i],end=',')
            else:
                print(arr[i],end=']')
                print()
        #print('['+','.join(map(str,list(arr)))+']')

 

ㅋㅋ 뻘짓 ㅠ for 대신 while문을 사용해서 연속되는 R의 갯수를 count 변수에 담은 담음, count가 짝수이면 결국 reverse하지 않은 형태이므로 뒤집지 않고, count가 홀수이면 reverse 해주었다.

이렇게 R에 대한 연산을 수행하고 D를 수행하니 D는 popleft()만 사용하게 되었다.

이쪽으로 생각이 한 번 빠지니 더 좋은 생각이 나지 않아서 자고 일어나서 다시 생각해보기로 했다.

 

---

시도 3 - 성공 

from collections import deque
import sys
T = int(sys.stdin.readline())
for i in range(T):
    p = sys.stdin.readline()
    n = int(sys.stdin.readline())
    line=sys.stdin.readline().strip()
    if len(line)!=2:
        arr = deque(map(int,line[1:-1].split(',')))
    else:
        arr=[]
    flag=0
    isError=0
    for item in p:
        if item=='R':
            flag= abs(flag-1)
            
        elif item=='D':
            if arr:
                if flag==1: #reverse 모드 
                    arr.pop()

                if flag==0:
                    arr.popleft()
            else:
                isError=1
                print('error')
                break
    if isError==0:
        if flag==1:
            arr.reverse()
        print('['+','.join(map(str,list(arr)))+']')

시도 2는 결국 여러번 Reverse하는 상황이 올 수 밖에 없기 때문에 최대길이가 10만이므로 결국 시간 복잡도가 O(n)에 가까울 수밖에 없다는 생각이 들었다.

그래서 D를 수정했다. R이 들어올 때마다 flag를 사용해서 현재 역순 모드 인지 비 역순 모드인지 체크해주었다.

D가 들어오는 여부와 상관없이 다음 R이 들어올 때까지 역순, 혹은 비 역순모드는 유지되므로, 굳이 R이 연속으로 들어왔는지를 확인할 필요가 없었다.

따라서, flag가 1이면 역순모드로, arr의 마지막 원소를 pop해주었고, flag가 0이면 비역순 모드로 arr의 첫번째 원소를 pop해주었다. 

출력하는 마지막에만 flag가 1일 때, 즉 역순모드일 때 reverse를 해주었다.

에러를 체크하는 변수는 isError로 새로 만들어 사용했다. 

input()을 사용해도 Python3를 통과했지만 시간을 더 줄이기 위해 sys.stdin.readline()을 사용해주었다.

 

---

다른사람코드 1

import sys
for tc in range(int(sys.stdin.readline())):
    ops = list(map(len, sys.stdin.readline().rstrip().replace('RR','').split('R')))
    N = int(sys.stdin.readline())
    line = sys.stdin.readline().rstrip()
    
    dq = line[1:-1].split(',') if N else []
    bound = [sum(ops[0::2]), sum(ops[1::2])]
    if sum(bound) > N:
        print('error')
        continue
    dq = dq[bound[0]:N-bound[1]]
    if len(ops)%2 == 0:
        dq.reverse()
    print('['+','.join(dq)+']')

해석해보기 ㅠ

---

시간초과, 메모리초과가 제일 어려운 것 같다 ㅠㅠㅠ 흑흑 .. 넘나 답답쓰.. 

각종 메소드들에 대한 시간복잡도도 공부를 해주어야 할 것 같다..

그리고 너무 안 풀리면 맑은 정신일 때 다시 풀어야 쉽게 풀리는 것 같다.