[구현] 백준 3961번 터치스크린 키보드 - JAVA

 

원래는 못 푼 문제가 아니여서 작성을 아니하려다...

푼 사람도 별로 없고, 후기도 별로 없길래 써본다.

원래 빈틈 시장 노리는 것 아니겠어? ㅎㅎ

 

Collection 구현에 관심이 있다면 풀어보는 것도 낫밷이다!

 

 

---

1. 출처

---

 

3961번: 터치스크린 키보드

 

 

 

내가 딱 100번째이다 ㅎㅎ 의미부여중 ㅎㅎ...

 

• 사용자가 어떤 단어를 입력한다.
• 컴퓨터에는 예비 단어 N가지가 있다.
• 사용자의 단어와 컴퓨터의 예비 단어 사이 거리를 구한다.
• 거리는 단어에 속해있는 각 캐릭터가 키보드 상에서 떨어져 있는 정도이다.
• 거리는 가로 + 세로 떨어져 있는 거리를 구하면 된다.

 

 

---

2. 설계

---

 

 

1. 키보드 초기화

static HashMap<Character, Loc> location = new HashMap<Character, Loc>(){{
        put('q', new Loc(0,0)); put('w', new Loc(0,1)); put('e', new Loc(0,2)); put('r', new Loc(0,3));
        put('t', new Loc(0,4)); put('y', new Loc(0,5)); put('u', new Loc(0,6)); put('i', new Loc(0,7));
        put('o', new Loc(0,8)); put('p', new Loc(0,9));
        
        put('a', new Loc(1,0)); put('s', new Loc(1,1)); put('d', new Loc(1,2)); put('f', new Loc(1,3));
        put('g', new Loc(1,4)); put('h', new Loc(1,5)); put('j', new Loc(1,6)); put('k', new Loc(1,7));
        put('l', new Loc(1,8));

        put('z', new Loc(2,0)); put('x', new Loc(2,1)); put('c', new Loc(2,2)); put('v', new Loc(2,3));
        put('b', new Loc(2,4)); put('n', new Loc(2,5)); put('m', new Loc(2,6));
}};

 

처음에는 키보드를 2중배열로 만들어주고, BFS로 4방탐색하며 큐로 넣어주며 거리를 계산하려했다. 근데 최대 1만의 길이 단어가 나오면 new를 최대 1만번을 진행해 비효율적으로 느껴졌다.

 

그런데 결국 각 단어의 캐릭터 사이 거리를 구하는 거면 HashMap으로 캐릭터와 위치를 저장하는 것이 더 효율적이겠다라는 생각을 했다.

Math.abs(사용자단어.row - 컴퓨터단어.row) + Math.abs(사용자단어.col - 컴퓨터단어.col)을 해주면 되기 때문이다.

 

 

이 때, HashMap을 초기화와 동시에 할당을 하고자 한다면, K,V 안써주면 컴파일 에러가 난다.

HashMap<Character, Loc> location = new HashMap<>() //컴파일 에러
HashMap<Character, Loc> location = new HashMap<Character, Loc>() //컴파일 ok

 

 

 

2. 거리 계산

//str1 == 유저 입력 단어
//str2 == 컴퓨터 단어
public static int Calculation(String str1, String str2){//단어 간의 거리 계산

        int len = 0;
        
        for(int i=0; i<str1.length(); i++){
            Character char1 = str1.charAt(i);
            Character char2 = str2.charAt(i);
            
            if(char1 == char2) continue;
            
            Loc userInput = location.get(char1);
            Loc computer = location.get(char2);
            len += Math.abs(computer.r - userInput.r) + Math.abs(computer.c - userInput.c);
        }

        return len;
}

 

위에서 말했던 것처럼 Math.abs(사용자단어.row - 컴퓨터단어.row) + Math.abs(사용자단어.col - 컴퓨터단어.col)을 해준다.

최종적으로 2개의 단어 사이의 거리만 반환해준다.

 

word[i] = new Distance(target, Calculation(userInput, target));

 

반환된 길이는 word 배열에 넣어준다.

 

 

3. 정렬

