백준 20437번 : 문자열 게임 2

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

 

---

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

---

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

---

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

🔵풀이

처음에 T의 입력 범위를 문자열 길이로 착각하여 투포인터로 접근하였지만, 시간초과가 났습니다,,,(잘보자..!) 이후 해쉬맵을 사용하여 훨씬 간단하게 풀이할 수 있었습니다. 해쉬맵을 이용하여 순차적으로 문자열의 문자를 넣어주었고 K 개수가 되는 문자에 대해서 indexOf를 이용하여 길이를 구할 수 있었습니다. 한번 길이를 구한 문자에 대해서도 계속해서 진행하기 위해 indexOf를 탐색시작을 저장하는 배열을 만들어 이후에 문자에 대해서 탐색할 수 있도록 해주었습니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.valueOf(br.readLine());
    int[] count = new int[26];

    for (int i=0; i<T; i++){
      String str = br.readLine();
      int K = Integer.valueOf(br.readLine());
      int min = Integer.MAX_VALUE;
      int max = Integer.MIN_VALUE;
      Map<Character, Integer> map = new HashMap<>();
      StringBuffer tmp = new StringBuffer(str);
      int[] fromIndex = new int[26];

      for (int j=0; j<str.length(); j++){
        if(map.containsKey(str.charAt(j))) {
          map.put(str.charAt(j), map.get(str.charAt(j)) + 1);
        }
        else map.put(str.charAt(j), 1);

        if (map.get(str.charAt(j))==K){
          int k = str.charAt(j)-'a';
          int compare = str.indexOf(str.charAt(j),fromIndex[k]);
          min = Math.min(min,j-compare+1);
          max = Math.max(max,j-compare+1);
          map.put(str.charAt(j), map.get(str.charAt(j)) - 1);
          fromIndex[k] = compare+1;
        }
      }

      if (min==Integer.MAX_VALUE){
        System.out.println(-1);
      }
      else {
        System.out.println(min + " " + max);
      }
    }
  }
}