[백준] 9019번 : DSLR - 자바[Java]

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

9019번: DSLR

 

 

풀이

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 구해야 하므로, BFS를 사용한다.

숫자의 중복 여부를 체크하기 위해 Map을 사용하고, 각 숫자마다 명령어 나열을 저장해야 하므로 Map에 (숫자, 명령어 나열)을 저장한다.

큐에는 숫자를 저장한다.

로직 (시간초과)

1. BFS를 수행할 dslr함수에서 int형 숫자를 저장하는 큐,  (숫자, 명령어 나열)을 저장하는 HashMap<Integer, String>을 선언한다.

2. 큐에는 시작 숫자(a), map에는 (a, "")를 추가한다.

3. 큐가 빈 상태가 될 때까지 다음 과정을 반복한다.

• 큐에서 숫자 한 개를 꺼낸다.
• 그 숫자가 b와 같다면 map.get(b)를 통해 명령어 나열을 리턴하고 dslr 함수를 종료한다.
• D, S, L, R 연산을 통해 나온 숫자를 구하고 각 숫자가 map에 key로 존재하지 않을 경우에만 map에 추가한다.

 

주의할 점

숫자가 4자리수가 아닐 때의 L연산과 R 연산은 다음과 같다.

L

1 -> 10

123 -> 1230

R

1 -> 1000

123 -> 3012

 

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

public class Main {
	

    static public String dslr(int a, int b) {

    	Queue<Integer> q = new LinkedList<>();
    	HashMap<Integer, String> map = new HashMap<>();
    	q.add(a);
    	map.put(a, "");
    	
    	while(!q.isEmpty()) {
    		int tmp = q.poll();
    		
    		
    		if (tmp == b) {
    			return map.get(tmp);
    		}
    		
    		int num = tmp;
    		StringBuilder sb = new StringBuilder();
        	
        	// D
			num = 2 * num % 10000;
			
			if (!map.containsKey(num)) {
				q.add(num);
				sb = new StringBuilder(map.get(tmp));
				map.put(num, sb.append("D").toString());
			}
			
			// S
			num = tmp;
			if (num == 0)
				num = 9999;
			num = num - 1;
			
			if (!map.containsKey(num)) {
				q.add(num);
				sb = new StringBuilder(map.get(tmp));
				map.put(num, sb.append("S").toString());
			}
			
			// L
			num = tmp;
			String str;
			
			sb = new StringBuilder();
			
			if (tmp >= 1000) {
				str = Integer.toString(tmp);
				sb.append(str.substring(1));
				sb.append(str.charAt(0));
				num = Integer.parseInt(sb.toString());
			}
			else
				num *= 10;
			
			if (!map.containsKey(num)) {
				q.add(num);
				sb = new StringBuilder(map.get(tmp));
				map.put(num, sb.append("L").toString());
			}
			
			// R
			num = tmp;
			sb = new StringBuilder();
			if (tmp < 1000) { // tmp가 3자릿수 이하라면 앞에 0이 있어야 한다.
				str = Integer.toString(tmp);
				for (int i = 0; i < 4 - str.length(); i++)
					sb.append("0");
			}
			str = sb.append(tmp).toString();
			
			sb = new StringBuilder();
			sb.append(str.substring(str.length()-1));
			sb.append(str.substring(0, str.length()-1));
			
			num = Integer.parseInt(sb.toString());
			
			if (!map.containsKey(num)) {
				q.add(num);
				sb = new StringBuilder(map.get(tmp));
				map.put(num, sb.append("R").toString());
			}
			
    	}
    	
    	return "";

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
        while (t-- > 0) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	String answer = dslr(a, b);
        	
        	bw.write(answer+'\n');
        }
        
        bw.flush();
        bw.close();
        br.close();

    }
}

위 풀이는 7%에서 시간 초과가 떴다.

L과 R연산을 StringBuilder를 사용하여 복잡하게 구현한 것이 시간을 오래 걸리게 한 것 같다.

또한 Map을 사용하여 중복 여부를 체크하지 않고, boolean 배열을 사용하여 중복 여부를 체크하고, String 배열을 사용하여 명령어 나열을 따로 저장하는 것이 시간을 더 단축시킨다.

 

---

수정한 점

1. L와 R 연산을 StringBuilder를 사용하여 복잡하게 구현한 것을 간단한 로직으로 수정

2. HashMap 대신 중복 여부를 체크하는 boolean 배열과 명령어 나열을 저장하는 String 배열 사용

3. "S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다." S 연산에 대해 잘못 이해하고 있었다. 올바른 S 연산은 다음과 같다.

// S
num = tmp - 1;
if (tmp == 0) num = 9999;

 

로직

1. BFS를 수행할 dslr함수에서 int형 숫자를 저장하는 큐,  중복 여부를 체크하는 boolean 타입 visited 배열과 명령어 나열을 저장하는 String 타입 ans 배열을 선언한다.

2. 큐에는 시작 숫자(a)를 추가하고, visited[a] = true, ans[a] = "" 를 수행한다.

3. 큐가 빈 상태가 될 때까지 다음 과정을 반복한다.

• 큐에서 숫자 한 개를 꺼낸다.
• 그 숫자가 b와 같다면 ans[tmp]를 리턴하고 dslr 함수를 종료한다.
• D, S, L, R 연산을 통해 나온 숫자를 구하고 각 숫자에 대해 아직 방문하지 않았을 경우(!visited[num])에만 큐에 추가하고, visited[num] = true, ans[num] = ans[tmp] + "명령어" 를 수행한다.

 

코드

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

public class Main {
	

    static public String dslr(int a, int b) {

    	Queue<Integer> q = new LinkedList<>();
    	
    	boolean[] visited = new boolean[10001];
    	String[] ans = new String[10001];
    	
    	q.add(a);
    	visited[a] = true;
    	ans[a] = "";
    	
    	while(!q.isEmpty()) {
    		
    		int tmp = q.poll();
    		
    		if (tmp == b) {
    			return ans[tmp];
    		}
    		
    		int num;
        	
        	// D
			num = 2 * tmp % 10000;
			
			if (!visited[num]) {
				visited[num] = true;
				q.add(num);
				ans[num] = ans[tmp] + "D";
			}
			
			// S
			num = tmp - 1;
	        if(tmp == 0) num = 9999;
			
			if (!visited[num]) {
				visited[num] = true;
				q.add(num);
				ans[num] = ans[tmp] + "S";
			}
			
			// L
			num = (tmp % 1000) * 10 + tmp / 1000;
			
			if (!visited[num]) {
				visited[num] = true;
				q.add(num);
				ans[num] = ans[tmp] + "L";
			}
			
			// R
			num = tmp / 10 + (tmp % 10) * 1000;
			
			if (!visited[num]) {
				visited[num] = true;
				q.add(num);
				ans[num] = ans[tmp] + "R";
			}
			
    	}
    	
    	return "";

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
        while (t-- > 0) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	String answer = dslr(a, b);
        	
        	bw.write(answer+'\n');
        }
        
        bw.flush();
        bw.close();
        br.close();

    }
}