백준 7795번 : 먹을 것인가 먹힐 것인가 (이진탐색)

게시 2024/04/02

By Jeremiah Lee 11 분 : 읽는 시간

이번 문제는 집합 A와 집합 B가 있을 때, 집합 A의 원소가 집합 B의 원소 보다 큰 경우를 한 쌍으로 최대 몇 쌍이 이루어지는 지 개수를 찾는 문제이다.

즉, A = {8, 1, 7, 3, 1}, B = {3, 6, 1}로 주어진 경우, 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1로 7 가지 경우의 수가 있다.

이 때, 정답은 7이다.

위와 같은 방식으로 주어지는 테스트 케이스 개수 T에 맞춰 정답을 리턴하면 된다.

우선 처음에는 입력되는 값을 핸들링하기 위해 두 개의 List를 활용하여 저장했다.

  
// 테스트 케이스
int t = Integer.parseInt(br.readLine());
 StringTokenizer st;
 while (t-- > 0) {
     st = new StringTokenizer(br.readLine());
     int n = Integer.parseInt(st.nextToken());
     int m = Integer.parseInt(st.nextToken());

     List<Integer> A = new ArrayList<>();
     st = new StringTokenizer(br.readLine());
     for (int i = 0; i < n; i++) {
         A.add(Integer.parseInt(st.nextToken()));
     }

     List<Integer> B = new ArrayList<>();
     st = new StringTokenizer(br.readLine());
     for (int i = 0; i < m; i++) {
         B.add(Integer.parseInt(st.nextToken()));
     }

  ...
 }

각 A와 B 집합을 ArrayList에 담아내고, 이를 정렬하여 효율적인 탐색을 위해 이진 탐색을 적용하면 되는데, 처음 풀 때는 A 집합을 내림차순으로, B 집합을 오름차순으로 정렬한 다음 각각 앞과 뒤를 비교하는 방법을 사용했다.

  
// A 집합은 내림차순 (큰것부터 비교)
A.sort(Collections.reverseOrder());
// B 집합 오름차순 (작은것부터 비교)
Collections.sort(B);

당장 생각난 방법이 이 방법이었기 때문에 일단 쭉 풀어보았다.

앞선 코드로 정렬을 해주고, 다음으로 비교를 진행했다.

  
// 비교
int result = 0;
for (int i = 0; i < n; i++) {
    int aNum = A.get(i);
    for (int j = 0; j < m; j++) {
        int bNum = B.get(j);
        
        if (aNum > bNum) {
            result++;
        }
    }
}

이중 반복문을 실행시켜서 각각 A 집합의 원소와 B 집합의 원소를 추출하고, A 집합을 기준으로 서로의 크기를 비교 후 result 변수에 값을 할당했다.

이렇게 해도 원하는 값을 도출해낼 수 있다.

그러나 이 방법은 효율적이지 않다.

테스트 케이스 최대 개수는 정해지지 않았지만 결국 while 문 내부에서 2중 반복문이 돌아가고, 또 모든 경우를 구하는 브루트포스 방식이기 때문에 집합 내 원소가 커질 수록 시간복잡도가 기하급수적으로 늘어난다.

즉, 시간 복잡도가 O(NM)으로, A와 B 집합의 원소가 각각 10000개 라고 하면, 10000 * 10000 의 경우의 수를 모두 탐색해야한다.

각 집합의 원소 최대 개수가 20,000개이기 때문에 굉장히 비효율적인 알고리즘이다.

이를 해결하기 위해 문제의 힌트를 체크했고, 이진 탐색이라는 힌트가 있어 해당 알고리즘을 사용했다.

이진 탐색이라는 것은 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘이다.

이진 탐색의 동작 방식 자체가 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식이기 때문에 이분 탐색이라고도 한다.

기본적으로 데이터 입출력에 관련된 코드는 기존 방식과 동일하다.

그러나 마지막 비교 연산 과정에서 변경이 있다.

  
// B 집합 오름차순 (작은것부터 비교)
Collections.sort(B);
 
