BOJ 9019 DSLR java 자바

BOJ 9019 DSLR java 자바

 

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

9019번: DSLR

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			solve(A, B);
		} // t
	
	} // main
	
	static class Info {
		int A;
		String orders;
		public Info(int a, String orders) {
			A = a;
			this.orders = orders;
		}
	};
	
	static void solve(int A, int B) {
		boolean[] visited = new boolean[10000];
		Queue<Info> queue = new LinkedList<>();
		queue.offer(new Info(A, ""));
		visited[A] = true;
		
		while(!queue.isEmpty()) {
			Info p = queue.poll();

			// D
			if(p.A != 0) {
				int num = (p.A*2) % 10000;
				if(!visited[num]) {
					if(num == B) {
						System.out.println(p.orders+"D");
						return;
					}
					visited[num] = true;
					queue.offer(new Info(num, p.orders+"D"));
				}
			}
			
			// S
			{
				int num = p.A == 0? 9999 : p.A-1;
				if(!visited[num]) {
					if(num == B) {
						System.out.println(p.orders+"S");
						return;
					}
					visited[num] = true;
					queue.offer(new Info(num, p.orders+"S"));
				}
			}
			
			// L
			{
				int num = (p.A % 1000) * 10 + (p.A / 1000);
				if(!visited[num]) {
					if(num == B) {
						System.out.println(p.orders+"L");
						return;
					}
					visited[num] = true;
					queue.offer(new Info(num, p.orders+"L"));
				}
			}
			
			// R
			{
				int num = (p.A % 10) * 1000 + p.A / 10;
				if(!visited[num]) {
					if(num == B) {
						System.out.println(p.orders+"R");
						return;
					}
					visited[num] = true;
					queue.offer(new Info(num, p.orders+"R"));
				}
			}
			
		}
		
	} // solve
	
}

 

 

풀고 나니 별 거 아닌데 두 시간이나 걸렸다

 

처음에 메모리 초과가 나서

1 ~ 9999 까지 visited 배열로 방문체크를 했다.

 

그 다음엔 시간 초과가 나서

String 을 자꾸 substring 하거나 charAt 하는 등 문자열 조작이 많아 그런 걸로 예상했다.

123 이면 0123 이런식으로 표기가 필요한 줄 알고 삽질했다 ㅜ,ㅜ

하지만 정수연산으로만 가능해서 정수연산으로 바꿨다.

 

L/R 연산은 간단한 mod 와 divide 로 가능했다

 

L 은 a 를 1000 으로 나눈 값(맨 앞 자)  +  a mod 1000(뒤 세글자) * 10

해서 앞글자를 뒤로 넘기고

 

R은 a mod 10 에 * 1000 해서 맨 뒷 자를 앞자로 바꾸고 + a / 10