[ Baekjoon - 11/15 ] - 5430번: AC

문제 링크 : https://www.acmicpc.net/problem/5430

5430번: AC

 

소요 시간 : 1시간 반

AC 

            

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	93352	20647	14575	19.860%

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

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

예제 입력 1

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1

[2,1]
error
[1,2,3,5,8]
error

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

1 >   TC (테케, TC : [0, 100]) 

2 >   p (수행할 함수, p의 길이 : [1, 10만]) 

3 >   n (배열에 들어있는 수의 개수, n : [0, 10만])

4 >   [x1, x2, ..., xn] (배열에 들어있는 정수, xi : [1, 100])

5 >   // TC만큼 2~4줄 반복

출력 > p연산을 전부 끝냈을때 남은 배열

※ p 길이의 합 + n : [0, 70만]

 

 

▶ 문제

새로운 언어 AC에는 두 가지의 함수가 있는데, 각각 R(뒤집기)와 D(버리기)가 있음

R은 배열의 수들 순서를 뒤집고, D는 배열의 첫번째 수를 버림. 못버리면 에러.

주어지는 형태는 "RDD"처럼 공백없이 이어진 R과 D의 조합.

모든 연산을 수행했을때 얻을 수 있는 최종 결과를 출력하는 문제

 

 

▶ 시간, 메모리 제한 : 1초, 256MB

 

2.  문제를 익숙한 용어로 재정의와 추상화

주어진 함수 p대로 따라가면 되는 문제라 이해가 어렵지 않아서 생략

 

3.  문제 해결 방안

1st 접근 ) R을 수행할 때, 실제로 뒤집지 말고 인덱스를 바꾸자

R연산은 뒤집는 연산 => 뒤집지말고 현재 인덱스에 대칭되는 반대의 아이를 제거하자

즉, X1번부터 Xn까지 있는 배열에서 Xi가 대칭되는 구역은 Xn-i+1

반례)

뒤집기는 저렇게 수행가능할지라도, 문제는 D연산임

R연산은 위 방법으로 실제로 뒤집지 않고 뒤집는 효과를 낼지라도 위 방식처럼 쓴다는 것은 배열이나 리스트로 수를 저장하겠다는 말과 같은데, 그랬을 때 첫번째 수를 삭제하는 연산은 O(1)이 아니라 O(N)임. 한칸씩 앞으로 당겨오므로!

 

2nd 접근 ) 덱을 이용

R은 인덱스만 바꾸는 연산이고, 실질적으로 시간복잡도에 영향을 줄 수 있는 연산은 D임

D는 가장 첫번째 아이만 빼오는 연산인데, R로 인해 가장 첫번째이거나 가장 마지막 아이일 수 있음

즉, 덱이라는 자료구조를 가져오게 되면 가장 첫 값, 가장 끝 값 삭제연산이 둘다 O(1)이므로 적절한 결과를 얻을 수 있게 된다.

 

4.  위 계획 검증

덱의 특징을 알고있다면 검증은 필요없음. 나머지는 조건만 잘 맞춰주면 된다.

※ 질문글에서 위 문제에서 일어날 수 있는 경우를 잘 정리한 글이 있어서 가져왔다.

https://www.acmicpc.net/board/view/25456

글 읽기 - ★☆★☆★ [필독] AC FAQ ★☆★☆★

혹여나 애매한 내용이 있다면 위 링크를 참고하길 바란다.

 

5.  코드 작성

▶ Java 11 ( 107480KB, 864ms)

import java.io.*;
import java.util.*;

public class Main {
    static int T,N;
    static String P,tmp;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < T; tc++) {
            P = br.readLine();
            N = Integer.parseInt(br.readLine());
            tmp = br.readLine();
            tmp = tmp.substring(1, tmp.length()-1);
            String[] arr = tmp.split(",");

            Deque<Integer> dq = new LinkedList<Integer>();
            for (int n = 0; n < N ; n++) {
                dq.add(Integer.parseInt(arr[n]));
            }

            boolean dir = true;
            boolean flag = false;
            for (int p = 0; p < P.length(); p++) {
                if(P.charAt(p)=='R') {
                    dir=!dir;
                }else {
                    if(dq.isEmpty()) {
                        flag=true;
                        break;
                    }
                    if(dir) {
                        dq.pollFirst();
                    }else {
                        dq.pollLast();
                    }
                }
            }
            if(flag) {
                sb.append("error\n");
                continue;
            }
            sb.append("[");
            if(dir) {
                while(dq.size()>1) {
                    sb.append(dq.pollFirst()).append(",");
                }
            }else {
                while(dq.size()>1) {
                    sb.append(dq.pollLast()).append(",");
                }
            }
            if(dq.size()!=0) {
                sb.append(dq.poll());
            }
            sb.append("]"+"\n");
        }
        System.out.println(sb);
    }
}

 

▶ Python 3 (44616KB, 188ms)

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    T = int(input())
    for t in range(T):
        P = input().rstrip()
        N = int(input())
        arr = input().rstrip()[1:-1].split(",")
        dq = deque(arr)

        order = True
        errFlag = False
        if N == 0:
            dq = []

        for p in P:
            if p == 'R':
                order = not order
            elif p == 'D':
                if len(dq) < 1:
                    errFlag = True
                    print("error")
                    break
                else:
                    if order:
                        dq.popleft()
                    else:
                        dq.pop()
        if not errFlag:
            if order:
                print("[" + ",".join(dq) + "]")
            else:
                dq.reverse()
                print("[" + ",".join(dq) + "]")

if __name__ == '__main__':
    solution()

 

6. 결과

틀렸습니다 둘다 같은 조건을 수정하지 않아서 생긴 문제이다.

빈 리스트라고 무조건 error가 아니지만, 이를 고려해주지 않았다.