문제
해결 방안 고민
1. 알파벳 소문자로 이루어진 문자열 W가 있음
2. 양의 정수 K
3. 어떤 문자를 정확히 K개 포함하는 가장 짧은 연속 문자열의 길이를 구함
4. 어떤 문자를 정확히 K개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구함
== 조건 2개 ==
- 어떤 문자를 정확히 K개 포함하는 가장 짧은 연속 문자열의 길이를 구함
- 어떤 문자를 정확히 K개 포함하고, 첫 번째 문자와 마지막 문자가 같아야 하며 가장 긴 연속 문자열 길이 구함
== 예시 (superaquatornado) ==
- 어떤 문자를 정확히 2개 포함하는 가장 짧은 연속 문자열의 길이를 구함
=> aqua
- 어떤 문자를 정확히 2개 포함하고, 첫 번째 문자와 마지막 문자가 같아야 하며 가장 긴 연속 문자열 길이 구함
=> raquator
Markdown
복사
•
접근법 자체를 고민하느라 시간이 많이 걸린 문제였다.
•
결국 다른 분의 풀이를 참고하여 문제를 해결하였다.
해결 방법
•
문제의 조건을 보면 다음과 같다
◦
소문자로 이루어진 문자열에서 어떤 문자를 K개 포함하는 가장 짧은, 가장 긴 문자열의 길이를 구한다.
◦
만족하는 문자열이 없다면 -1을 출력한다.
•
문제풀이
◦
입력받는 문자열의 소문자별로 개수를 센다
◦
문자열의 첫 번째 문자부터 탐색을 시작하며, 해당 문자의 개수가 K개 이하인 경우 탐색하지 않는다.
◦
뒷 문자열과 비교하여 같은 문자의 개수를 세어주고, 같은 문자의 수가 K개가 되는 순간 min, max 값을 계산한다.
•
입력받는 문자열의 알파벳 개수를 센다
◦
K개 이하인 문자는 탐색에서 제외해야 한다.
•
문자열의 첫 번째 문자부터 탐색을 하며, 해당 문자의 개수가 K개 이하인 경우 탐색하지 않는다
◦
탐색은 문자열의 길이만큼 진행된다.
•
뒷 문자열과 비교하여 같은 문자의 개수를 세어주고, 같은 문자의 수가 K개가 되는 순간 min, max값을 계산한다
◦
count가 K가 된다는 의미는 탐색을 시작하는 문자에서 부터 현재 문자까지 문제에서 요구하는 조건 만큼의 문자를 포함하는 길이가 되었으므로 min, max를 계산해 준다.
◦
min은 최소 길이이므로 K만큼 포함되는 순간 더 이상 탐색을 할 필요가 없다.
◦
max는 첫 번째와 마지막 글자가 같은 가장 긴 연속 문자열의 길이이므로 K 이상 되는 순간 탐색 할 필요가 없다.
코드
package algo250302;
import java.io.*;
public class Baek20437 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
String W = br.readLine();
int K = Integer.parseInt(br.readLine());
if (K == 1) {
System.out.println("1 1");
continue;
}
// 알파벳별 개수 저장
int[] alpha = new int[26];
int length = W.length();
for (int j = 0; j < length; j++) {
alpha[W.charAt(j) - 'a']++;
}
int min = Integer.MAX_VALUE; // 최솟값은 가장 큰 수로
int max = -1; // 최댓값은 가장 작은 수로
for (int j = 0; j < length; j++) {
if (alpha[W.charAt(j) - 'a'] < K) {
continue;
}
int count = 1;
for (int l = j + 1; l < length; l++) {
if (W.charAt(j) == W.charAt(l)) {
count++;
}
if (count == K) {
min = Math.min(min, l - j + 1);
max = Math.max(max, l - j + 1);
break;
}
}
}
if (min == Integer.MAX_VALUE || max == -1) {
System.out.println("-1");
} else {
System.out.println(min + " " + max);
}
}
}
}
Java
복사