Arrays.sort(word, new Comparator<Distance>(){
	@Override
	public int compare(Distance o1, Distance o2){
		if(o1.dis==o2.dis){
			for(int i=0; i<o1.word.length(); i++){
				Character word1 = o1.word.charAt(i);
				Character word2 = o2.word.charAt(i);

				if(word1 == word2) continue;
                            
				return word1>word2?1:-1;
			}
		}
		return o1.dis>o2.dis?1:-1;
	}
});

 

Comparator을 이용해 word를 길이 순으로 정렬한다.

여기서 주의점은 길이가 같으면 단어 사전순으로 정렬하는 것이다.

 

 

4. 결과저장

for(int i=0; i<wordCount; i++){
	sb.append(word[i]. word).append(" ").append(word[i].dis).append("\n");
}

 

모든 테스트케이스의 정렬 결과를 StringBuilder로 저장해 시간을 단축한다.

 

 

---

3. 전체 코드

---

 

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

class Main {
    static HashMap<Character, Loc> location = new HashMap<Character, Loc>(){{
        put('q', new Loc(0,0)); put('w', new Loc(0,1)); put('e', new Loc(0,2)); put('r', new Loc(0,3));
        put('t', new Loc(0,4)); put('y', new Loc(0,5)); put('u', new Loc(0,6)); put('i', new Loc(0,7));
        put('o', new Loc(0,8)); put('p', new Loc(0,9));
        
        put('a', new Loc(1,0)); put('s', new Loc(1,1)); put('d', new Loc(1,2)); put('f', new Loc(1,3));
        put('g', new Loc(1,4)); put('h', new Loc(1,5)); put('j', new Loc(1,6)); put('k', new Loc(1,7));
        put('l', new Loc(1,8));

        put('z', new Loc(2,0)); put('x', new Loc(2,1)); put('c', new Loc(2,2)); put('v', new Loc(2,3));
        put('b', new Loc(2,4)); put('n', new Loc(2,5)); put('m', new Loc(2,6));
    }};
    
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    static String userInput;
    static Distance[] word;
    static int wordCount;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int T=1; T<=t; T++){
            String info = br.readLine();
            StringTokenizer st = new StringTokenizer(info," ");
            
            userInput = st.nextToken();
            wordCount = Integer.parseInt(st.nextToken());

            word = new Distance[wordCount];
            for(int i=0; i<wordCount; i++){
                String target = br.readLine();
                word[i] = new Distance(target, Calculation(userInput, target));
            }

            Arrays.sort(word, new Comparator<Distance>(){
                @Override
                public int compare(Distance o1, Distance o2){
                    if(o1.dis==o2.dis){
                        for(int i=0; i<o1.word.length(); i++){
                            Character word1 = o1.word.charAt(i);
                            Character word2 = o2.word.charAt(i);
                            
                            if(word1 == word2) continue;
                            
                            return word1>word2?1:-1;
                        }
                    }
                    return o1.dis>o2.dis?1:-1;
                }
            });
            
            for(int i=0; i<wordCount; i++){
                sb.append(word[i]. word).append(" ").append(word[i].dis).append("\n");
            }
            
        }//test case

        System.out.println(sb);
    }

    //char2 == 컴퓨터에 있는 단어
    //char1 == userInput
    public static int Calculation(String str1, String str2){//단어 간의 거리 계산

        int len = 0;
        
        for(int i=0; i<str1.length(); i++){
            Character char1 = str1.charAt(i);
            Character char2 = str2.charAt(i);
            
            if(char1 == char2) continue;
            
            Loc userInput = location.get(char1);
            Loc computer = location.get(char2);
            len += Math.abs(computer.r - userInput.r) + Math.abs(computer.c - userInput.c);
        }

        return len;
    }

    public static class Distance{
        String word;
        int dis;
        public Distance(String word, int dis){
            this.word = word;
            this.dis = dis;
        }
    }

    public static class Loc{
        int r;
        int c;
        public Loc(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}

 

 

BFS, DFS 같은 정형화된 알고리즘 보다도 구현에 어려움을 느끼는 요즘이다 ㅎㅎ... 화이팅!