24-06-11 알고리즘 문제 풀이

오늘부터 새로운 프로젝트가 시작되는 날이었다. 지난 번 프로젝트 때 아쉬웠던 부분을 잘 보완해서 이번 프로젝트에 적용해보고 싶었는데 오늘 하루 그런 부분들도 잘 이루어진것 같고 하루를 잘 알차게 보낼 수 있었던 것 같다.

 

여기에는 알고리즘 문제 푼 것 하나를 정리해보았다.

 

1. 알고리즘 문제 풀이

오늘은 leetcode에 있는 '973. K Closest Points to Origin' 문제를 풀어보았다.

1-1. 풀어본 문제

[문제]

points[i]가 X-Y평면의 [xi, yi]의 한 점을 나타내는 points라는 배열과 k라는 정수가 주어졌을 때, 원점 (0,0)에서 가장 가까운 k개의 점을 반환하세요.

 

X-Y 평면에서의 두 점 사이의 거리는 유클리드 거리(예시, $\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}$ )입니다.

 

답은 순서와 상관없이 반환해도 괜찮습니다. 답은 고유함이 보장됩니다. (순서는 제외하고)

 

- 예시 1

 

입력: points = [[1, 3], [-2, 2]], k = 1

출력: [[-2, 2]]

설명: (1,3)과 원점 사이의 거리는 √10 입니다. (-2, 2)와 원점 사이의 거리는 √8입니다. √8 < √10 이기 때문에, (-2, 2)가 더 원점과 가깝습니다. 원점에서 가장 가까운 k = 1 만큼의 점만 구하면 되기 때문에, 답은 [[-2, 2]] 입니다.

 

- 예시 2

입력: points = [[3, 3], [5, -1], [-2, 4]], k = 2

출력: [[3, 3], [-2, 4]]

설명: [[-2, 4], [3, 3]] 역시 답으로 통과됩니다.

 

-제한 사항

• $1 {\;}{\leq}{\;} k {\;}{\leq}{\;} points.length {\;}{ \leq}{\;}10^{4}$
• $-10^{4} {\;}{\leq}{\;}   x_{i}, {\;} y_{i} {\;}{ \leq}{\;}10^{4}$

 

1-2. 문제 풀이

먼저 문제 풀이 이전에 우선순위 큐라는 것에 대해 조금 공부하게 되었었다. 그래서 이 문제를 풀게 되었고 우선순위 큐를 이용해서 문제를 풀어보았다.

 

먼저 우선순위 큐를 하나 선언해주었다. 큐에는 Pair<Int, IntArray>가 들어가게 되는데 Int는 거리를, IntArray는 좌표가 들어가게 된다.

 

유클리드 거리의 경우는 x제곱과 y제곱을 합한다음에 제곱근을 구하게 된다. 하지만 우리는 거리가 필요한 것이 아니라 거리가 가까운 것만 구하면 되기 때문에 굳이 제곱근을 씌워줄 이유가 없다.

 

주어진 제약조건 하에서 원점에서 가장 멀리 떨어진 점의 x제곱과 y제곱의 합은 20억이다. 따라서 Int의 범위를 넘어서지 않기 때문에 오버플로우가 발생하지 않는다.

 

그렇기 때문에 거리의 경우는 그냥 x제곱과 y제곱의 합으로 구하였다.

 

우선순위 큐에는 이렇게 구한 거리를 비교하는 비교기를 넣어주었다.

 

모든 점들에 대해 거리를 구한 다음 우선순위 큐에 하나씩 넣어주고나서 마지막에 k만큼 우선순위 큐에서 뽑아내기만 하면 된다.

 

아래는 위의 아이디어들을 코드로 옮긴 것이다.

class Solution {
    fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
        // 우선순위 큐 선언
        val priorityQue: Queue<Pair<Int,IntArray>> = PriorityQueue(compareBy { it.first })

        for (point in points) {
            // 거리 구하기
            val distance = point[0]*point[0] + point[1]*point[1]
            // 우선순위 큐에 거리와 좌표 넣기
            priorityQue.add(distance to point)
        }
        // 답이 될 빈 배열 미리 선언하기
        val answer = Array(k) { IntArray(2) }
        
        // 배열에 우선순위 큐에서 k개 만큼 뽑아 집어넣기
        for (i in 0..<k) {
            answer[i] = priorityQue.poll().second
        }

        return answer
    }
}

위와 같이 코드를 작성하면 답안으로 잘 통과된다.

 

우선순위 큐를 활용하는 법에 대해서는 잘 알게 되었지만 어떻게 작동하는지 그 내부 알고리즘은 생각보다 이해하기가 어려웠다. 시간이 되면 조금 더 자세히 공부해보아야겠다. 

 

2. 오늘 배운 것

- 이벤트 스토밍, ERD 작성, API 명세서 작성까지 실제 프로젝트 코드 작성에 들어가기에 앞서 정해야할 것들을 오늘 잘 정해둔 것 같다. 내일 부터는 마음 편히 코드 작성에 집중할 수 있을 것 같다.

- 우선 순위 큐를 활용해볼 수 있었다.