[Java / Kotlin] 99 클럽 코딩 테스트 스터디 미들러 24일차 - 대충 만든 자판

https://school.programmers.co.kr/learn/courses/30/lessons/160586?language=kotlin

프로그래머스

[문제]

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다.
키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

 

[제한 사항]

 

[입출력 예]

 

[풀이]

특정 키보드가 있는데, 해당 키보드를 눌러야 옆 자판으로 포커스가 이동하는 것으로 생각해 주시면 됩니다.

그리고 그 누르는 카운트를 축적해서 최소 몇 번의 이동으로 targets를 구성할 수 있는지 확인하는 문제입니다.

해당 문제는 Map을 사용했습니다. 

 

코틀린 코드를 기준으로 설명하겠습니다.

답을 반환할 List와 각 Char의 가장 작은 위치 값을 저장할 Map을 선언해줍니다.

val answer = IntArray(targets.size) { -1 } // -1로 모두 초기화
val map = mutableMapOf<Char, Int>()

 

제시된 keyboard를 순회하면서 각 Char가 나타나는 가장 작은 위치 값을 저장합니다.
이때 인덱스가 아니라 위치 값이므로 +1에 주의합니다.

map에 이미 값이 존재한다면 신규 값과 기존 값 중 작은 것을 반영, 기존 값이 아예 없다면 새롭게 추가합니다.

keymap.forEach { str ->
    val arr = str.toCharArray()
    arr.forEach {
        if (map.containsKey(it)) {
            //키가 포함된 가장 가까운 위치 값 저장
            map[it] = min(map[it]!!, arr.indexOf(it) + 1)
        } else {
            map[it] = arr.indexOf(it) + 1
        }
    }
}

 

이제 타깃 목록에 들어간 각 요소의 Char 단위까지 반복문을 돌며 구성 가능한 최소 카운트를 구하면 됩니다.

만일 map에 특정 Char가 포함되어 있다면 해당 카운트를 축적.

존재하지 않는다면 구성 가능한 타깃이 아니므로 -1 상태를 유지하도록 합니다.

바로 result list에 추가하는 방법도 있겠으나 flag를 활용하여 계산 완료 처리 등록을 했습니다.

for (i in targets.indices) {
    val arr = targets[i].toCharArray()
    var count = 0
    var flag = true
    for (j in arr.indices) {
        //포함되어 있다면 계산
        if (map.containsKey(arr[j])) {
            count += map[arr[j]]!!
        } else {
            flag = false
            break
        }
    }
    if (flag) answer[i] = count
}
return answer

 

전체 코틀린 코드입니다.

class Solution {
    fun solution(keymap: Array<String>, targets: Array<String>): IntArray {
        val answer = IntArray(targets.size) { -1 } // -1로 모두 초기화

        val map = mutableMapOf<Char, Int>()

        keymap.forEach { str ->
            val arr = str.toCharArray()
            arr.forEach {
                if (map.containsKey(it)) {
                    //키가 포함된 가장 가까운 위치 값 저장
                    map[it] = min(map[it]!!, arr.indexOf(it) + 1)
                } else {
                    map[it] = arr.indexOf(it) + 1
                }
            }
        }

        for (i in targets.indices) {
            val arr = targets[i].toCharArray()
            var count = 0
            var flag = true
            for (j in arr.indices) {
                //포함되어 있다면 계산
                if (map.containsKey(arr[j])) {
                    count += map[arr[j]]!!
                } else {
                    flag = false
                    break
                }
            }
            if (flag) answer[i] = count
        }
        return answer
    }
}

 

아래는 자바 코드입니다.

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        for (int i = 0; i < targets.length; i++) {
            answer[i] = -1; // -1로 모두 초기화
        }

        Map<Character, Integer> map = new HashMap<>();

        for (String str : keymap) {
            char[] arr = str.toCharArray();
            for (char c : arr) {
                int index = str.indexOf(c) + 1;
                if (map.containsKey(c)) {
                    // 키가 포함된 가장 가까운 위치 값 저장
                    map.put(c, Math.min(map.get(c), index));
                } else {
                    map.put(c, index);
                }
            }
        }

        for (int i = 0; i < targets.length; i++) {
            char[] arr = targets[i].toCharArray();
            int count = 0;
            boolean flag = true;
            for (char c : arr) {
                // 포함되어 있다면 계산
                if (map.containsKey(c)) {
                    count += map.get(c);
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag) answer[i] = count;
        }

        return answer;
    }
}