[코딩테스트] [2470] 두 용액 & [10816] 숫자 카드 2

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

문제풀이

이 문제는 N개의 용액이 주어지는데 이 용액의 특성값이 -[10억:10억] 범위로 주어진다.

이 서로 다른 용액을 혼합하여(더하여) 특성값이 0에 가까운 용액을 만들자.

0에 가까운 용액을 만드는 용액 2개를 구하는 문제이다.

그러면 아래처럼 정렬된 배열이 주어졌을 때 어떻게 0에 가까운 용액을 찾는 지 알아보자.

자기 자신(0번째 요소)를 제외한 나머지 요소들 중에서 찾아야 한다.

이 때, 이분탐색방법(binary search)를 사용할 수 있다.

L = 1, R = 8 로 잡으면 M = -2가 된다.

이때 M과 자신(-99)을 더하면 -101이 된다.

그러면 -101은 음수이고 -2보다 작은 값을 더하면 절대값이 0보다 더 멀어지는 상황이 나온다.

즉, L = M+1로 하면 된다.

그 뒤로 또 이분탐색방법을 사용하면 -99 + 6 = -93이 되기 때문에 또 L = M+1로 하면 된다.

마찬가지로, -99 + 75 = -24 이기에 또 오른쪽으로 이동하고 결국 -99 + 89까지 가는데 더한값이 -99+89=-10이고 89보다 더 큰 값이 없기에 89가 -99기준으로 더하여 0에 가까운 용액이다.

1. 현재 요소와 다른 요소를 더하였을 때 0에 가까운 값 찾기

그래서 위의 풀이 방식을 코드로 변환해보자.

    static int findOptimalPair(int[] arr, int fromIndex, int toIndex, int value) {
        int optimalPairValue = arr[fromIndex];
        int optimalAbs = Math.abs(value + optimalPairValue);
        int l = fromIndex + 1, r = toIndex;
        while (l <= r) {
            int m = (l+r)/2;
            int sum = value + arr[m];
            int sumAbs = Math.abs(sum);
            if (sumAbs < optimalAbs) {
                optimalPairValue = arr[m];
                optimalAbs = sumAbs;
            }
            if (sum < 0) l = m + 1;
            else if (sum > 0) r = m - 1;
            else return optimalPairValue
        }
        return optimalPairValue;
    }

2. 반복문을 이용하여 0에 제일 가까운 값 찾기

위 함수에서 현재 요소를 더하였을 때 0에 가까운 요소를 찾았기에 이제 더한 값들 중 가장 0에 가까운 값을 찾아야한다.

int ansAbs = Math.abs(arr[0] + arr[1]);
int ans1 = arr[0];
int ans2 = arr[1];
for (int i = 0; i < N-1; i++) {
	int pairValue = findOptimalFari(arr, i + 1, N - 1, arr[i]);
	int sumAbs = Math.abs(arr[i] + pairValue);
	if (ansAbs > sumAbs) {
		ansAbs = sumAbs;
		ans1 = arr[i];
		ans2 = pairValue;
	}
}

전체코드

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

class Main
{
    static int findOptimalPair(int[] arr, int fromIndex, int toIndex, int value) {
        int optimalPairValue = arr[fromIndex];
        int optimalAbs = Math.abs(value + optimalPairValue);
        int l = fromIndex + 1, r = toIndex;
        while (l <= r) {
            int m = (l+r)/2;
            int sum = value + arr[m];
            int sumAbs = Math.abs(sum);
            if (sumAbs < optimalAbs) {
                optimalPairValue = arr[m];
                optimalAbs = sumAbs;
            }
            if (sum < 0) l = m + 1;
            else if (sum > 0) r = m - 1;
            else return optimalPairValue;
        }
        return optimalPairValue;
    }

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

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

        Arrays.sort(arr);

