[LeetCode] 1. Two Sum

문제

leetcode.com/problems/two-sum/

 

잠깐

문제를 간단히 설명하자면 다음과 같습니다.

int 어레이 중 2개의 엘리먼트를 선택하여 그 합이 target인 엘리먼트들을 찾아라. (같은 엘리먼트 사용 불가)

자세한건 구글 번역을 사용해보세요. (크롬 확장 프로그램으로 구글 번역 추천)

해당 문제는 단순 이중 for문으로 구현이 가능합니다. 하지만 더 효율적인 코드를 짜는게 관건이겠죠?

코드

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for firstIndex in 0..<nums.count {
            let needSecondNum = target - nums[firstIndex] 
            for secondIndex in (firstIndex + 1)..<nums.count {
                if nums[secondIndex] == needSecondNum {
                    return [firstIndex, secondIndex]
                }
            }
        }
        return []
    }
}

* 참고로, 속도와 메모리 사용은 사이트 환경에 따라 달라집니다.

설명

순서대로 이중포문을 돌립니다.

로직을 손으로 그려볼까요???

[0,1], [0,2], [0,3]

[1,2], [1,3]

[2,3]

순서대로 합을 구합니다.

그런데, needSecondNum을 구하는게 특이하지 않아요?

코드 최적화 전에는 다음과 같이 구현했어요

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
        	for j in i+1..<nums.count {
        	    if nums[i] + nums[j] == target {
        	        return [i, j]
        	    }
        	}
    	}
        return []
    }
}

근데 해당 코드를 자세히 보세요.

두번째 포문을 도는 동안, nums[i]의 값은 변경되지 않죠??

그럼 매번 어레이에 접근하는것 보다 값으로 가지고 있으면 어떨까요??

또, 매번 더하기(+) 연산을 하고 있죠??

일부 구간동안 변경되지 않는 target과 nums[i]을 이미 알고있습니다.

결국 우리는 필요한 두번째의 숫자를 알고 있어요.

그래서 두번째 숫자를 미리 구하여, 비교합니다.

let needSecondNum = target - nums[firstIndex]

 

 

아래에는 제가 21년 3월에 구현한 코드에요. (Swift)

당시에는 가독성을 높이기 위해, 변수를 일부러 사용했는데, 지금 다시 보니 오히려 코드 가독성이 안좋고 어떤 코드인지 쉽게 파악이 어렵네요;;;;;

변수명을 잘 사용해야겠어요. 반성합니다.

class Solution {

    func twoSum(_ nums: [Int], _ target: Int) ->Int] {
        for i in 0..<nums.count {
            var num = nums[i]
            var minusNum = target - num

            for j in i+1..<nums.count {
                if nums[j] == minusNum {
                    return[i, j]
                }
            }
        }
        return []
    }
}

 

아래는 단순 이중포문 코드입니다.

for i in 0..<nums.count {
    var num = nums[i]
    var minusNum = target - num

    for j in 0..<nums.count {
        if i != j, nums[j] == minusNum {
            return[i, j]
        }
    }
}

하지만, 두번째 for문을 0부터 실행한다면, 이미 탐색하여 불필요한 중복 탐색이 수행됩니다.

비효율적이죠.

그림으로 설명하자면 주황색 화살표가 중복 탐색이네요.

nums[0]과 nums[1]의 비교와 nums[1]과 nums[0]의 비교는 같아요. 그래서 중복 수행 할 필요가 없어요.

따라서 이미 한번 수행한 비교(빨간색)를 두번 수행(주황색)할 필요가 없어요.

 

회고

백준? 오일러?에서 풀어본 문제 같기도 하고, 몸풀기로 쉬운 문제였네요.