[240308] 알고리즘 리부트 27일차 - 백준 2470, 10816 자바

[Part1-Chapter07-Clip04]

- 백준 2470 두 용액

문제에서 주의해야 할 점은 '모든 용액의 특성값은 다르다, 산성 두 개 또는 알칼리성 두 개의 용액으로도 가장 0에 가까운 혼합 용액을 만들 수 있다' 라는 부분이다. 이 두 부분에서 정렬 처리와 음수와 양수를 구분하지 말기를 생각할 수 있었다. 이분 탐색으로 처리하다가 코드 상으로는 문제가 없어보였는데 5%에서 오류가 나서 투포인터 방식으로 다르게 구현했다.

두 값을 더한 값의 절댓값이 이전의 최솟값보다 작다면 갱신하여 두 개의 특성값을 저장했고 여기서 l과 r를 변경시키는 로직을 생각해내기가 어려웠는데 두 값을 더한 값이 0보다 작으면 더 작은 값을 키우고 0보다 크면 더 큰 값을 줄이도록 구현했다. 

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 int n;
    public static int[] solutions;

    public static void main(String[] args) throws IOException {
        input();
        Arrays.sort(solutions);

        //System.out.println(Arrays.toString(solutions));

        int min = Integer.MAX_VALUE;

        int num1 = 0;
        int num2 = 0;

        int l = 0;
        int r = n - 1;

        while (l < r) {

            //System.out.printf("l는: %d, r은: %d\n", l, r);

            if (Math.abs(solutions[l] + solutions[r]) < min) {
                min = Math.abs(solutions[l] + solutions[r]);
                num1 = solutions[l];
                num2 = solutions[r];
                //System.out.printf("** 갱신! 최솟값은: %d, 왼쪽 수는:  %d, 이번 테스트 수는: %d\n", min, num1, num2);
            }

            if (solutions[l] + solutions[r] < 0) {
                l++;
            } else {
                r--;
            }
        }
        System.out.println(num1 + " " + num2);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        solutions = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }
    }
}

 

[Part1-Chapter07-Clip05]

- 백준 10816 숫자 카드 2

주어지는 수의 최댓값이 int를 넘어가지 않아 배열로  풀어봐야겠다는 생각을 하게 되었고 카운팅 배열을 구현하여 문제를 풀었다. 메모리는 굉장히 많이 사용했지만 인덱스로 접근하는 방식 덕분에 시간은 훨씬 적게 걸린 것을 알 수 있다. 다만 주어지는 수 중에 음수가 존재해서 모든 입력 받는 수에 천만을 더해 음이 아닌 정수의 구간에 들어오게 처리했다. 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] cardArr = new int[20000001];

        st = new StringTokenizer(br.readLine());

        // 인덱스 접근이라 O(1)
        while (n-- > 0) {
            cardArr[Integer.parseInt(st.nextToken()) + 10000000]++;
        }

        int m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());

        while (m-- > 0) {

            int thisNum = Integer.parseInt(st.nextToken());

            sb.append(cardArr[thisNum + 10000000] + " ");
        }

        System.out.println(sb);

    }
}

그 다음은 강의에서 풀이한 방식이다. 이분 탐색으로 풀 수 있다고 해서 시도해봤지만 계속 틀리는 바람에 강의를 참고했다. 여기서 처음 알게 된 개념이 있는데 바로 이분탐색의 변형 버전인 lowerBound와 upperBound이다.

lowerBound는 특정 수 이상의 값 중 최초인 수의 인덱스를 구하는 것이고 upperBound는 특정 수를 초과하는 값 중 최초인 수의 인덱스를 구하는 것이다. 이 방식을 사용하는 이유는 특정 수가 해당 배열에 몇개나 존재하는지 구간으로 구하기 위해 특정 수가 존재하는 가장 앞 인덱스와 특정 수보다 큰 수가 존재하는 가장 처음 인덱스를 구하는 것이다. 

이를 이해하는 게 꽤나 오래걸렸는데 좀 더 기억에 오래 남기기 위해 조금 정리하자면, 

lowerBound로직의 경우 구하고자 하는 인덱스를 ans라는 변수로 선언하고 배열의 가장 첫 인덱스인 0을 l값으로, 배열의 마지막 인덱스를 r 값으로 둔다. 그 후 반복문 안에서 기본적인 이분탐색과 동일하게 중앙값 m를 구해주고 배열의 m번째 값과 찾고자하는 값을 비교한다.