        int ansAbs = Math.abs(arr[0] + arr[1]);
        int ans1 = arr[0];
        int ans2 = arr[1];
        for (int i = 0; i < N-1; i++) {
            int pairValue = findOptimalPair(arr, i + 1, N - 1, arr[i]);
            int sumAbs = Math.abs(arr[i] + pairValue);
            if (ansAbs > sumAbs) {
                ansAbs = sumAbs;
                ans1 = arr[i];
                ans2 = pairValue;
            }
        }

        System.out.println(ans1 + " " + ans2);
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 findOptimalPair함수에서 이분탐색방법을 사용하니 O(logN),

그리고 정답을 구할때 반복문안에 findOptimalPair함수가 있으니 O(NlogN)이다.

TreeSet을 이용한 풀이

이 문제는 Set을 이용하여 풀 수 있다.

TreeSet의 메서드 중에서는 floor 와 ceiling 메서드가 있는데 이 메서드들을 사용하면 된다.

set.floor(x)는 set중에서 x이하인 값 중 가장 가까운 값을 반환한다. 만약 x가 최소값이라면 x 이하인 값이 없을 수 도 있으니 없다면 null을 반환한다.

set.celiing(x)는 set중에서 x이상인 값 중 가장 가까운 값을 반환한다. 마찬가지로 만약 x가 최대값이라면 x이상인 값이 없을 수 있으니 없다면 null을 반환한다.

그렇다면 이 두개의 메서드를 이용해서 풀어보자.

왜 set.add를 마지막에 하냐면 먼저 넣으면 자기 자신과 비교를 하기 때문에 비교를 하고 마지막에 넣는 것이다.

int ansAbs = 2000000001;
int ans1 = 0;
int ans2 = 0;
TreeSet<Integer> set = new TreeSet<>();
for(int i = 0; i<N; i++) {
	int x = sc.nextInt();
	Integer[] pairValues = {set.floor(-x), set.ceiling(-x)};
	for (Integer pairValue: pairValues) {
		if (pairValue == null) continue;
		int sumAbs = Math.abs(x + pairValue);
		int (ansAbs > sumAbs) {
			ansAbs = sumAbs;
			ans1 = x;
			ans2 = pairValue;
		}
	}
}
set.add(x);
}

전체코드

import java.util.Scanner;
import java.util.TreeSet;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ansAbs = 2000000001;
        int ans1 = 0;
        int ans2 = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 0; i<N; i++) {
            int x = sc.nextInt();
            Integer[] pairValues = {set.floor(-x), set.ceiling(-x)};
            for (Integer pairValue: pairValues) {
                if (pairValue == null) continue;
                int sumAbs = Math.abs(x + pairValue);
                if (ansAbs > sumAbs) {
                    ansAbs = sumAbs;
                    ans1 = x;
                    ans2 = pairValue;
                }
            }
            set.add(x);
        }

        System.out.println(Math.min(ans1, ans2) + " " + Math.max(ans1, ans2));
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 TreeSet을 사용하니 O(logN)인데 N번 반복하니 O(NlogN)이다.

TreeSet을 사용하면 더 간단하게 알고리즘을 작성할 수 있다.

[10816] 숫자 카드 2

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

168372

66928

47621

38.094%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

문제풀이

이 문제는 숫자에 해당하는 카드들이 몇 개가 있는지 찾아내면 되는 문제이다.

즉, Map 자료구조를 활용하여 Key(카드)에 해당하는 Value(개수)를 찾아내면 되는 문제이다.

그러면 코드로 간단하게 작성해보자.

출력한 수가 많기에 BufferedWriter를 사용하여 제출을 해야하지만 시간초과가 발생하지 않는다.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        int N = sc.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int M = sc.nextInt();
        while (M-- > 0) {
            int x = sc.nextInt();
            bw.write(map.getOrDefault(x, 0) + " ");
        }
        bw.write("\\n");
        bw.flush();
    }
}

이분탐색방법으로 풀이

