LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정수가 든 배열 nums
2. output: size = 3 && 원소의 합이 0이 되는 nums의 부분집합 리턴
3. 리턴하는 부분집합에 중복X
   • 3 <= nums.length <= 3000
   • 105 <= nums[i] <= 105

Idea

완전 탐색으로 풀 경우, n^3 시간초과(27억회)가 될 것이다.

n^3을 최소한 n^2로 변형해야한다 (n^2연산 하나를 n으로)

정렬된 정수 배열에서 조건을 만족하는 원소쌍 찾기를 n^2이 아닌 n으로 해결 → 투포인터

주어진 문제를 몇가지 조작을 통해 투포인터 문제로 변형할 수 있다 → Sol1

Solution

1. 투포인터 문제로 변형

   • 주어진 배열을 정렬
   • 한개의 포인터(시작점)를 고정하여 투포인터만 조작

   class Solution {
       fun threeSum(nums: IntArray): List<List<Int>> {
           val answer = mutableSetOf<List<Int>>()
           nums.sort() // 정렬
           for (firstIdx in 0 until nums.size - 2) { // 시작점 고정
               if (nums[firstIdx] > 0) return answer.toList()
   						// 투포인터
               var left = firstIdx + 1
               var right = nums.size - 1
               var sum = nums[firstIdx] + nums[left] + nums[right]
               while (left < right) {
                   if (right < 0) break
                   if (sum == 0) {
                       answer.add(listOf(nums[firstIdx], nums[left], nums[right]))
                       left++
                       right--
                   } else if (sum < 0) {
                       left++
                   } else {
                       right--
                   }
                   sum = nums[firstIdx] + nums[left] + nums[right]
               }
           }
           return answer.toList()
       }
   }
   

   시간 복잡도: 배열 순회(시작점) X 배열 순회(투포인터) = n^2

   

Point

1. 문제를 완전탐색으로 풀었을 때의 시간 복잡도를 보고 발전시킬 수 있는 부분을 찾는 습관
2. 알고 있는 유형의 문제로 변환시킬 수 있는 능력 중요