[프로그래머스/JAVA] 대충 만든 자판

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

 

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

---

📌 문제 요약

 

📄 문제 상황

옛날 휴대폰 자판은 한 키에 여러 문자가 할당되어 있었던 것과 비슷한 상황이다.

 

예를 들어 1번 키에 "A", "B", "C" 순으로 들어 있다면,

1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 C 이런 식으로 동작한다.

 

그런데 이 문제의 자판은 옛날 휴대폰 보다 훨씬 자유분방(?)하다.

• 키의 개수는 1~100개 사이이고
• 각 키에 어떤 문자가 들어갈지는 무작위다.
• 게다가 중복도 허용해서, 같은 문자가 여러 키에 있거나, 한 키에 여러 번 있을 수도 있다.
• 심지어 어떤 문자는 아예 없을 수도 있다. (입력 불가능)

 

🎯 목표

우리의 목표는 주어진 자판(keyamp)을 이용해서 타겟 문자열(targets)을 작성할 때

최소 몇 번 키를 눌러야 하는지를 구하는 것이다.

(만약 만들 수 없는 문자열이라면 -1을 반환하면 된다.)

 

 

🔎 예시

keymap = ["ABACD", "BCEFD"]
targets = ["ABCD"]

 

위와 같은 예시가 주어졌을 때, "ABCD"를 입력하는 상황을 알아보자.

편의상 "ABACD"를 1번 키맵, "BCEFD"를 2번 키맵이라고 부르기로 하자.

• 1번 키맵에 A가 존재하는데, 키를 1번 눌러서 A를 만들 수도 있고, 3번 눌러서 A를 만들 수도 있다.
• 최소 횟수는 1번 눌러서 A를 만드는 것이므로, 1번 키맵을 1회 누른다.
• B는 1번 키맵과 2번 키맵에 모두 존재한다.
• 그러나 1번 키맵에서는 2회 눌러야 하지만, 2번 키맵에서는 1회만 누르면 된다.
• 따라서 2번 키맵을 1회 눌러서 B를 만든다.
• C도 1번 키맵과 2번 키맵에 모두 존재하는데, 2번 키맵이 누르는 횟수가 더 적다.
• 따라서 2번 키맵을 2회 눌러서 C를 만든다.
• D도 1번 키맵과 2번 키맵에 모두 존재하는데, 둘 다 5회 눌러야 D를 입력할 수 있다.
• 따라서 아무거나 5회 눌러서 D를 만든다.

👉🏻 즉, "ABCD"를 만들기 위해서는 키를 최소 1 + 1 + 2 + 5 = 9회 눌러야 한다.

 

---

💡 아이디어

🧠 핵심 전략

1️⃣ 전처리를 위한 맵 만들기

Map<Character, Integer> map = new HashMap<>();
for (String key : keymap) {
  for (int i = 0; i < key.length(); i++) {
    char c = key.charAt(i);
    int press = i + 1; // i는 0-based, 누른 횟수는 1부터 카운트 하므로 +1 해주기
    
    // 기존 값과 새 후보 중에서 더 작은 값을 저장하기
    map.put(c, Math.min(map.getOrDefault(c, Integer.MAX_VALUE), press));
  }
}

 

같은 문자가 여러 키 & 여러 위치에 있어도 가장 작은 누름 횟수만 저장하기 위해서 위와 같이 설계하였다.

 

 

2️⃣ 타겟별 합산하기

for (int i = 0; i < targets.length; i++) {
  String t = targets[i];
  int sum = 0;       // 이 타겟의 총 누름 수 합계
  boolean ok = true; // 만들 수 있는지 여부 (중간에 불가능하면 false로 바꿔주기)

  for (int j = 0; j < t.length(); j++) { // 타겟의 문자를 왼쪽부터 하나씩 살펴보기
    char c = t.charAt(j);                // 현재 문자
    Integer p = map.get(c);              // map에서 최소 누름 수 찾기
    
    // 어떤 키에도 없음 → 불가능
    if (p == null) {
    	ok = false;
        break;
    }
    
    sum += p;
  }
  
  answer[i] = ok ? sum : -1; // 만들 수 있으면 합계를, 없으면 -1을 저장
}

• sum: 현재 타겟 하나에 대한 합계로, 매 타겟마다 0으로 초기화해줘야 한다.
• ok: 이 타겟을 만들 수 있는가를 표시하는 플래그이다.
        하나라도 만들 수 없는 문자가 나오면, 바로 false로 바꿔줘야 한다.
• answer[ ]: i번째 타겟의 결과를 넣어준다.

 

---

👩🏻‍💻 최종 코드

import java.util.*;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        
        int answer[] = new int[targets.length];
        
        Map<Character, Integer> map = new HashMap();
        for(String key : keymap){
            for(int i = 0; i < key.length(); i++){
                char c = key.charAt(i);
                int press = i + 1;
                map.put(c, Math.min(map.getOrDefault(c, Integer.MAX_VALUE), press));
            }
        }
        
        for(int i = 0; i < targets.length; i++){
            String t = targets[i];
            int sum = 0;
            boolean ok = true;
            
            for(int j = 0; j < t.length(); j++){
                char c = t.charAt(j);
                Integer p = map.get(c);
                
                if(p == null){
                    ok = false;
                    break;
                }
                
                sum+= p;
            }
            
            answer[i] = ok ? sum : -1;
        }
    
        return answer;
    }
}

 

---

🕑 시간 복잡도

1️⃣ 전처리 과정

for (String key : keymap) {
  for (int i = 0; i < key.length(); i++) {
    ...
  }
}

 

모든 문자들을 정확히 한 번씩 스캔해야 하므로 시간 복잡도는 O(N)이다.

(이때, N은 모든 키맵에 있는 각 문자열 길이의 합이다.)

 

 

2️⃣ 타겟별 합산

for (int i = 0; i < targets.length; i++) {
  for (int j = 0; j < t.length(); j++) {
    ...
  }
}

 

각 타겟의 모든 문자를 한 번씩 조회해야 하므로 시간 복잡도는 O(M)이다.

(이때, M은 타겟에 있는 각 문자열 길이의 합이다.)

 

 

👉🏻 따라서 최종 시간 복잡도는 O(N + M)이다.