[Java] 조합->탐색 알고리즘

Minuuu·2023년 2월 1일

목록 보기

14/36

1. 문제 설명

카드 개수 n개가 있고, 정답 카드 m개가 있다
n개의 카드 개수중 2개를 뽑아 두 카드의 합이 m이 되는 값을 도출하고자 한다
(단, 하나의 같은 카드를 중복으로 뽑는게 가능)
이 때 n개의 카드 중 두 카드의 합이 되는 m카드의 갯수를 구하시오

ex) cards[1, 9, 2, 7, 3] , targets[6, 7, 8]이라면 1+7, 3+3(중복카드가능) 2개가 정답

입력 형식

첫 줄에는 카드의 갯수 n (1 ~ 10만) 정답 카드의 수 m(1 ~ 100)을 입력한다
두 번째 줄에는 N개의 카드에 적힌 숫자들이 주어진다(1 ~ 1억이하의 자연수)
세 번째 줄에는 M개의 당첨번호가 주어진다(1 ~ 2억이하의 자연수)

출력 형식

2. 알고리즘 접근

단순히 생각한다면 위는 n개의 카드를 두번 뽑아 조합하는 조합문제인 것 같다
하지만 그런식으로 접근한다면

for(int x : cards){
	for(int y : cards){}
    	if(x + y == k){}
}

위와 같이 가게되는데 그렇다면 O(N *N)의 시간복잡도가 나와 시간제한에 걸린다

조합문제를 -> 탐색문제로 바꿔보자

우리가 당첨번호를 target이라고 가정하고 당첨번호를 6이라고 가정해보겠다
그리고 카드 하나(p)를 뽑았을 때 4를 뽑았다고 또 가정을 한다면
target = p + q 일 것이다
그렇다면 여기서 q는 무엇일까? -> q = 반드시 2인 값만 맞는 결과가 도출된다
즉 우리는 일일히 모두 탐색하며 조합을 할 것이 아니라
p2에 맞는 값을 탐색하여 문제를 푸는 방법을 사용한다

모든 target을 돌면서 첫 카드p를 뽑으면
두번 째 카드는 target - p가 되어 이 카드가 카드에 있는지 확인하면 된다

이를 확인하는 방법은 이진 검색을 이용할 것

이진 검색

-> 반드시 정렬해야만 사용할 수 있음
-> 절반씩 쪼개어 검색하는 알고리즘 기법 $O(Log_2N)$ 을 이용하여 풀자

3. 알고리즘 풀이

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

public class Q3H {
    static final Scanner sc = new Scanner(System.in);
    // 결과값 도출 함수
    private static int getPossibleTargetNumber(int n, int m, int[] cards, int[] target) {
        int answer = 0; // 만들 수 있는 당첨번호의 수

        Arrays.sort(cards); // O(N Log2 N)
        for(int k: target){ // +O(MN Log2 N)
            // k:= 모든 당첨번호가 들어온다
            // k가 cards[]의 합으로 표현될 수 있는지 확인
            boolean possible = false;
            for(int p : cards){
                int q = k - p;
                //cards 내에 q가 존재하는지만 검사 (이진탐색)
                if(Arrays.binarySearch(cards, q) >= 0){
                    // cards배열안에 q값이 있는지 검색 찾으면 인텍스값이 나오고 못찾으면 음수값이 나옴
                    possible = true;
                    break;
                }
            }
            if(possible){
                answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int n = sc.nextInt(); // 사용할 카드의 수 n (1 ~ 10만)
        int m = sc.nextInt(); // 당첨 번호의 수 m (1~100)

        int[] cards = new int[n]; // n개의 카드의 수를 담을 배열
        int[] target = new int[m]; // 당첨 번호의 수를 담을 배열

        for(int i = 0; i < cards.length; i++){
            cards[i] = sc.nextInt(); // 카드 데이터 입력 (1 ~ 1억)
        }
        for(int i = 0; i < target.length; i++){
            target[i] = sc.nextInt(); // 당첨 번호 담을 배열 (1 ~ 2억)
        }
        // n개의 당첨번호 중 2개를 뽑아 2개를 합했을 때 당첨번호가 될 수 있는 값의 개수를 찾는 를제(중복된 카드를 뽑을 수 있다)
        // n = 5, m = 3이고
        // cards[1, 9, 2, 7, 3] , targets[6, 7, 8]이라면 1+7, 3+3(중복카드가능) 2개가 정답
        // ex) target 6을 찾는데 p라는 값에 2를 찾았다면 q는 4여야 target이랑 맞을것이다 즉 p + q = target
        // 즉 조합을 통해 이미 target과 p를 찾았다면 q의 값은 정해져있기 때문에 탐색으로 풀 수 있다 -> 효율적인 이진검색을 활용하자

        int answer = getPossibleTargetNumber(n ,m, cards, target);

        System.out.println(answer);


    }
}

위 코드의 시간복잡도는 이진 검색을 할 때 $O(Log_2N)$ 이고
이를 카드의 갯수 n만큼 진행하기 때문에 $O(N Log_2N)$ 이고
또 이를 정답의 개수 m만큼 진행하기 때문에 $O(MN Log_2N)$ 의 시간복잡도를 가지고
정렬을 하면서 $O(N Log_2N)$ 의 시간복잡도를 가진다
즉 이를 더한 $O(MN Log_2N) + O(N Log_2N)$ 가 결과로 나오지만 계수가 왼쪽이 크기에 $O(MN Log_2N)$ 의 시간복잡도를 가지게 된다