[Do it! 알고리즘 코딩 테스트 자바] 백준 17298번 오큰수 / 11286번 절댓값 힙(6일차)

백준 17298번(오큰수)

1. 주요 오개념 및 시행착오 (Pain Point)

• O(N^2) 완전 탐색 접근으로 인한 시간 초과 발생.
• 배열을 [인덱스, 값] 형태로 미리 오름차순 정렬하여 접근하려 했으나, '오른쪽에 있으면서 가장 가까운'이라는 위치 조건을 만족시키기 위해 반복문 내부에서 추가 탐색이 발생하여 시간 복잡도 최적화에 실패함.
• 정답 도출 로직이 완벽하더라도 System.out.print를 반복 호출하면 입출력 병목으로 인해 1초의 시간 제한을 통과할 수 없음을 인지하지 못함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 단조 스택(Monotonic Stack) 알고리즘 적용. 스택 내부에 아직 오큰수를 찾지 못한 원소들을 대기시키고, 새로 들어온 값이 스택 맨 위(top) 원소보다 클 때만 스택에서 제거(pop)함.
• 분할 상환 분석(Amortized Analysis)에 따라, 배열의 모든 원소는 스택에 최대 한 번 삽입(push)되고 최대 한 번 삭제(pop)됨. 이중 반복문 형태를 띠더라도 총 연산 횟수는 2N에 수렴하여 전체 O(N)의 시간 복잡도를 보장함.

3. 설계 통찰

• 값 대신 인덱스를 스택에 저장하는 구조. 인덱스를 보관함으로써 원본 배열의 값을 비교하는 동시에, 정답 배열(result)의 정확한 위치에 오큰수를 기록하는 작업을 한 번에 처리함.
• 동기적 사고에서 비동기적(이벤트 주도) 사고로 패러다임 전환. 매번 정답을 직접 찾으러 순회하는 것이 아니라, 조건(나보다 큰 수)이 나타나는 이벤트가 발생할 때까지 대기열에서 보류하는 방식으로 불필요한 연산을 제거함.

4. 구현상의 유의점 (Implementation Wisdom)

• 대규모 데이터 출력 시 BufferedWriter 사용 필수. 100만 개의 결과를 버퍼에 모아 한 번에 출력하여 입출력 오버헤드를 극복함.
• Stack 클래스 대신 ArrayDeque 활용. 기존 Stack 클래스는 멀티스레드 환경을 위한 동기화(synchronized) 처리가 되어 있어 단일 스레드 알고리즘 풀이 시 불필요한 성능 저하를 유발하므로, ArrayDeque를 스택으로 사용하여 실행 속도를 극대화함.

 

---

백준 11286번(절댓값 힙)

1. 주요 오개념 및 시행착오 (Pain Point)

• PriorityQueue 선언 시 사용자 정의 정렬 조건(Comparator)을 부여하는 문법과 람다식 활용법에 대한 초기 인지 부족.
• 우선순위 규칙 구현 시 Math.abs() 차이를 직접 계산하고 Math.toIntExact()로 형변환을 시도했으나, if 조건문(absA > absB) 설계의 논리적 허점으로 인해 음수 케이스에서 절댓값이 큰 수가 우선순위를 가지는 오류 발생.
• 정렬 조건 선언 문법을 제외한 나머지 데이터 삽입 및 예외 처리(0 입력 시 출력) 로직은 성공적으로 구현함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 힙(Heap) 트리 구조를 기반으로 데이터의 삽입과 삭제를 O(log N)에 처리하여 최솟값/최댓값을 빠르게 도출함.
• 다중 조건 정렬의 수학적 모델링 적용. 1순위로 두 수의 절댓값을 비교하고, 절댓값이 같을 경우 2순위로 실제 값을 비교하는 계층적 비교 연산 수행.

3. 설계 통찰

• 조건문 내부에서 1순위 조건(절댓값 차이 존재)이 완전히 분별된 경우(absA != absB)와 그렇지 않은 경우를 명확히 분리하여 논리적 예외 발생을 차단함. 이때, absA > absB의 조건을 absA != absB으로 바꿈으로서 큰 경우와 작은 경우 모두 대비함.
• 직접 뺄셈(a - b) 연산 대신 자바 내장 함수인 Long.compare()를 활용하여, 수의 범위를 초과할 때 발생하는 자료형 오버플로우 위험을 원천 차단하고 코드의 가독성을 높임.

4. 구현상의 유의점 (Implementation Wisdom)

• 우선순위 큐 초기화 시 람다식 (a, b) -> { ... }을 사용하여 간결하게 커스텀 정렬 규칙을 큐 내부에 주입함.
• 큐가 비어있을 때 요소를 무작정 pop() 하려 하면 NullPointerException이 발생할 수 있으므로, isEmpty() 검사를 선행하여 문제 조건에 맞게 0을 출력하는 안전한 분기 처리 구현.
• 대량의 입력을 받아 조건에 따라 즉각 출력해야 하므로 BufferedReader와 BufferedWriter를 조합하여 입출력 효율 유지.

 

우선순위 큐 구현 방식

PriorityQueue<Long> pq = new PriorityQueue<>((a, b) -> {
    long absA = Math.abs(a);
    long absB = Math.abs(b);

    if (absA != absB) {
        // 1. 절댓값이 다르면 절댓값끼리 비교 (작은 것이 앞으로)
        return Long.compare(absA, absB);
    }
    // 2. 절댓값이 같으면 실제 값끼리 비교 (작은 것이 앞으로)
    return Long.compare(a, b);
});

 

뺄셈 연산 시 오버플로우 주의: return a - b 방식은 값이 너무 크거나 작으면(음수/양수 끝값) 계산 결과가 이상할 수 있음

-> 타입.compare는 내부적으로 두 값을 비교해 -1, 0, 1 중 하나인 int를 반환하므로 별도의 형변환이 필요 없음

 

비교 원칙:

• 결과값이 음수: 첫 번째 인자가 더 작다고 판단 (앞으로 이동)
• 결과값이 0: 두 인자가 같다고 판단
• 결과값이 양수: 첫 번째 인자가 더 크다고 판단 (뒤로 이동)