99클럽 코테 스터디 13일차 TIL + 오늘의 학습 키워드

☑️ 문제: 숫자 카드

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

 

• 문제 풀이 고민
  • 완전탐색으로 풀면 N*M = (5 * 10^5)^2 이기 때문에 안 된다.
  • 어떤 풀이 방법이 있을지 고민해보다 아래 풀이들이 떠올랐다.
    1. 첫번째: Set 자료구조 사용해서 풀기
    2. 두번째: 정렬 후, 이분탐색하기
    3. 세번째: 2*10^7 크기의 인덱스 배열을 활용해서 풀기

 

☑️ 풀이1: Set 자료구조 사용해서 풀기

import java.util.*;

public class Main {
  public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      Set set = new HashSet<Integer>();
      
      int N = sc.nextInt();
      for (int i = 0; i < N; i++) {
          set.add(sc.nextInt());
      }
      
      StringBuilder answer = new StringBuilder(""); // String을 쓸 경우, 시간 초과.
      int M = sc.nextInt();
      for (int i = 0; i < M; i++) {
          int num = sc.nextInt();
          answer.append(set.contains(num) ? 1 : 0);
          answer.append(" ");
      }
      
      System.out.println(answer); // print를 여러번 부르면 시간이 걸림.
  }
}

 

 

과거에 이미 풀었던 문젠데, 그 때의 나는 세번째 방식으로만 풀어보았더라.

나머지는 다른 해야 할 일이 끝나고 여유가 생기면 도전해보고,

각 풀이의 복잡도를 계산해보자.