[Baekjoon] 5430번: AC

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

5430번: AC

 

문제 설명

새로운 언어 AC를 만들었다고 합니다.

R은 배열에 있는 숫자의 순서를 뒤집는 명령어고 D는 첫 번째 숫자를 버리는 함수라고 합니다.

 

명령어, 배열크기, 배열이 각각 주어졌을 때 명령어가 실행된 후 배열의 상태를 출력하는 문제입니다.

 

예를 들어 RDD라고 명령어가 주어졌으면

주어진 배열에 뒤집기, 첫 번째 숫자 삭제, 첫 번째 숫자 삭제를 수행한 후 배열에 남아있는 요소를 출력하면 됩니다.

첫 번째 숫자를 뽑을 수 없으면 error를 출력합니다. 

 

 

소스코드 & 설명

우선 이 문제를 가장 처음 봤을 때 자료구조 덱(deque, deck)을 사용해야겠다는 생각이 들었습니다.

왜냐면 덱을 사용하면 양 끝 요소에 대한 삽입, 삭제의 시간 복잡도가 $O(1)$로 매우 효율적이기 때문입니다.

 

*덱은 스택과 큐의 장점을 합친 자료구조로써 양쪽에서 요소를 뽑거나 삽입 가능합니다.

 

D 명령어의 경우에는 첫번째 요소를 뽑는 것이니 그냥 popleft() 해주면 되고

R 명령어의 경우에는 반복문으로 N번 돌려서 오른쪽에서 요소를 뽑고 왼쪽에 append 해주면 되겠다는 생각으로 문제를 풀었습니다.

 

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

repeat = int(input().rstrip())
for i in range(repeat):
    command = input().rstrip()
    length = int(input().rstrip())
    deck = deque(input().rstrip().split(","))
    
    #양쪽 [, ] 뽑아서 제거해준다. -> deck은 양쪽 pop&append 의 시간복잡도가 O(1)
    
    if len(deck) == 1: #한개 들어온경우
        one = deck.pop()
        if one == "[]":
            pass
        else:
            deck.append(one.replace("[", "").replace("]", ""))
    else:
        left = deck.popleft()
        right = deck.pop()
        deck.appendleft(left.replace("[", ""))
        deck.append(right.replace("]", ""))
    
    error = False
    command = command.replace("RR", "") #연속뒤집기는 의미가 없으므로 제거함.
    for element in command:
        if element == "R":
            tmp_deck = deque([])
            while deck: #끝에서 계속 뽑고 임시 덱에 넣어준다.
                tmp_deck.append(deck.pop())
            deck = tmp_deck #임시덱을 원래 덱으로 한다.
        elif element == "D":
            if not deck: #비었으면
                error = True
                break
            else:
                deck.popleft() #맨 처음껄 뺀다.
    if(error == True):
        print("error")
    else:
        print("[", end="")
        for i in range(len(deck)):
            if(i == len(deck) - 1):
                print(deck[i], end="")
            else:
                print(deck[i], end=",")
        print("]", end="")

위와 같이 문제의 조건대로 정직하게 코드를 짠 후 즐거운 마음으로 제출했습니다.

 

당연히 될 거라고 생각하고 제출하니 어김없이 발생하는 시간 초과..

 

input도 아니고 stdin.readline으로 입력받고 있으니 입출력 속도 문제도 아닐 거고 Pypy3로도 통과가 안됩니다.

command = command.replace("RR", "") #연속뒤집기는 의미가 없으므로 제거함.

중간에 RRRRRR 같은 의미 없는 명령어도 replace로 제거하고 들어갔는데 시간 초과가 계속 뜨네요

( *RR -> 두 번 뒤집으면 원래대로 돌아옵니다. 즉 의미가 없습니다. )

문제의 티어가 골드 V로 분류되어 있고 시간제한도 1초입니다.

실버 하위 문제였으면 그냥 방금처럼 정직하게 풀었으면 풀렸는데 이 문제는 조금 더 생각해야 풀립니다.

 

이 문제는 배열의 크기 n이 우선 최대 100000개로 주어집니다.

물론 RR 같은 명령어는 제거했지만

 

문제의 입력을

RDRDRDRDRDRDRD...로 준다고 생각해봅시다.

R이 10번만 나와도 벌써 뒤집는 과정에서 100만 번 반복하게 되고 시간제한 1초에 맞출 수 없습니다.

 

이걸 어떻게 해결해야 할까요?

 

안 뒤집으면 됩니다.

 

간단하죠? 안 뒤집고 어떻게 요소를 뽑냐고 하면.... 뒤집는 명령어가 들어온 후 D 명령어가 들어오면

뒤에 있는 걸 빼주면 됩니다.

조금만 생각해보세요.

 

뒤집어진 상태를 저장하는 변수를 1로 초기화하고 만들고

R 명령어가 들어올 때마다 -1만 곱해서 저장해줍니다. (처음 뒤집으면 -1, 또 뒤집으면 -1 곱해서 다시 1)

 

그리고 D 명령어가 들어오면 뒤집어진 상태가 -1이라면 리스트의 맨뒤에서 빼줍니다.

뒤집었으면 맨뒤의 요소가 맨 앞으로 오고 그걸 뽑아야 하기 때문입니다.

 

만약에 아니라면 (뒤집어진 상태가 1이라면) 리스트의 맨 앞에서 그냥 빼주면 됩니다.

 

 

그리고 출력할 때도 뒤집어진 상태가 -1이라면 거꿀로 출력하고 아니라면 그대로 출력해주시면 되겠습니다.

 

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

repeat = int(input().rstrip())
for i in range(repeat):
    reverse_flag = 1 #뒤집혀 있지 않음.
    command = input().rstrip()
    length = int(input().rstrip())
    deck = deque(input().rstrip().split(","))
    
    #양쪽 [, ] 뽑아서 제거해준다. -> deck은 양쪽 pop&append 의 시간복잡도가 O(1)
    
    if len(deck) == 1: #한개 들어온경우
        one = deck.pop()
        if one == "[]":
            pass
        else:
            deck.append(one.replace("[", "").replace("]", ""))
    else:
        left = deck.popleft()
        right = deck.pop()
        deck.appendleft(left.replace("[", ""))
        deck.append(right.replace("]", ""))
    
    error = False
    command = command.replace("RR", "") #연속뒤집기는 의미가 없으므로 제거함.
    for element in command:
        if element == "R":
            reverse_flag = reverse_flag * -1 #뒤집힘 상태에 -1을 곱해준다. 
        elif element == "D":
            if not deck: #비었으면
                error = True
                break
            else:
                if reverse_flag == -1: #뒤집혀 있으면
                    deck.pop() #맨 오른쪽걸 빼준다. (뒤집힌 상태서 빼는것 이므로.)
                else: #안뒤집혀 있으면
                    deck.popleft() #앞에걸 그냥 빼주면 된다.
    if(error == True):
        print("error")
    else:
        if reverse_flag == -1: #뒤집혀 있으면 거꾸로 출력해준다.
            deck.reverse() #뒤집는다.
            print(str(list(deck)).replace(" ", "").replace("'", ""))
        else:
            print(str(list(deck)).replace(" ", "").replace("'", ""))

출력에서 오류가 나서 출력하는 부분도 for문이 아니라 리스트를 문자열로 바꾼 뒤

replace 해서 필요 없는 부분을 지워, 문제의 출력과 동일하게 맞췄습니다.

 

풀이에 이해가 안 가신다면 언제든지 댓글 주세요. 감사합니다.