이 문제는 이분탐색방법으로도 풀이가 가능하다.

바로 정렬하고 우리가 찾는 x값이 배열에 있을때 몇번째에 위치하고 있는지 파악하면 된다.

아래는 오름차순으로 정렬된 배열이다.

우리가 찾는 값이 3이면 3번째, 4번째에 위치하는 것을 알 수 있다.

그러면 3보다 큰 수 중 가장 작은값은 5번째 요소에 있을거고 5 - 3을하게 되면 2라는 값이 나오게 된다.

 

 

10이라고 가정하고 보자.

마찬가지로 7번째 요소가 10보다 크거나 같은 수이고 10번째 요소 부터 10보다 큰 값이니 빼주면 된다.

10 - 7 ⇒ 3

 

그러면 만약 우리가 찾는 값이 배열에 없을 때는 어떻게 동작하는 것인가

우리가 찾는 값이 5라면 5이상이 처음으로 나타는 것다. 즉 5번째 요소인 6이 시작이다.

즉 X이상의 값이 처음으로 나타나는 위치와 X초과의 값이 처음으로 나타나는 위치를 구하여 둘의 차를 계산하면 된다.

그러면 코드로 작성해보자.

LowerBoundIndex 찾는 함수 생성

arr[m]이 x와 같거나 큰 경우에는 X이상의 값이 처음으로 나타는 위치가 나오게 while문을 만들어준다.

중복된 값이 있다면 중복된 값 중 가장 맨 앞에 있는 위치가 반환이 될 것이다.

그래서 m을 반환해주자.

    static int findLowerBoundIndex(int[] arr, int x) {
        int lowerBoundIndex = arr.length;
        int l = 0, r = arr.length-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else {
                r = m - 1;
                lowerBoundIndex = m;
            }
        }
        return lowerBoundIndex;
    }

UpperBoundIndex 찾는 함수 생성

마찬가지로 X를 초과하는 값을 찾는 함수를 생성해주자.

위 코드와 다른 점은 조건이 arr[m] > x인 경우이다.

   static int findUpperBoundIndex(int[] arr, int x) {
        int upperBoundIndex = arr.length;
        int l = 0, r = arr.length-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if (arr[m] <= x) l = m + 1;
            else {
                r = m - 1;
                upperBoundIndex = m;
            }
        }
        return upperBoundIndex;
    }

답 구하기

이렇게 lowerIndex와 upperIndex를 구하였으면 그 둘의 값을 빼서 나온 결과를 출력하면 된다!

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i< N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        int M = sc.nextInt();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < M; i++) {
            int count = 0;
            int X = sc.nextInt();
            int lowerIndex = findLowerBoundIndex(arr, X);
            int upperIndex = findUpperBoundIndex(arr, X);
            bw.write(upperIndex - lowerIndex + " ");
        }
        bw.flush();

전체 코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

class Main {
    static int findLowerBoundIndex(int[] arr, int x) {
        int lowerBoundIndex = arr.length;
        int l = 0, r = arr.length-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else {
                r = m - 1;
                lowerBoundIndex = m;
            }
        }
        return lowerBoundIndex;
    }

    static int findUpperBoundIndex(int[] arr, int x) {
        int upperBoundIndex = arr.length;
        int l = 0, r = arr.length-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if (arr[m] <= x) l = m + 1;
            else {
                r = m - 1;
                upperBoundIndex = m;
            }
        }
        return upperBoundIndex;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i< N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        int M = sc.nextInt();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < M; i++) {
            int count = 0;
            int X = sc.nextInt();
            int lowerIndex = findLowerBoundIndex(arr, X);
            int upperIndex = findUpperBoundIndex(arr, X);
            bw.write(upperIndex - lowerIndex + " ");
        }
        bw.flush();
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 입력할 때 O(N) 그리고 출력할 때 M번 만큼 이분탐색방법을 진행하니 O(MlogN)이 나온다.