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

[문제 링크]

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

---

문제 설명

알파벳 소문자로 이루어진 문자열 w와 양의 정수 k가 주어질 때, 아래 두 개에 해당되는 문자열의 길이를 구한다.

- 어떤 문자를 정확히 k개 포함하는 가장 짧은 문자열의 길이

- 어떤 문자를 정확히 k개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 문자열의 길이

 

만족하는 문자열이 없을 경우 -1 출력

 

 

 

 

 

 

문제 풀이

• 반복문을 사용해서 어떤 문자 k개를 포함하는 가장 짧은 문자열과 가장 긴 문자열의 길이를 구한다.
• 처음에는 모든 경우의 수를 탐색하도록 구현했더니 시간초과가 떴다.
• 그래서 아래와 같이 알파벳별로 개수를 세서 탐색을 실행하는 조건을 추가했다.

추가한 부분

1. 입력받은 문자열 w에서 각 알파벳별로 개수를 세서 배열에 따로 저장한다.

//문자열에서 알파벳별로 개수를 세서 저장
int[] alphaCnt = new int[26];
for (int i = 0; i < w.length(); i++) {
    alphaCnt[w.charAt(i) - 'a']++;
}

 

2. 해당 알파벳의 개수가 k보다 작으면, 탐색하지 않고 다음 문자로 넘어간다.

if (alphaCnt[w.charAt(i) - 'a'] < k)    continue;

 

 

 

전체코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while (t > 0) {
            String w = br.readLine();
            int k = Integer.parseInt(br.readLine());

            //k가 1인 경우는 따로 처리
            if (k == 1) {
                sb.append(1 + " " + 1 + " \n");
                t--;
                continue;
            }

            //문자열에서 알파벳별로 개수를 세서 저장
            int[] alphaCnt = new int[26];
            for (int i = 0; i < w.length(); i++) {
                alphaCnt[w.charAt(i) - 'a']++;
            }

            int shortestStr = Integer.MAX_VALUE;    //특정문자 k개 포함하는 가장 짦은 문자열의 길이
            int longestStr = Integer.MIN_VALUE;     //특정문자 k개 포함 + 맨앞,뒤문자가 같은 가장 긴 문자열의 길이


            for (int i = 0; i < w.length() - 1; i++) {
                if (alphaCnt[w.charAt(i) - 'a'] < k)    continue;   //해당 알파벳의 개수가 k보다 작으면 탐색하지 않는다.

                int cnt = 1;
                for (int j = i + 1; j < w.length(); j++) {
                    if (w.charAt(i) == w.charAt(j)) {
                        cnt++;
                        if (cnt == k) {
                            shortestStr = Math.min(shortestStr, j - i + 1);
                            longestStr = Math.max(longestStr, j - i + 1);
                            break;
                        }
                    }
                }
            }

            if (shortestStr == Integer.MAX_VALUE || longestStr == Integer.MIN_VALUE) {
                sb.append(-1 + "\n");
            } else {
                sb.append(shortestStr + " " + longestStr + "\n");
            }
            t--;
        }
        System.out.println(sb);
    }
}