[BOJ] 20437 문자열 게임 2

문자열 게임 2

풀이

• "어떤 문자를 정확히 K개" 포함하는 가장 짧은 연속 문자열의 길이와
• "어떤 문자를 정확히 K개" 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구하는 문제
• HashMap<Character,ArrayList> 를 사용해야겠다고 생각한 이유는, 각 알파벳이 등장한 index와 갯수를 저장해야겠다고 생각했기 때문이다.
• 정확히 "K개" 를 포함하는 것이 문제의 조건이기 때문에, 슬라이딩 윈도우 로도 풀 수 있다. 각 알파벳에 대해서 List<Integer>[] list = new ArrayList[26]; 으로 list를 만들고, 등장 시에 index를 각 list에 추가하는 방식.

  😊 내 풀이

  import java.util.*;
  import java.io.*;
  public class BOJ20437 {
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int T = Integer.parseInt(br.readLine());
          for(int i=0;i<T;i++){
              String str = br.readLine();
              int K = Integer.parseInt(br.readLine());
              HashMap<Character,ArrayList> alpha = new HashMap<>();
              for(int j=0;j<str.length();j++){
                  ArrayList<Integer> list;
                  if(alpha.containsKey(str.charAt(j))){
                      list = alpha.get(str.charAt(j));
                  }
                  else{
                      list = new ArrayList<>();
                  }
                  list.add(j);
                  alpha.put(str.charAt(j),list);
              }
              ArrayList<Character> alphabet = new ArrayList<>(alpha.keySet());
              ArrayList<Character> keys = new ArrayList<>();
              for(char c: alphabet){
                  ArrayList arrayList = alpha.get(c);
                  if(arrayList.size()>=K){
                      keys.add(c);
                  }
              }
              if(keys.size()==0){
                  System.out.println("-1");
              }
              else{
                  int shortest = Integer.MAX_VALUE;
                  int longest = Integer.MIN_VALUE;
                  for(char key:keys){
                      ArrayList list = alpha.get(key);
                      for(int s=0;s<=list.size()-K;s++){
                          int index = (int)list.get(s);
                          int next = (int)list.get(s+K-1);
                          shortest = Math.min(shortest,(next-index)+1);
                          longest = Math.max(longest,(next-index)+1);
                      }
                  }
                  StringBuilder sb = new StringBuilder();
                  sb.append(shortest).append(" ").append(longest);
                  System.out.println(sb);
              }
          }
      }
  }

  • HashMap에 등장한 알파벳에 대해 index들을 list로 저장했다.
  • 그리고 HashMap의 keySet을 뽑아, for문 돌면서 size가 K개 이상, 즉 각 알파벳 중 K번 이상 등장한 녀석들을 keys 라는 list에 후보로 넣었다.
  • keys 후보들을 돌면서, index를 이용하여 가장 짧은 길이, 가장 긴 길이를 구했다.
  • 지금 생각해보니 keys 후보들을 따로 저장할 필요 없이, 그냥 HashMap keySet을 순회하면서 value list size가 K개 이상인 애들에 대해서 짧은 길이, 긴 길이를 구하면 될 것 같다.

골드를 한 번에 푼게 오랜만이라 기분이 좋다 😋