[BOJ] 5430 : AC [구현/덱](Python)

문제 링크

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

5430번: AC

소스 코드

import sys
from collections import deque,Counter
input = sys.stdin.readline

t = int(input().rstrip())
for _ in range(t):
    function = list(input().rstrip())
    function_count = Counter(function) # 개수 세기
    leng = int(input().rstrip()) # 리스트 길이
    nums = input().rstrip() # 리스트 입력 받기

    # (1)'D'의 개수가 리스트의 길이보다 큰 경우 불가능
    if function_count["D"] > leng:
        print("error")
    else: 
        # 리스트 초기화
        queue = deque([])
        temp = ""
        for num in nums:
            if num == "[": continue
            elif num.isdigit(): # 숫자인 경우
                temp += num
            else: # 숫자 확인되면 큐에 추가
                if temp != "":
                    queue.append(int(temp))
                    temp = ""
                else: continue

        flag = True # 에러 발생 여부
        reverse = False # 뒤집힘 상태
        for i in range(len(function)):
            if function[i] == "R": # 뒤집기
                if not reverse: reverse = True
                else: reverse = False
            else:
                # (2) 뒤집힘에 따라 좌,우에서 pop
                if queue and not reverse:
                    queue.popleft()
                elif queue and reverse:
                    queue.pop()
                else: # 뽑을 원소가 없는 경우
                    flag = False
                    break
        
        if not flag: print("error") # 에러가 발생한 경우
        else: 
            # 뒤집히지 않은 상태라면 그대로 출력
            if not reverse: print("[" + ",".join(map(str,queue)) + "]")
            else: # 뒤집혔다면 반영해서 출력
                queue.reverse()
                print("[" + ",".join(map(str,queue)) + "]")

 

해설

• 구현은 어렵지 않으나 시간 제한이 빡빡하다.
• 리스트를 매번 뒤집으면 시간 초과를 피할 수 없다.

사실 구현하는 것 자체는 그렇게 어렵지 않은 유형이다.

그런데 누가 봐도 시간 제한을 빡빡하게 준 느낌이 든다.

여러 개의 테스트 케이스를 확인해야 함과 동시에 리스트의 길이 자체도 굉장히 길어질 수 있기 때문에, 일반적인 리스트로는 절대 풀지 못할거라는 판단이 섰다.

 

또한 뒤집는 것도 시간을 많이 잡아먹는 요인이 될 것이라고 생각했다. 길이가 긴 리스트를 매번 뒤집어야 한다면 시간이 오래 걸릴 것인데 처음에는 이걸 효율적으로 해결할 방법이 떠오르지 않았다.

 

위 풀이에서 가장 아쉬운 것은 숫자 리스트를 받아오는 과정이다.

그냥 join 함수로 숫자들만 걸러서 받을 수 있었는데 그게 떠오르지가 않아서 일일이 숫자인지 확인하고 누적해서 queue에 추가하는 짓을 저질렀다.

결국 이 부분에서 처리 시간이 추가로 걸리지 않았나 생각한다.

 

(1) 'D'의 개수 세기

'D'는 리스트의 가장 앞 원소를 빼는 명령이다.

따라서 주어진 전체 명령에 포함된 'D'의 개수가 리스트 전체 길이보다 크다면 이 명령은 끝까지 수행될 수 없다(에러가 필연적으로 발생한다).

비어있는 리스트에 D를 입력하면 에러가 발생한다고 문제에서 설명되어 있다.

 

따라서 D의 개수를 Counter 를 통해 센 뒤, 이것이 리스트의 길이보다 긴 경우에는 어떤 작업도 수행하지 않고 바로 'error'를 출력하도록 했다.

    # (1)'D'의 개수가 리스트의 길이보다 큰 경우 불가능
    if function_count["D"] > leng:
        print("error")

 

(2) 리스트를 실제로 뒤집지는 않는다.

(스스로 떠올렸던 좋은 아이디어라 뿌듯했다)

 

맨 처음 고민했던 것처럼 리스트 전체를 뒤집는 것은 시간이 오래 걸리는 처리 중 하나다.

그런데 생각해보니 어차피 맨 앞의 원소만 뽑아낼 것이라면, 

뒤집어진 리스트에 대해서는 맨 뒤의 원소만 뽑아주면 되는 것이라는 걸 떠올릴 수 있었다.

 

[1,2,3,4,5] 이 상태에서 D를 만나면 숫자 1이 빠져나가고 [2,3,4,5] 가 된다.

[1,2,3,4,5] 이 상태에서 RD를 만나면 숫자 5를 빼고 [1,2,3,4] + 뒤집힌 상태가 된다.

[1,2,3,4,5] 이 상태에서 RRD를 만나면 숫자 1이 빠져나가고 [2,3,4,5] + 뒤집히지 않은 상태가 된다.

 

즉, 우리는 매번 리스트를 실제로 뒤집을 필요 없이 '리스트가 뒤집혀 있는지 아닌지'를 기록하면 되는 것이다.

리스트가 뒤집혀 있는 경우에는 맨 오른쪽 원소를(pop) 뽑아내고,

뒤집히지 않은 정상 상태인 경우에는 맨 왼쪽 원소(popleft)를 뽑아내면 된다.

 

 

위 과정이 모두 끝났을 때에도 뒤집힌 상태를 고려하여 리스트를 출력하면 된다.

이때 주의할 점은 현재 deque 자료형인 queue를 list 함수를 통해 변환하면(list(queue)) 각 원소 사이에 공백이 끼어 있을 것이라는 점이다.

따라서 그 공백들을 제거해주기 위해 join 함수를 사용하고, join 함수의 매개변수로는 str(문자열)만 올 수 있다는 것도 신경써야 한다.