24-05-22 알고리즘 문제 풀이

오늘은 스프링 과제를 조금 더 진행해보고 JPA에 대해서 더 자세히 공부해보았다. 그 내용을 정리하려면 조금 더 시간이 필요할 것 같다.

 

여기에는 오늘 풀어본 알고리즘 문제 풀이 하나를 정리해본다.

 

1. 알고리즘 문제 풀이

leetcode에 있는 '15. 3Sum' 문제를 풀어보았다.

 

1-1. 풀어본 문제

[문제]

정수 배열 nums가 주어졌을 때,  i != j, i != k, j != k 를 모두 만족하고  nums[i] + nums[j] + nums[k] == 0을 만족하는 

[nums[i], nums[j], nums[k]]를 모두 반환하세요

 

솔루션 셋에는 중복된 삼중항이 포함되서는 안됩니다.

 

- 예시 1

입력: nums = [-1, 0, 1, 2, -1, -4]

출력: [[-1, -1, 2], [-1, 0, 1]]

설명:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

중복되지 않는 삼중항은 [-1, 0, 1] 과 [-1, -1, 2] 이다.

출력의 순서와 삼중항의 순서는 상관이 없다.

 

- 예시 2

입력: nums = [0, 1, 1]

출력: []

설명: 가능한 유일한 삼중항은 합이 0이 되지 않습니다.

 

-예시 3

입력: nums = [0, 0, 0]

출력: [[0, 0, 0]]

설명: 가능한 삼중 합은 0뿐입니다.

 

- 제한 사항

• 3 <= nums.length <= 3000
• -100000 <= nums[i] <= 100000

 

1-2. 문제 풀이 방법

먼저 이 문제를 브루트 포스로 풀 수도 있을 것 같았는데, 그 보다 투 포인터를 이용해서 풀이를 해보았다.

 

투 포인터를 이용하려면 먼저 숫자들을 정렬해야 한다. 숫자들을 정렬하면 합을 구한 뒤에 0보다 크면 오른쪽 포인터를 왼쪽으로 이동하고 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동하는 식으로 코드를 작성하면 된다.

 

여기서 아래 빨간 숫자처럼 숫자를 하나씩 증가시키는 식으로 숫자를 하나 지정해주고, 파란색이 왼쪽 포인터 노란색이 오른쪽 포인터로 합이 0이 되는 지점을 찾아가는 식으로 프로그램을 작성하면 세 수의 합을 쉽게 구할 수 있다.

 

0 1 2 3 4 5 6

 

0 1 2 3 4 5 6

 

0 1 2 3 4 5 6

 

아래 코드를 직접 보면 더 이해하기가 쉬울 것이다.

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        var left: Int
        var right: Int
        var sum: Int
        val results: MutableList<List<Int>> = mutableListOf()
        // 숫자들을 정렬한다
        nums.sort()

        for(i in 0..nums.size-3) {
            // i가 같은 수 일때는 건너뛴다
            if (i > 0 && nums[i] == nums[i-1]) continue
            
            left = i + 1
            right = nums.size - 1

            while (left < right) {
                sum = nums[i] + nums[left] + nums[right]

                if (sum < 0) left += 1
                else if (sum > 0) right -= 1
                else {
                    results.add(listOf(nums[i],nums[left],nums[right]))
                    
                    // 중복된 숫자를 건너뛰어야한다
                    while (left<right && nums[left] == nums[left + 1]) left += 1
                    while (left<right && nums[right] == nums[right - 1]) right -= 1

                    left += 1
                    right -= 1
                }

            }
        }
        
        return results
        
    }
}

위와 같이 작성하면 답안이 잘 통과된다. 이런 문제를 만나면 무조건 브루트 포스로 먼저 접근하곤 했었는데 이제 투 포인터에 어느정도 익숙해졌으니 앞으로도 이런 식으로 문제를 풀 수 있을 것 같다.

 

 

2. 오늘 배운 것

- Spring data JPA의 사용법에 대해 조금 더 공부해보았다.

- 연관관계 매핑하는 법을 조금 더 잘 이해하게 되었다.