99클럽 코테 스터디 20일차 TIL ✒️CD 두 포인터/이분 탐색/해시

 

✅ 오늘의 학습 키워드

• binarySearch를 활용한 탐색 알고리즘
• StringBuilder, BufferedReader, StringTokenizer를 이용한 입출력 최적화
• 두 포인터 Two Pointers / HashSet을 이용한 탐색 최적화

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

• 입력은 여러 개의 테스트 케이스로 이루어져 있다
• 각 테스트 케이스는 N M으로 시작하며 0 0 입력이 들어오면 종료된다
• 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M (N, M ≤ 1,000,000)
• CD의 번호는 오름차순으로 주어진다
• 상근이와 선영이가 같은 CD를 여러 장 가지고 있는 경우는 없다
• 두 사람이 동시에 가지고 있는 CD의 개수를 출력한다

오늘의 문제는 두 사람이 가지고 있는 CD 번호 목록에서 중복되는 CD의 개수를 출력하는 문제였다. 이미 CD의 번호는 오름차순으로 정렬되어 있기 때문에 이분 탐색의 기본 조건인 정렬을 필요로 하지 않는다. 하지만 시간 복잡도를 줄이지 않으면 시간 초과 에러가 발생하기 때문에 이를 유념해서 풀어야 한다. 그리고 여러 개의 테스트 케이스를 처리할 수 있도록 루프를 구성해야 한다.

---

✨ 오늘의 회고

📌내가 적은 답안📌

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    while (true) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      if (N == 0 && M == 0) {
        break;
      }

      int[] n = new int[N];

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

      int result = 0;

      for (int i = 0; i < M; i++) {
        int target = Integer.parseInt(br.readLine());

        if (Arrays.binarySearch(n, target) >= 0) {
          result++;
        }
      }

      sb.append(result).append("\n");
    }
    System.out.println(sb);
  }
}

 

📗처음 작성한 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] s = sc.nextLine().split(" ");

    int N = Integer.parseInt(s[0]); //상근이가 가지고 있는 CD의 수
    int M = Integer.parseInt(s[1]); //선영이가 가지고 있는 CD의 수

    int[] n = new int[N];

    for (int i = 0; i < N; i++) {
      n[i] = sc.nextInt();
    }

      Arrays.sort(n);
    int result = 0;

    for (int i = 0; i < M; i++) {
      int target = sc.nextInt();
      int index = Arrays.binarySearch(n, target);

      if (index >= 0) {
        result++;
      }
    }

    System.out.println(result);

  }
}

 

처음 작성한 코드는 CD 목록을 배열로 받아서 binarySearch를 통해서 같은 CD의 개수를 result에 세도록 했다. 이 코드 자체는 문제가 없지만, 테스트 케이스를 한번만 처리하는 구조여서 여러 테스트 케이스를 처리하지 못하는 이슈가 있었다. 문제는 여러 개의 테스트 케이스를 포함하고 있기 때문에 while 루프 내부에서 전체 로직이 반복되도록 처리하는 것이 중요했다. 문제에서 제시한 테스트 케이스의 시작과 종료 조건을 이용해서 루프를 종료시키도록 코드를 수정했다.

 

🔖수정한 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    while (true) { //여러 개의 테스트 케이스 처리를 위한 루프
      int N = sc.nextInt(); //상근이가 가지고 있는 CD의 수
      int M = sc.nextInt(); //선영이가 가지고 있는 CD의 수

      if (N == 0 && M == 0) { //테스트 케이스 종료 조건 = 0 0 입력
        break;
      }

      int[] n = new int[N];

      for (int i = 0; i < N; i++) {
        n[i] = sc.nextInt();
      }

      int result = 0;

      for (int i = 0; i < M; i++) {
        int target = sc.nextInt();

        if (Arrays.binarySearch(n, target) >= 0) {
          result++;
        }
      }

      System.out.println(result);
    }

  }
}

 

while 루프를 사용해서 여러 개의 테스트 케이스를 처리할 수 있는 구조로 수정했으나 시간 초과 에러가 발생했다. 여기서 문제가 된 부분은 Scanner의 느린 입력 속도였다. 문제의 최대 입력 크기는 백만인데, 입력하는 데이터의 크기가 크면 입력 시간이 느려져서 시간 초과 에러가 난 것이다. 그래서 최종 제출한 코드처럼 BufferedReader와 StringBuilder를 사용해서 입출력 시간을 더 빠르게 처리하도록 수정했고 에러 없이 통과할 수 있었다. 하지만 binarySearch는 M 배열의 모든 요소에 대한 인덱스를 찾기 때문에 약간 비효율적인 부분이 있다. 여기서 두 포인터를 사용하면 더 빠르게 탐색할 수 있다.

 

🔁 두 포인터 풀이 방법

int i = 0, j = 0, result = 0;
while (i < N && j < M) {
    if (n[i] == m[j]) {
        result++;
        i++;
        j++;
    } else if (n[i] < m[j]) {
        i++;
    } else {
        j++;
    }
}

 

문제에서 배열은 모두 정렬된 상태로 주어지기 때문에 두 포인터 방법을 쓰면 가장 효율적으로 탐색할 수 있다. 두 포인터는 두 배열을 각각 포인터(i, j)로 순회하면서 비교하는 방식이다. 각 요소마다 한 번씩만 비교해서 처리하기 때문에 시간 복잡도가 가장 빠르고 메모리도 효율적이다.

 

🔁 HashSet 풀이 방식

Set<Integer> set = new HashSet<>();
for (int i = 0; i < N; i++) set.add(Integer.parseInt(br.readLine()));

int result = 0;
for (int i = 0; i < M; i++) {
    if (set.contains(Integer.parseInt(br.readLine()))) result++;
}

 

 

HashSet의 contains 메서드를 활용해서 중복된 요소를 찾는 방법이다. 인덱스를 찾을 필요가 없고 존재 여부만 확인하면 되기 때문에 binarySearch보다 효율적으로 탐색할 수 있다. 이 문제에서 CD 번호는 중복이 없어서 해시 충돌이 일어나지 않기 때문에 빠르고 일정한 속도로 찾을 수 있다는 점이 장점이다. 그리고 메서드를 사용하기 때문에 코드가 직관적이고 유지보수가 좋다.

 

---

 

미션 모두 완료!!!

 

✍️오늘로 20일간 진행한 99클럽 코테 스터디가 마무리되었다!

스터디를 시작하면서 매일 모든 미션을 빠짐없이 완료하자는 목표를 세웠는데, 그 목표를 달성할 수 있어서 참 다행이고 뿌듯하다. 매일 문제를 풀고 TIL을 작성하는 일이 결코 쉽지는 않았지만, 그 과정을 통해 많은 것을 배울 수 있었다. 

 

특히 스터디를 시작하기 전에는 자료구조도 잘 모르겠고 문제 풀이도 막막했는데, 스터디를 진행하면서 여러 자료구조에 점점 익숙해지면서 코테에 대한 자신감이 생긴 것이 가장 큰 수확인 것 같다😊

 

그리고 매일 두 번씩 오는 알림과 미션 덕분에 끝까지 완주할 수 있었다. 이번 스터디를 계기로 앞으로도 꾸준히 문제를 풀면서 실력을 더 쌓아가면 좋을 것 같다!