Baekjoon #9019 DSLR (java)

접근 방법

1. 연산 하나씩 해보며 탐색
   1. 명령어 리스트를 어떻게 기억할까? → class에 숫자와 명령어 속성을 만들까? —> 한번 탐색한 숫자를 반복해서 탐색하면서 시간초과 발생
   → 한번 탐색한 숫자는 다시 탐색할 필요 없다. 동적계획법으로 해당 숫자의 방문여부와 명령어 순서를 기록해두는 방법을 사용해서 실행횟수를 줄일 수 있다.
   1. D
      1. n*2 , > 9999 → mod
   2. S
      1. n-1, n=0 → 9999
      2. n이 0인지 여부를 먼저 판단해야한다. 안 그러면 n=0으로 들어왔을 때 -1이 리턴되면서 어레이인덱스오류가 남.
   3. L
      1. (n%1000) * 10 + n/1000
   4. R
      1. (n%10) * 1000 + n/10

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int T;
    static String answer;
    static String[] cmd = {"D", "S", "L", "R"};

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            answer = calculate(A, B);
            System.out.println(answer);
        }
    }

    private static String calculate(int a, int b) {
        Queue<Integer> numQ = new LinkedList<>();
        boolean[] visited = new boolean[10000];
        String[] command = new String[10000];
        numQ.offer(a);
        visited[a] = true;
        command[a] = "";

        while (!numQ.isEmpty()) {
            int curNum = numQ.poll();
            if (curNum == b) {
                return command[curNum];
            }

            for (int c = 0; c < 4; c++) {
                int nextNum = doCommand(curNum, cmd[c]);

                if (!visited[nextNum]) {
                    numQ.offer(nextNum);
                    visited[nextNum] = true;
                    command[nextNum] = command[curNum] + cmd[c];
                }
            }
        }
        return "";
    }

    private static int doCommand(int n, String cmd) {
        int result;
        if ("D".equals(cmd)) {
            result = cmdD(n);
        } else if ("S".equals(cmd)) {
            result = cmdS(n);
        } else if ("L".equals(cmd)) {
            result = cmdL(n);
        } else {
            result = cmdR(n);
        }
        return result;
    }

    private static int cmdR(int x) {
        x = (x % 10) * 1000 + x / 10;
        return x;
    }

    private static int cmdL(int x) {
        x = (x % 1000) * 10 + x / 1000;
        return x;
    }

    private static int cmdS(int x) {
        if (x == 0) {
            x = 9999;
        } else {
            x -= 1;
        }
        return x;
    }

    private static int cmdD(int x) {
        x *= 2;
        if (x > 9999) {
            x %= 10000;
        }
        return x;
    }
}

출처

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

9019번: DSLR