백준 20437번 : 문자열 게임 2 [자바]

 

 

 

 

🧫 문제 분석

✔️ 출처

문자열 게임 2 골드 5

 

📖 문제

 

주어진 문자열의 알파벳의 위치 처리 문제다. 

 

처음에는 투포인터로 하면 되겠나 싶었는데 말이 안되는 반례가 너무많이 생각나서 이 방법은 버리고,

 

각 알파벳의 ASCII 코드에서 'a'의 ASCII 코드를 빼서 0~25 범위의 인덱스로 변환한 후,

배열(ArrayList<>[] list)의 해당 인덱스에 현재 문자열에서 해당 알파벳이 등장한 위치(인덱스)를 저장했다.

 

그리고 각 알파벳이 k개 이상이면

k개씩 묶어서 거리를 구한 후 max, min 값을 갱신했다.

 

예제를 예시로

w = "abaaaba" 

k = 3

 

일때

list[0] = [0, 2, 3, 4, 6];  // 0 = 'a'알파벳 - 'a' 로 얻은  a알파벳의 인덱스 
list[1] = [1, 5]              // 1 = 알파벳 b의 인덱스

 

k = 3이므로 

[0, 2, 3, 4, 6] // 문자열 w에 있는 알파벳 a의 각 위치(인덱스)
 0  1  2  3  4  // 현재 리스트에서의 인덱스
 
 list[0 + k(3) - 1] - list[0] // -1을 해주는 이유는 k개로 묶을 때 자기자신 위치 + k이므로 k+1까지 묶게 되기때문이다.
 list[1 + k(3) - 1] - list[1]
 list[2 + k(3) - 1] - list[2]
 
 // 이 값들 중 max , min 갱신

 

b의 경우 list[1].size() < k 이므로 고려하지 않는다.

 

 

---

🔅 문제 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T--> 0) {
            char[] w = br.readLine().toCharArray();
            int k = Integer.parseInt(br.readLine());
            ArrayList<Integer>[] list = new ArrayList[26];

            for (int i = 0; i < 26; i++) {
                list[i] = new ArrayList<>();
            }

            // 각 문자에 대한 인덱스 저장
            for (int i = 0; i < w.length; i++) {
                list[w[i] - 'a'].add(i);
            }

            int max = -1;
            int min = Integer.MAX_VALUE;
            // 3. 가장 짧은거는 중앙에서부터 투포인터 탐색
            // 4. 가장 긴 거는 양 끝에서부터 탐색
            for (int i = 0; i < list.length; i++) {
                if (list[i].size() < k) continue; // k개 미만이면 조건에 만족하지 않음

                // 각 문자의 k개씩 묶어서 거리를 재고, min, max값 탐색
                for (int j = 0; j < list[i].size() - k + 1; j++) {
                    int length = list[i].get(j + k - 1) - list[i].get(j) + 1;
                    max = Math.max(max, length);
                    min = Math.min(min, length);
                }
            }
            
            // k개를 포함하는 문자가 없다면, 조건 불충족으로 -1
            if (max == -1 && min == Integer.MAX_VALUE) {
                sb.append("-1\n");
            } else { 
                sb.append(min).append(" ").append(max).append("\n");
            }
        }

        bw.write(sb.toString() + "");
        bw.flush();
        bw.close();
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  잘 풀었다. ㅎ