[9019] DSLR
문제 분석
네 개의 명령어 D, S, L, R 을 활용하여 주어진 숫자 를 target 숫자 로 바꿀 때 최소 명령어를 출력하는 문제.
정답이 여러개인 경우 아무거나 출력하면 된다.
풀이 과정
네 개의 명령어는 다음과 같은 코드로 바꿀 수 있다.
D : n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다.
그 결과 값(2n mod 10000)을 레지스터에 저장한다.
return (number * 2) % 10_000;S : n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다.
n이 0 이라면 9999 가 대신 레지스터에 저장된다.
return number == 0 ? 9999 : number - 1;L : n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.
이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
return ((number % 1000) * 10) + (number / 1000);R : n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다.
이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
return ((number % 10) * 1000) + (number / 10);위의 핵심 로직을 만들어 놓고, 필요한 재료들을 준비하자.
🎯 방문 체크
먼저 시간 복잡도의 효율을 높이기 위해 재탐색을 하지 않아야 한다.
탐색 여부를 체크하는 변수를 하나 만든다.
주어지는 숫자는 0 이상 10,000 미만이다.
boolean[] visited = new boolean[10_001];🎯 핵심 로직
예제를 기준으로 1234 를 시작으로 3412 를 찾아야 한다면
시작 명령어는 "" 빈 문자열로 설정한다.
명령어는 각각마다 4가지의 경우의 수 로 뻗어나간다.
첫 번째는 하나의 명령어로 결과값을 찾아오는 것.
1번째 경우의 수 ) `"D"`, `"S"`, `"L"`, `"R"`
1번째 경우의 수의 결과값을 담아야한다.두 번째는 이전 명령어들 * 4가지의 경우의 수가 된다.
2번째 경우의 수 ) `"DD"`, `"DS"`, `"DL"`, `"DR"`, `"SD"`, `"SS"`, `"SL"`, `"SR"`......
2번째 경우의 수의 결과값을 담아야한다.세 번째도 마찬가지로 이전 명령어들 * 4가지의 경우의 수 가 된다.
이 로직에 알맞는 Queue 자료 구조를 활용하여 구현한다.
해당 자료 구조에 담을 타입은
int number 와 명령어 String result 를 가지고 있는 class DSLR 를 만들었다.
int number 는 명령어로 바뀐 숫자를 담는다.
String result 는 명령어를 담는다.
빈 문자열 을 탐색 시작값으로 한다.
start 는 입력으로 주어지는 숫자 A 다.
...
Queue<DSLR> queue = new LinkedList<>();
queue.add(new DSLR("", start));
...
class DSLR {
String result;
int number;
public DSLR(String result, int number) {
this.result = result;
this.number = number;
}
}나의 생각
class 를 만들어 algorithm 에 접근하는 방식이 복잡한 로직을 잘 나눌 수 있게 해주었다.
각각의 핵심 로직을 먼저 분리한 후 필요에 따라 class 를 새로 정의한다면
얽히고설켜있는 문제들을 좀 더 수월하게 접근할 수 있을 것 같다.
코드
package baekjooncompletion;
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 BaekJoon9019 {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int inputSize = Integer.parseInt(br.readLine());
for (int i = 0; i < inputSize; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
Queue<DSLR> queue = new LinkedList<>();
queue.add(new DSLR("", start));
boolean[] visited = new boolean[10_001];
w:
while (!queue.isEmpty()) {
int size = queue.size();
for (int j = 0; j < size; j++) {
DSLR dslr = queue.poll();
int number = dslr.number;
String result = dslr.result;
if (number == target) {
System.out.println(result);
break w;
}
int d = D(number);
if (!visited[d]) {
visited[d] = true;
queue.add(new DSLR(result + "D", d));
}
int s = S(number);
if (!visited[s]) {
visited[s] = true;
queue.add(new DSLR(result + "S", s));
}
int l = L(number);
if (!visited[l]) {
visited[l] = true;
queue.add(new DSLR(result + "L", l));
}
int r = R(number);
if (!visited[r]) {
visited[r] = true;
queue.add(new DSLR(result + "R", r));
}
}
}
}
}
private static int D(int number) {
//D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
return (number * 2) % 10_000;
}
private static int S(int number) {
//S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
return number == 0 ? 9999 : number - 1;
}
private static int L(int number) {
//L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
return ((number % 1000) * 10) + (number / 1000);
}
private static int R(int number) {
//R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
return ((number % 10) * 1000) + (number / 10);
}
}
class DSLR {
String result;
int number;
public DSLR(String result, int number) {
this.result = result;
this.number = number;
}
}
