[CLASS 3]백준 5430번 : AC

5430번 : AC

 

처음에 이 문제를 접했을 때는, 그냥 reverse로 뒤집고 pop몇번 하면 되는거 아닌가? 라고 생각했다. 그래서 다음과 같은 코드를 작성했다.

 

내 코드(시간 초과):

from sys import stdin
input = stdin.readline

for _ in range(int(input())):
    cmd = input().rstrip()
    length = int(input())
    if length:
        li = list(input()[1:-2].split(','))
    else:
        _ = input()
        li = []

    Dcount = cmd.count('D')
    if Dcount > length:
        print('error')
        continue
    elif Dcount == length:
        print('[]')
        continue
    else:
        Dlist = list(map(len,cmd.split('R')))
        for Dnum in Dlist:
            li.reverse()
            for _ in range(Dnum):
                li.pop()

        if cmd[-1] != 'R':
            li.reverse()
        
        print('['+','.join(li)+']')

 

pop함수의 경우 시간 복잡도가 O(1)이지만 reverse함수의 경우 시간 복잡도가 O(n)이다. 이 코드는 뒤집고 버리고를 반복하는데, 처음부터 계속 뒤집기 때문에 처음에 배열의 길이가 길 때는 시간 손실이 크다. 그래서 다음과 같은 코드로 수정했다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

for _ in range(int(input())):
	# 명령어 입력
    cmd = input().rstrip()
    # 배열(리스트)의 길이
    length = int(input())
    # 길이가 양수라면, 숫자만 뽑아서 li에 저장
    if length:
        li = list(input()[1:-2].split(','))
    # 길이가 0이하라면 li를 빈 리스트로 초기화
    else:
        _ = input()
        li = []
	
    # 명령어에서 D가 나오는 횟수 계산
    Dcount = cmd.count('D')
    # 배열의 총 길이보다 크다면 error 출력
    if Dcount > length:
        print('error')
        continue
    # 배열길이와 같다면 [] 출력
    elif Dcount == length:
        print('[]')
        continue
    else:
    	# R을 기준으로 명령어 잘라서 Dlist에 연결된 D들의 길이를 저장
        Dlist = list(map(len,cmd.split('R')))
        # 왼쪽에서 잘라낼 개수
        popLeft = sum(Dlist[0::2])
        # 오른쪽에서 잘라낼 개수
        popRight = sum(Dlist[1::2])
		
        if popRight:
            li = li[popLeft:-popRight]
        # 오른쪽에서 하나도 뽑지 않아서 popRight가 0일 경우
        else:
            li = li[popLeft:]
        
        # R이 홀수개 였을 경우 마지막에 한번 리스트 뒤집음
        if len(Dlist)%2 == 0:
            li.reverse()
        
        # 출력
        print('['+','.join(li)+']')

지금 보니 continue 2개는 필요가 없다😅😅😅

 

 

이번에는 리스트 슬라이싱을 적극 활용해서 자른다. 리스트 슬라이싱의 시간 복잡도는 결과 함수의 길이, 예를 들어 li[a:b]라면 O(b-a)이다. 즉 이 코드를 따르면 꽤 효율적인 방법으로 리스트를 자를 수 있다. R이 짝수개였다면 마지막에 리스트를 뒤집을 필요도 없으므로 더 좋다.

 

 

 

여담

 

와! 파이썬 1등!