2025-동계 모각코 4회차 회고

이전에 '2467번: 용액' 문제를 풀었던 경험이 있다.

2467번은 두 용액의 합의 절댓값을 최대한 0에 가깝게 하는 문제였는데, 이번 문제는 용액의 개수가 세 개로 늘어났다는 차이점이 있다. 또한, 입력의 크기(용액 개수)도 100,000에서 5,000으로 줄어들었다.

여기서, 문제를 푸는 알고리즘은 크게 차이가 없음을 직감했다.

처음엔 투 포인터를 구현하여 인덱스 두 개를 고정해놓고, 그 사이의 인덱스를 하나 정해 절댓값을 비교하는 방식을 채택하려 했었다.

그러나 중간부터 구현 난이도가 올라 난관에 봉착했고, 인덱스 하나를 고정한 뒤 나머지 인덱스들을 투 포인터로 구현하는 방식으로 문제를 해결했다.

용액 특성값의 절댓값이 1,000,000,000까지 가능했는데, 용액 3개를 합치면 30억에 근접하는 경우가 있을 수도 있음을 고려하지 못해 39%에서 오답처리를 당했으며, 자료형을 int에서 long으로 수정함으로써 통과할 수 있었다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        long[] arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Long.parseLong(st.nextToken());

        Arrays.sort(arr);

        long bestAbs = Long.MAX_VALUE;
        long ans1 = 0;
        long ans2 = 0;
        long ans3 = 0;
        
        for (int fixed = 1; fixed <= n - 2; fixed++) {
            int left = 0;
            int right = n - 1;

            while (left < right) {
                if (left == fixed) { left++; continue; }
                if (right == fixed) { right--; continue; }

                long sum = arr[left] + arr[fixed] + arr[right];
                long abs = Math.abs(sum);

                if (abs < bestAbs) {
                    bestAbs = abs;
                    ans1 = arr[left];
                    ans2 = arr[fixed];
                    ans3 = arr[right];
                    if (bestAbs == 0) break;
                }

                if (sum < 0) left++;
                else right--;
            }
            if (bestAbs == 0) break;
        }
        
        long[] out = {ans1, ans2, ans3};
        Arrays.sort(out);
        System.out.println(out[0] + " " + out[1] + " " + out[2]);
    }
}

저번 주 자료구조 초급 특강에서 진도를 나가지 못하고, 자료만 제공 받았던 '해시 자료구조'를 직접 구현해보았다.

해시의 개념, 동작 원리, 해시 함수의 종류와 원리, 충돌이 발생하는 경우와 이를 해결하기 위한 이상적인 방지 기법을 배우고 직접 선형 조사 방식의 해시 자료구조를 구현해보았다.

public class LinearProbing <K, V> {

    private int m = 11;
    private K[] a = (K[]) new Object[m];
    private V[] d = (V[]) new Object[m];

    private int hash(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % m;
    }

    public void put(K key, V value) {
        int initialpos = hash(key);
        int i = initialpos;
        int j = 1;
        do {
            if (a[i] == null) {
                a[i] = key;
                d[i] = value;
                return;
            }
            if (a[i].equals(key)) {
                d[i] = value;
            }
            i = (initialpos + j++) % m;
        } while (i != initialpos);
    }

    public V get(K key) {
        int initialpos = hash(key);
        int i = initialpos;
        int j = 1;
        while (a[i] != null) {
            if (a[i].equals(key)) {
                return d[i];
            }
            i = (initialpos + j++) % m;
        }
        return null;
    }

    public void print() {
        System.out.println("Hash Table: ");
        for (int i = 0; i < m; ++i) {
            System.out.printf("\t%2d", i);
        }
        System.out.println();
        for (int i = 0; i < m; ++i) {
            System.out.print("\t" + a[i]);
        }
        System.out.println();
        for (int i = 0; i < m; ++i) {
            System.out.print("\t" + d[i]);
        }
    }
}

이차 조사, 랜덤 조사, 이중 해싱 등의 방식들은 선형 조사 방식의 해시 테이블을 부분 수정하여 구현할 수 있으므로 따로 코드를 적지는 않았다.