// 비교 - 이진 탐색
int result = 0;
for (int i = 0; i < n; i++) {
    int aNum = A.get(i);
    int idx = lower(B, aNum);
    result += idx;
}

System.out.println(result);

기존에는 A 집합과 B 집합 두 집합을 모두 정렬하여 사용했다면, 이번에는 비교 대상이 되는 B 집합만 오름차순 정렬한다.

이후 반복문 내부에서 lower라는 이진 탐색 알고리즘이 적용된 함수를 활용하여 값을 찾는다.

이 때, 기준 값을 A 집합의 원소이고, B 집합과 함께 매개변수로 이진 탐색 함수로 전달한다.

이후 idx는 현재 입력된 A 집합 원소에 대응되는 “쌍”의 개수이며, 이를 result에 합산하여 최종적으로 이 result를 리턴하면 정답이 된다.

사용된 이진 탐색 알고리즘은 다음과 같다.

  
// 비교 함수 - 이진 탐색
private static int lower(List<Integer> B, int target) {
    int low = 0, high = B.size();
    while (low < high) {
        int mid = (low + high) / 2;
        if (B.get(mid) < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low; // target 보다 작은 원소들의 개수
}

lower라는 이름의 이진 탐색 알고리즘은 앞서 말했듯이 정렬된 배열에서 특정 값을 효율적으로 찾기 위해 사용된다.

여기에서는 특정 값인 A 집합의 원소보다 작은 원소들의 개수를 찾는데 사용되었다.

위 함수는 다음과 같은 방식으로 작동한다.

low와 high 포인터를 배열의 시작과 끝으로 설정
mid를 low와 high의 평균으로 설정하여 중간 위치 탐색
배열의 mid 위치에 있는 원소를 검사
- 만약 mid 위치의 원소가 타겟 값보다 작으면, low를 mid + 1로 설정하여 검색 범위를 오른쪽으로 좁힘
- 그렇지 않은 경우, high를 mid로 설정하여 검색 범위를 왼쪽으로 좁힘
이 과정을 low < high가 될 때까지 반복

타겟 값보다 작은 원소들의 최대 인덱스를 찾아내어, 그 개수를 반환하는 방식을 사용함으로써 불필요한 탐색을 줄이고 검색 범위를 반으로 줄일 수 있기 때문에, 값을 탐색하는데 필요한 시간복잡도가 O(log m)으로 효율적인 탐색이 가능하다.

이로써, 기존의 방식에 비해 시간 복잡도를 O(NM) 에서 O(logM)으로 대략 9900% 개선했다. (M = 1000 인 경우)

전체 소스코드는 다음과 같다.

  
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        // 테스트 케이스
        int t = Integer.parseInt(br.readLine());

        StringTokenizer st;
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            List<Integer> A = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                A.add(Integer.parseInt(st.nextToken()));
            }

            List<Integer> B = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                B.add(Integer.parseInt(st.nextToken()));
            }

            // B 집합 오름차순 (작은것부터 비교)
            Collections.sort(B);

            // 비교 - 이진 탐색
            int result = 0;
            for (int i = 0; i < n; i++) {
                int aNum = A.get(i);
                int idx = lower(B, aNum);
                result += idx;
            }

            System.out.println(result);
        }
    }

    // 비교 함수 - 이진 탐색
    private static int lower(List<Integer> B, int target) {
        int low = 0, high = B.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (B.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low; // target 보다 작은 원소들의 개수
    }
}

이번 문제를 통해 이진탐색을 어떻게 구현해야하는지 파악이 어느정도 되었다.

또한, 기존 풀이 방식보다 명백한 성능 개선이 있었기 때문에 이러한 방식으로 구현, 기술하는 것 자체가 아주 좋은 것 같다.

앞으로도 가능하다면 “성능 개선”에 중점을 두고 (알고리즘 문제 뿐만 아니라 프로젝트도) 기록할 수 있도록 하자.

알고리즘, 백준

알고리즘 백준

인기 태그