-
[백준]20437: 문자열 게임2(java)Algorithm/백준 2022. 5. 2. 19:58728x90
https://www.acmicpc.net/problem/20437
문제
작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.
- 알파벳 소문자로 이루어진 문자열 W가 주어진다.
- 양의 정수 K가 주어진다.
- 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
- 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.
위와 같은 방식으로 게임을 T회 진행한다.
입력
문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)
다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)
출력
T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.
만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.
예제 입력 1
2 superaquatornado 2 abcdefghijklmnopqrstuvwxyz 5
예제 출력 1
4 8 -1
첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.
두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.
풀이
문제 자체는 어렵지 않았지만 어떻게 접근하느냐에 따라 시간이 정말 많이 차이났다.
a~z를 0~25로 표현하여 int형 배열을 만든 후 각 단어의 등장 횟수를 저장한다.
1) 현재 문자가 총 등장 횟수가 K보다 작으면 볼 필요가 없다.
2) 이미 본 단어는 빼준다.
이 2개가 핵심으로 작용했던 것 같다.
전체 코드
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class BJ_G5_20437_문자열게임2 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder ans = new StringBuilder(); int TC = Integer.parseInt(br.readLine()); for(int t=1; t<=TC; t++) { char[] arr = br.readLine().toCharArray(); int[]charArr = new int[26]; int K = Integer.parseInt(br.readLine()); if(K==1) { ans.append("1 1"); if(t!=TC) { ans.append("\n"); } continue; } for(int i=0; i<arr.length; i++) { charArr[arr[i]-'a']++; } int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i=0; i<arr.length-K+1; i++) { char word = arr[i]; if(charArr[word-'a'] <K) continue; int cnt = 1; for(int j=i+1; j<arr.length; j++) { if(word == arr[j]) { cnt++; } if(cnt == K) { if(min > j-i+1) { min = j-i+1; } if(max < j-i+1) { max = j-i+1; } charArr[word-'a']--; break; } } } if(min==Integer.MAX_VALUE) { ans.append("-1"); } else { ans.append(min + " " + max); } if(t!=TC) { ans.append("\n"); } } System.out.printf("%s", ans.toString()); } }
728x90'Algorithm > 백준' 카테고리의 다른 글
[백준]12100: 2048(Easy)(java) (0) 2022.05.05 [백준]6416: 트리인가? (0) 2022.05.03 [백준]2933: 미네랄(java) (0) 2022.05.01 [백준]5430: AC(java) (0) 2022.04.30 [백준]4179: 불!(java) (0) 2022.04.29