99클럽 코테 스터디 19일차 TIL ✒️Sort 마스터 배지훈의 후계자

✅ 오늘의 학습 키워드

• 이진 탐색 메서드 활용하기
• 출력 초과 에러

---

🔍 오늘의 문제 분석

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

 

• N개의 정수를 입력받아 오름차순으로 정렬
• M개의 정수 D가 정렬된 배열에서 처음으로 등장하는 인덱스 출력
• D가 배열에 없으면 -1 출력

---

✨ 오늘의 회고

📌내가 적은 답안📌

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringTokenizer st = new StringTokenizer(sc.nextLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    ArrayList<Integer> list = new ArrayList<>();

    for (int i = 0; i < N; i++) {
      list.add(sc.nextInt());
    }

    Collections.sort(list);

    for (int i = 0; i < M; i++) {
      int left = 0;
      int right = N - 1;
      int target = sc.nextInt();
      int answer = -1;

      while (left <= right) {
        int mid = (left + right) / 2;

        if (list.get(mid) == target) {
          answer = mid;
          right = mid - 1;
        } else if (list.get(mid) > target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }

      System.out.println(answer);
    }

  }
}

이진 탐색을 활용해서 정렬된 배열에서 정수 D의 위치를 효율적으로 탐색할 수 있도록 했다. 자바에서 기본으로 제공하는 Arrays.binarySearch() 메서드를 활용하는 방법과 메서드를 활용하지 않는 방법 두 가지를 모두 사용해 보았다.

 

오늘 문제에서 시간 초과와 출력 초과 에러가 발생했는데 결괏값을 출력할 때 for문 밖에서 하지 않고 for문 안에서 출력해서 중복으로 출력이 되는 문제가 있었다. 그리고 오름차순으로 배열을 정렬했을 때 동일한 정수가 2회 이상 나올 경우, 정수가 가장 먼저 등장한 위치를 출력해야 하는 상황을 고려해서 코드를 작성해야 했다.

 

그리고 binarySearch 메서드를 활용해 보면서 List 컬렉션이 아니라 배열형으로 풀어보았다. 이진 탐색 메서드는 값을 찾지 못했을 때 해당 요소가 삽입되어야 할 위치(insertion point)의 인덱스를 반환하는데 이때 반환되는 값은 -(insertion point) -1이다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[] numbers = new int[N];
        
        for (int i = 0; i < N; i++) {
            numbers[i] = sc.nextInt();
        }
        
        Arrays.sort(numbers);
        
        for (int i = 0; i < M; i++) {
            int target = sc.nextInt();
            int result = find(numbers, target);
            System.out.println(result);
        }
        
        sc.close();
    }
    
    private static int find(int[] arr, int target) {
        int index = Arrays.binarySearch(arr, target);
        
        if (index < 0) {
            return -1;
        }
        
        while (index > 0 && arr[index - 1] == target) {
            index--;
        }
        
        return index;
    }
}