그리고 이 분기에서 조금 달라지는데 만약 배열[m] 값이 찾고자하는 값보다 작다면 그 수를 포함한 그 이전의 값들은 lowerBound가 될 수 없기에 l = m+1로 조정한다. 반대로 배열[m] 값이 찾고자 하는 값보다 크거나 같다면 1) 이 값이 찾고자 하는 특정 수 이상 중 최초 값일 수 있기 때문에  ans에 m을 담아주고 2) 최초 값이 아니고 특정 수보다 크지만 이 수보다는 작은 수가 있거나 같은 수가 있을 수 있기 때문에 이를 확인하기 위해 r에 m-1을 담아준다. 

upperBound의 경우 분기의 조건이 조금 다르다. 우리는 지금 찾고자 하는 값을 "초과"하는 최초 값을 찾는 중인데 만약 배열[m]의 값이 찾고자하는 값보다 작거나 같다면, 찾고자하는 값에 해당하지 않기 때문에 l = m+1로 이전 구간을 제외시킨다. 그리고 만약 배열[m] 값이 찾고자 하는 값보다 크다면 최초 값일 수 있기에 ans에 m을 담아주고 다시 이 수보다 작으면서 찾고자 하는 수보다 큰 수가 존재하는지 확인하기 위해 r에 m-1을 담아서 확인하게 한다. 

진짜 정말로 머리가 멈춘 것 같았다. 부디 잘 기억해서 다음 기회에 꼭 사용할 수 있기를 바란다. 아 그리고 내 코드에서는 기본 이분탐색을 먼저 진행한 후에 존재하는 경우에만 bound를 찾으러 가게 시켰다. 굳이 필수는 아니지만 존재하지도 않는 수를 굳이 두번 더 찾을 필요가 없을 것 같아서 추가한 로직이다. 이 문제를 이렇게도 풀 수 있다니 놀랍다. 확실히 카운팅 배열을 사용한 것보다는 메모리와 시간 모두 줄어든 것을 확인할 수 있다. 

 

import java.io.*;
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));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] cardArr = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            cardArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(cardArr);

        //System.out.println(Arrays.toString(cardArr));

        int m = Integer.parseInt(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());

        while (m-- > 0) {
            int thisNum = Integer.parseInt(st.nextToken());
            bw.write(findNum(thisNum, cardArr) + " ");
        }
        br.close();
        bw.flush();
    }

    private static int findNum(int thisNum, int[] cardArr) {

        //System.out.println("=================================");
        //System.out.println("thisNum: " + thisNum);

        int l = 0;
        int r = cardArr.length - 1;

        int ans = 0;

        while (l <= r) {

            int m = (r + l) / 2;

            if (cardArr[m] == thisNum) {
                int start = findLowerBound(cardArr, thisNum);
                int end = findUpperBound(cardArr, thisNum);

                ans = end - start;

                //System.out.println("tempAns: " + ans);
                break;

            } else if (cardArr[m] > thisNum) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    private static int findLowerBound(int[] cardArr, int thisNum) {
        // thisNum이상의 값이 처음 등장하는 곳 찾기
        int l = 0;
        int r = cardArr.length - 1;

        int ans = cardArr.length;

        while (l <= r) {
            int m = (l + r) / 2;

            if (cardArr[m] < thisNum) l = m + 1;
            else { // 지금 값이 기준보다 크거나 같다면
                r = m - 1;
                ans = m;
            }
        }

        return ans;
    }

    private static int findUpperBound(int[] cardArr, int thisNum) {
        // thisNum을 초과하는 값이 최초로 등장하는 곳 찾기
        int l = 0;
        int r = cardArr.length - 1;

        int ans = cardArr.length;

        while (l <= r) {
            int m = (l + r) / 2;

            // 우리는 초과하는 값을 찾는 것인데 같거나 작으면 아얘 필요 없으니 l 옮겨줌
            if (cardArr[m] <= thisNum) l = m + 1;
            else { // 지금 값이 기준보다 크다면
                r = m - 1; // 초과하는 값 중 더 작은 값이 있는지 찾으러가요
                ans = m; // 지금이 초과하는 값 중 최초 값이라면
            }
        }

        return ans;
    }
}