백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이)

백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이)

 

---

 

 

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

 

---

 

이분 탐색을 이용한 풀이이다. 

 

N개의 문자열로 이루어진 집합 S에서 M개의 문자열 중 집합 S에 속하는 문자열의 개수를 구해야 한다. 

 

자바의 컬렉션 Set의 contains 메서드를 이용하면 간단하게 풀 수 있지만 바이너리 서치를 직접 구현해 풀어보기 좋은 문제여서 바이너리 서치를 이용해 풀어보았다. 

 

먼저 문자열을 sort 해준다. 

 

String[] strings = new String[N];
while(N-->0){
   strings[N] = bufferedReader.readLine();
}

Arrays.sort(strings);

 

-> 시간 복잡도 O(nlogn)

 

문자열 집합에 대해 exist 함수를 통해 count 값을 구한다. 

 

int count =0;
while(M-->0){
   if(exist(bufferedReader.readLine(), strings)){
      count++;
   }
}

 

exist 함수에 바이너리 서치를 구현해주면 된다. 

 

숫자를 찾는 것과 로직이 같은 이유는 String 클래스에서 compareTo 메서드를 이미 구현해 놓았기 때문이다. 

 

즉, 같은 경우(이때도 compareTo를 써도 됨)와 

if (strings[mid].equals(word)){
   return true;
}

 

다른 경우를 다음과 같이 판단할 수 있다. 

 

if (strings[mid].compareTo(word) < 0){
   left = mid +1;
} else if(strings[mid].compareTo(word) > 0){
   right = mid -1;
}

 

 

이분 탐색을 그대로 구현해준다. 

 

private static boolean exist(String word, String[] strings) {

   int left =0 ;
   int right = strings.length -1;

   while(left<=right){
      int mid = (left + right) / 2;
      if (strings[mid].equals(word)){
         return true;
      }
      if (strings[mid].compareTo(word) < 0){
         left = mid +1;
      } else if(strings[mid].compareTo(word) > 0){
         right = mid -1;
      }
   }
   return false;
}

 

이때 시간 복잡도는 어떻게 될까? 

 

문자열 비교 compareTo 메서드의 시간 복잡도는 O(n), 즉 문자열 길이 만큼 가지므로 

 

binarySearch의 시간복잡도 O(logn)에 이 값을 곱한 

 

O(Xlogn)이 되는데, 문제의 케이스를 M 번 반복하므로 

 

O(M * Xlogn)이 된다. 

 

이때, X의 값이 500이므로 크지 않아 넉넉한 시간을 가질 수 있다. 

 

 

💡 코드 구현

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int N = Integer.parseInt(stringTokenizer.nextToken());
      int M = Integer.parseInt(stringTokenizer.nextToken());

      String[] strings = new String[N];
      while(N-->0){
         strings[N] = bufferedReader.readLine();
      }

      Arrays.sort(strings);

      int count =0;
      while(M-->0){
         if(exist(bufferedReader.readLine(), strings)){
            count++;
         }
      }

      System.out.println(count);

   }

   private static boolean exist(String word, String[] strings) {

      int left =0 ;
      int right = strings.length -1;

      while(left<=right){
         int mid = (left + right) / 2;
         if (strings[mid].equals(word)){
            return true;
         }
         if (strings[mid].compareTo(word) < 0){
            left = mid +1;
         } else if(strings[mid].compareTo(word) > 0){
            right = mid -1;
         }
      }
      return false;
   }

}