문제 탐색하기
입력 자료 정리하기
- T는 게임의 수, 즉 테스트케이스 개수다
- 이어서 오는 문자열은 탐색에 대상이 될 문자열이다
- k는 정답을 찾는데 기준이 될 숫자이다.
해결방법 추론
- 어떻게 문제를 풀어야할까 고민하던 와중,
두가지에서 힌트를 얻어 해결방법을 추론할 수 있었다 - 먼저 개수를 세어서 k개 될때를 찾아야한다.
주어진 알파벳 문자열이 반복되며 개수를 세어주어야지 가능하기 때문에,
HashMap을 사용하여 탐색 과정속에서 개수를 기록한다면 될 것이라 생각하였다 - 또한 길이를 찾아야한다. 따라서 그 길이를 보관해줄 알파벳 배열이 필요하다고 생각하였다
- 하지만 k만큼 찾게 되면 그 기록이 모두 삭제되어야 하는 것이 아니다.
- 발견할 때마다 그 위치를 기록하면서 슬라이딩 윈도우처럼
위치의 개수가 k개가 되도록 맞춰나가야 한다 - 따라서 우선순위 큐 배열을 사용하여, 위치를 기록하면 될 것이라 생각하였다
- 이렇게 하면 n번의 탐색동안에 모든 조건을 만족시킬 수 있다.
시간복잡도 계산
- 총 연산은 T번의 케이스동안 n번의 탐색에서 끝난다
- 따라서 시간복잡도는 O(T x n)이 되며, 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- 테스트케이스와 k는 변수로 보관하며, 문자열은 문자 배열로 보관하여 관리한다
- 이외에는 hashMap과 우선순위큐 배열을 선언하며, 우선순위 큐 배열은 알파벳 개수인
26개를 맞춰 크기를 지정하며, 각 인덱스마다 우선순위 큐 인스턴스를 생성한다
탐색 로직 설계
- 최솟값과 최댓값 변수를 선언한다. 최솟값은 Integer.MAX_VALUE로 초기화하며,
최댓값은 -1로 초기화한다 - 탐색 과정속에서 map에 key로 없으면 1을 value로 하도록 넣어준다.
- 또한 알파벳 배열의 해당 알파벳 인덱스 위치에 현재 탐색 인덱스를 넣어준다
- 만약 key가 map에 있따면 그 크기를 증가시켜서 넣어준다.
알파벳 배열에도 동일하게 진행한다 - 이어서 만약 map의 개수가 k와 같다면, 현재 위치에서 알파벳 배열의 해당 인덱스의
우선순위 큐에서 값을 하나 뽑아 그 차이를 구한 다음 + 1을 더해서 길이를 구한다 - 그리고 map에 있는 value값을 감소시키고, 최솟값과 최댓값을 갱신한다
출력값 설계
- 출력값으로 big이 -1이라면 발견하지 못한 것이므로 -1을 출력한다
- 아닌 경우 최솟값과 최댓값을 출력하면 정답이 되는데...
시도회차 수정
1회차 시도 실패..
- 2%에서 틀렸습니다가 나와버렸다.
- 원인을 모르겠어서 반례를 생각하던 와중 k가 1일때 발생할 수 있겠다고 생각하였다
반례 탐색
- k가 1일때는 무조건 1 1이된다.
- 따라서 k가 1일때는 1 1 을 출력하도록 추가로 설정하였다
2회차 시도 성공!
- 위 반례를 하나 추가하니 바로 정답이 되었다!
정답 코드
(1회차 시도 실패...)
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
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));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
HashMap<Character, Integer> map = new HashMap<>();
PriorityQueue<Integer>[] alpha = new PriorityQueue[26];
for (int j = 0; j < 26; j++) {
alpha[j] = new PriorityQueue<>();
}
int small = Integer.MAX_VALUE;
int big = -1;
char[] input = br.readLine().toCharArray();
int k = Integer.parseInt(br.readLine());
for (int j = 0; j < input.length; j++) {
if(!map.containsKey(input[j])){
alpha[input[j] - 'a'].add(j);
map.put(input[j], 1);
}else{
map.put(input[j], map.get(input[j])+1);
int num = map.get(input[j]);
alpha[input[j] - 'a'].add(j);
if(num == k){
int ans = j - alpha[input[j] - 'a'].poll()+1;
map.put(input[j], num-1);
small = Math.min(small, ans);
big = Math.max(big, ans);
}
}
}
if(big == -1){
bw.write("-1\n");
}else{
bw.write(small+ " " + big + "\n");
}
}
br.close();
bw.close();
}
}(2회차 시도 성공!)
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));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
HashMap<Character, Integer> map = new HashMap<>();
PriorityQueue<Integer>[] alpha = new PriorityQueue[26];
for (int j = 0; j < 26; j++) {
alpha[j] = new PriorityQueue<>();
}
int small = Integer.MAX_VALUE;
int big = -1;
char[] input = br.readLine().toCharArray();
int k = Integer.parseInt(br.readLine());
for (int j = 0; j < input.length; j++) {
if(!map.containsKey(input[j])){
alpha[input[j] - 'a'].add(j);
map.put(input[j], 1);
}else{
map.put(input[j], map.get(input[j])+1);
int num = map.get(input[j]);
alpha[input[j] - 'a'].add(j);
if(num == k){
int ans = j - alpha[input[j] - 'a'].poll()+1;
map.put(input[j], num-1);
small = Math.min(small, ans);
big = Math.max(big, ans);
}
}
}
if(k == 1){
bw.write("1 1\n");
}else if(big == -1){
bw.write("-1\n");
}else{
bw.write(small+ " " + big + "\n");
}
}
br.close();
bw.close();
}
}
문제 링크
Software Developer