onlybooks/java-algorithm-interview

<자바 알고리즘 인터뷰 with 코틀린> 102가지 알고리즘 문제 풀이로 완성하는 코딩 테스트

java-algorithm-interview's Issues

책에 대한 문의는 이곳에 공개 질문으로 등록해주세요.

책에 대한 문의는 보다 많은 분에게 도움이 될 수 있도록 이곳에 공개 질문으로 등록해주세요.
감사합니다.

p.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)

제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.

p.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)에 질문이 있어 문의 드립니다.

풀이1, 3 모두 언어의 차이(java, kotlin)만 있을 뿐, 모두 이중 구조 방식으로 풀이하고 있습니다.
하지만 값을 추출한 후, 대응하는 다른 힙의 엘리먼트를 삭제하는 과정이 비효율적이라고 생각합니다.
=> 최대값 추출의 경우, 최대힙에서 최대값을 추출 후, 해당 값을 최소힙에서 remove() 메서드를 통해 제거
=> 최소값 추출의 경우, 최소힙에서 최소값을 추출 후, 해당 값을 최댜힙에서 remove() 메서드를 통해 제거

우선순위 큐의 이점은 최대값과 최소값 추출을 O(log n)에 수행하여 완전탐색 O(n)에 비해 빠르다는 것이지만,
이후, remove() 메서드를 사용하면 결국 시간복잡도 O(n)의 연산으로 우선순위 큐를 사용하는 의미가 사라집니다.

전체 엘리먼트 관리를 아래와 같이 전체 엘리먼트 개수로 하게 되면, 값 추출의 시간복잡도가 O(log n)이 됩니다.

import java.util.*

class Solution {
    fun solution(operations: Array<String>): IntArray {
        // 우선순위 큐 선언, 자바 기본은 최소 힙이므로 최대 힙으로 정렬 지정
        val minHeap: Queue<Int> = PriorityQueue()
        val maxHeap: Queue<Int> = PriorityQueue(Collections.reverseOrder())
        var totalCnt = 0
        // 명령어 목록을 하나씩 순회하면서 해당하는 작업 수행
        operations
            .map { it.split(" ") }
            .forEach { op ->
                // 삽입 연산
                when (op[0]) {
                    "I" -> { // 추출 연산
                        minHeap.add(op[1].toInt())
                        maxHeap.add(op[1].toInt())
                        totalCnt++
                    }

                    "D" -> { // 삭제 연산
                        if (totalCnt > 0) {
                            when (op[1]) {
                                // 값이 1인 경우 최댓값 추출
                                "1" -> maxHeap.poll()
                                // 값이 -1인 경우 최솟값 추출
                                "-1" -> minHeap.poll()
                            }
                            if (--totalCnt == 0) {
                                maxHeap.clear()
                                minHeap.clear()
                            }
                        }
                    }
                }
            }

        // 최종결과인 최댓값과 최솟값을 추출하고 값이 없다면 0, 아니라면 해당 값으로 리턴
        return intArrayOf(
            maxHeap.poll() ?: 0,
            minHeap.poll() ?: 0
        )
    }
}

검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.

7번의 두 수의 합(Two Sum) 에서 투 포인터로 풀 경우 Wrong Answer가 발생합니다.

Case1, 2, 3 중 Case 2번에서 답이 틀리다고 나옵니다!

p.g. 490의 '풀이 1 다익스트라 알고리즘 구현'

제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.

p.g. 490의 '풀이 1 다익스트라 알고리즘 구현'의 풀이에 질문이 있어 문의 드립니다.

본 풀이는 격자 모양을 사방이 거리 1인 노드로 연결된 그래프로 두고, 다익스트라 알고리즘으로 해결하고 있습니다.
하지만 이는 적절하지 않은 풀이입니다.

각 노드 사이의 거리가 1이기 때문에, 다익스트라 알고리즘으로 풀었을 때의 아무런 이점이 없습니다.
동작 방식이 아래의 BFS코드와 완전히 동일하며, 유일한 차이는 우선순위큐의 유무이지만 우선순위큐를 사용하는 것이 아래의 이유로 손해입니다.

• 특정 노드와 연결된 모든 모든 노드와의 거리가 동일하기 때문에 탐색의 우선순위가 없습니다.
• 우선순위 큐를 사용하면 다음 탐색 후보 노드 삽입과 탐색 노드 추출에서 O(log n)으로 오히려 손해를 보게됩니다.
  (BFS 풀이에서는 queue를 사용하므로 이과정이 O(1))

아래와 같은 BFS 풀이가 더 적절한 풀이라고 생각합니다.

import java.util.*;

class Solution {
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(int[][] maps) {
        return bfs(maps);
    }

    public int bfs(int[][] maps) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});
        maps[0][0] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curX = current[0];
            int curY = current[1];
            int depth = current[2];
            if (curX == maps.length - 1 && curY == maps[0].length - 1) {
                return depth;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (nextX >= 0 && nextX < maps.length && nextY >= 0 && nextY < maps[0].length && maps[nextX][nextY] == 1) {
                    maps[nextX][nextY] = 0;
                    queue.add(new int[]{nextX, nextY, depth + 1});
                }
            }
        }
        return -1;
    }
}

실제 프로그래머스의 효율성 테스트 결과 역시 차이가 있음을 확인하였습니다.

1. 책에 기재된 다익스트라 풀이 코드
   

2. BFS 풀이
   

검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.