[Problems] [Gold V] 백준 5430 AC 문제풀이

문제 설명

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

 

소요시간: 20분 + 30분

처음 풀이를 했을 때 20분 정도 소요됐고, 이후 수정하며 30분이 더 걸렸다.

 

문제에서 요구하는 핵심은

1. [1,2,3,4,5] 로 받은 문자열을 배열로 어떻게 저장할 것인가

2. RDD를 어떻게 분리하고, 판별할 것인가

3. 분리한 R, D를 각각 어떻게 기능하면 좋을까?

4. R이라면 배열의 리버스는 어떻게 구현할 것인가?

5. D라면 어떻게 가장 앞의 요소를 제거할 것인가?

출력형식에 대한 것은 크게 생각하지 않았다.

 

처음 요구사항을 파악한 다음 느낀 점은 생각보다 간단한 문제라고 생각했다.

사실 이 문제에서 가장 중요한 것은 시간제한 1초

 

풀이 과정

[1차 풀이]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());


        while (t-- > 0) {
            String commandLine = br.readLine();
            String[] commands = commandLine.split("");

            int n = Integer.parseInt(br.readLine());
            String[] str = br.readLine()
                    .replace("[", "")
                    .replace("]", "")
                    .split(",");

            int[] numbers = new int[n];
            for (int i = 0; i < n; i++) {
                numbers[i] = Integer.parseInt(str[i]);
            }


            for (String command : commands) {
                int[] tempNumbers;

                if (command.equals("D") && numbers.length == 0) {
                    System.out.println("error");
                    break;
                }

                if (command.equals("R")) {
                    tempNumbers = new int[numbers.length];
                    for (int i = numbers.length - 1, j = 0; i >= 0; i--, j++) {
                        tempNumbers[j] = numbers[i];
                    }
                    numbers = tempNumbers;
                } else if (command.equals("D")) {
                    tempNumbers = new int[numbers.length - 1];
                    System.arraycopy(numbers, 1, tempNumbers, 0, numbers.length - 1);
                    numbers = tempNumbers;
                }
            }

            if (numbers.length != 0) {
                String answer = Arrays.stream(numbers)
                        .mapToObj(String::valueOf)
                        .collect(Collectors.joining(","));
                System.out.println("[" + answer + "]");
            }
        }
    }
}

주어진 테스트케이스는 통과한 코드이다.

논리의 흐름을 그대로 구현한 코드라 성능면에서는 좋지 못한 코드이다.

코드의 결과는

시간 초과

예상하지 못한 것은 아니였다.

문제를 풀기 전에, 배열을 그대로 사용해도 될까?

1. 큐를 사용하는 것이 안정적일 거 같은데..

 

2. 문자열에서 정수만 뽑아내는데 너무 많은 함수를 불러내고 있는 것 아닐까?

3. 결과 출력 형식에서도 스트림은 과한 연산이었나?

라는 생각을 했다.

 

비교적 간단한 2, 3 번을 수정하고 다시 제출했지만

모두 시간초과였다.

 

수정 코드

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            String p = sc.next();
            int n = sc.nextInt();

            String arrStr = sc.next();
            Deque<Integer> deque = new LinkedList<>();
            for (String s : arrStr.substring(1, arrStr.length() - 1).split(","))
                if (!s.isEmpty())
                    deque.add(Integer.valueOf(s));

            System.out.println(ac(deque, p));
        }
    }

    static String ac(Deque<Integer> deque, String commands) {
        boolean reverse = false;

        for (char command : commands.toCharArray()) {
            if (command == 'R')
                reverse = !reverse;
            else {
                if (deque.isEmpty())
                    return "error";

                if (reverse)
                    deque.removeLast();
                else
                    deque.removeFirst();
            }
        }

        StringBuilder sb = new StringBuilder("[");
        while (!deque.isEmpty()) {
            sb.append(reverse ? deque.removeLast() : deque.removeFirst());
            if (!deque.isEmpty())
                sb.append(',');
        }
        sb.append(']');

        return sb.toString();
    }
}

 

느낀점

시간복잡도를 유의하며 문제풀이를 해야한다.

구현 문제의 경우 요구하는 핵심요소를 잘 파악하는 것이 우선이라고 생각한다.

이번 문제를 계기로 시간복잡도를 유념하며 문제풀이를 해야겠다.