백준 1796 신기한 키보드 (Java)

1. 문제 링크

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

1796번: 신기한 키보드

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 문자별로 ArrayList를 만들어 해당 문자 별로 어떤 문자가 들어왔는지 추가했다.
2. 처음 시작은 a이고, 위치는 0, 움직인 횟수는 0으로 dfs를 했다.
3. 마지막 알파벳인 z까지 출력했다면 return 한다.
4. 현재 알파벳의 개수가 0이라면 다음으로 넘어간다.
5. 현재 알파벳이 있다면 첫번째 자리와 마지막 자리를 구한다. 5-1. 처음과 끝이 같은 위치라면 그 사이 차를 더한 후 그 위치로 옮겨서 dfs한다. 5-2. 현 위치가 해당 문자의 사이에 있는 경우라면 어느쪽으로 가는 것이 최소가 나올지 모르니 양쪽으로 dfs를 한다. 5-3. 현 위치에서 해당 문자가 전부 오른쪽이거나 전부 왼쪽인 경우 그 길이만큼 더하고 dfs한다.
6. 최소값을 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;

public class Main {
	static int result=Integer.MAX_VALUE, len;
	static ArrayList<Integer>[] list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		len = str.length();
		
		list = new ArrayList[26]; //문자마다 위치를 추가할 list 배열
		for(int i=0;i<26;i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=0;i<len;i++) {
			char now = str.charAt(i);
			list[now-'a'].add(i); //위치를 추가
		}
		
		dfs(0, 0, 0);

		System.out.println(result+len);

	}

	private static void dfs(int alpha, int idx, int move) {
		if(alpha == 26) {
			result = Math.min(result, move);
			return;
		}
		
		if(list[alpha].size()==0) { //문자가 없으면 다음으로
			dfs(alpha+1, idx, move);
		}
		else {
			int first = list[alpha].get(0);
			int last = list[alpha].get(list[alpha].size()-1);
			
			if(first == last) { //하나 들어 있는 경우
				move += Math.abs(idx - first);
				idx = first; //현 위치 옮기기
				dfs(alpha+1, idx, move);
			}
			else {
				int num1 = Math.abs(idx-first);
				int num2 = Math.abs(idx-last);
				
				if(idx>first && idx<last) { //idx가 둘 사이에 있을 때
					int temp = move+num1*2+num2;
					dfs(alpha+1, last, temp);
					
					temp = move+num1+num2*2;
					dfs(alpha+1, first, temp);
				}
				else {
					if(num1<num2) { //차이가 더 많이 나는 만큼 이동
						move+=num2; 
						idx = last;
					}
					else {
						move+=num1;
						idx = first;
					}
					dfs(alpha+1, idx, move);
				}
			}
		}
	}
}