[Baekjoon] 5430번: AC


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

 

5430번: AC

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

www.acmicpc.net

 

문제 설명

새로운 언어 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 해서 필요 없는 부분을 지워, 문제의 출력과 동일하게 맞췄습니다.

 

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

COMMENT WRITE