[BOJ] 5430 - AC

엄혜영·2024년 4월 22일

algorithm boj

알고리즘 챌린저까지

목록 보기

11/11

요즘 푸는 문제는 죄다 어찌저찌 출력은 잘 나오는데

막상 제출하면 틀렸거나 시간 초과다.

내 코드가 똥인걸 우째... 분석이나 잘 해보자.

문제의 코드

from collections import deque
import sys

testcase = int(input())

for i in range(testcase):
    order = sys.stdin.readline().strip('\n')
    listlength = int(sys.stdin.readline())
    acstr = sys.stdin.readline().strip('[]\n')
    error = False
    if len(acstr)==0:
        print('error')
        continue
    aclist = deque(map(int, acstr.split(',')))

    orderlist = list(order)
    for ord in orderlist:
        if ord=='R':
            aclist = list(aclist)
            aclist = aclist[::-1]
            aclist = deque(aclist)
        else:
            if len(aclist)==0:
                error = True
                break
            aclist.popleft()
    if error:
        print('error')
    else:
        aclist = list(aclist)
        print(aclist)

맨 첫 줄에 테스트 케이스의 개수를 입력받고

테스트 케이스 만큼 반복하며 출력을 해야하는 문제이다.

내가 짠 코드는 이중 for 문을 통해 문제를 해결하고 있다.

해당 문제를 풀기 위해서는 이것 이상으로 반복문을 줄일수는 없을 것이다.

그래서 결과로 시간초과가 나왔을 때 당황스러웠다.

아니... 더 이상 줄일게 없는데..?

내가 알던 네가 아냐

눈알 빠져라 코드를 보던 중 눈에 띈 슬라이싱

위의 코드에서는 R(뒤집기)를 하기 위해서 슬라이싱으로 리스트를 뒤집어주고 있다.

지금까지 아무 생각 없이 써도 아무 문제도 발생하지 않아서 몰랐는데,

슬라이싱이 생각보다 많은 시간을 잡아먹는다고 한다.

아니 나는 그냥 너가 빠른 애인줄 알았지....

Q. string slicing이 시간소요가 큰가요?
A. python 의 슬라이싱은 매번 새로운 객체를 만들어내는 O(n) 연산입니다.
블로그를 더 찾아보니 정확히는 O(b-a)의 시간 복잡도를 가진다고 한다.

그래서 문제가 되는 슬라이싱 관련 코드를 제거하고

뒤집기를 해야 하는지 판별하는 isR를 이용해

'R' 명령이 들어오면 ~isR을 해주었다.

'D' 명령이 들어오면 isR의 상태에 따라 pop()/popleft()를 한다.

+) 항상 디테일에 주의하자

위의 수정으로 시간 초과 문제를 벗어났는데 바로 함정에 빠졌다.

어려운 문제인가 했는데.........

리스트를 그냥 바로 출력했을 때 공백이 있던게 문제였던 것 같다.

ㅎㅎ...

해결 완료!

from collections import deque
import sys

testcase = int(input())

for i in range(testcase):
    order = list(sys.stdin.readline().strip('\n'))
    listlength = int(sys.stdin.readline())
    acstr = sys.stdin.readline().strip('[]\n')
    error = False
    isR = False
    if len(acstr)==0:
        aclist = deque()
    else:
        aclist = deque(map(int, acstr.split(',')))

    for ord in order:
        if ord=='R':
            isR = ~isR
        else:
            if len(aclist)==0:
                error = True
                break
            if ~isR:
                aclist.popleft()
            else:
                aclist.pop()
    if error:
        print('error')
        continue

    aclist = list(aclist)
    if isR:
        aclist = aclist[::-1]
    print('[', end='')
    for i in range(len(aclist)):
        if i==len(aclist)-1:
            print('{}'.format(aclist[i]), end='')
            break
        print('{},'.format(aclist[i]), end='')
    print(']')