[백준 25970] 현대 모비스 에어 서스펜션 - JAVA

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

 

완전 탐색을 해야함은 자명하다.

 

Java로 생각한 방법 중 최고 복잡도가 나오는 (부분문자열 기반, 출력 최적화x)로 풀었는데 통과되었다.

 

아마 "특정 언어에서 쉬운 문제"가 아닌가 싶다.

 

정해(문제 분류)는 비트마스킹을 활용한 풀이다. (판단데이터 B (B.length <=50)를 key로 value를 세는 풀이가 생각났다.)

 

난이도 기여에 가면 좀 더 어려운 알고리즘을 적용할 수 있다고 써있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int B = Integer.parseInt(br.readLine());
    String[][] bit = new String[B][2];

    for (int i = 0; i < B; i++) {
      bit[i][0] = br.readLine();
    }
    for (int i = 0; i < B; i++) {
      bit[i][1] = br.readLine();
    }

    int N = Integer.parseInt(br.readLine());
    String[] comp = new String[N];

    for (int i = 0; i < N; i++) {
      comp[i] = br.readLine();
    }

    for (int i = 0; i < N; i++) {

      String cs = comp[i];
      int cl = cs.length();

      int high = 0;
      int low = 0;

      for (int t = 0; t < B; t++) {
        String hs = bit[t][0];
        String ls = bit[t][1];

        int hl = hs.length();
        int ll = ls.length();

        for (int j = 0; j + hl <= cl; j++) {

          String sub = cs.substring(j, j + hl);

          if (sub.equals(hs)) {
            high++;
          }
        }

        for (int j = 0; j + ll <= cl; j++) {

          String sub = cs.substring(j, j + ll);

          if (sub.equals(ls)) {
            low++;
          }
        }
      }

      if (high == low) {
        System.out.println("GOOD");
      } else if (high > low) {
        System.out.println("HIGH " + Math.abs(high - low));
      } else {
        System.out.println("LOW " + Math.abs(high - low));
      }
    }
  }
}