Coding Interview - 1

Coding Interview - 1

문제

정수 배열 a 와 b 가 주어졌을때, a 와 b 에서 각각 하나씩 집은 뒤 더해서 v 를 만들 수 있으면 true 를 리턴하고, 아니면 false 를 리턴해라

## CASE1
a = [1, 2, 3]
b = [10, 20, 30, 40]

v = 42

## CASE2
a = [0,0,-5,30212]
b = [-10, 40, -3, -9]

Solution (Brute-Force)

fun solution(a: IntArray, b: IntArray, v: Int): Boolean {
    for (firstNum in a) {
        val meetsCondition = v - firstNum
        for (secondNum in b) {
            if (meetsCondition == secondNum) {
                return true
            }
        }
    }    
    return false
}

• 가장 간단한 방법으로는 위와 같은 방법으로 문제를 해결 할 수 있다. Brute-Force 알고리즘으로, 가능한 각 모든 수를 판단하여 문제를 찾는 간단한 방법이다.
• 현재 시간 복잡도는 O(N^2) | 공간 복잡도는 O(1) 에 해당한다.

Optimization

fun solution(a: IntArray, b: IntArray, v: Int): Boolean {
	val record = mutableMapOf<Int, Int>()
	saveRecord(a, v, record)
	saveRecord(b, v, record)

	for (ele in a) {
		val value = record[ele]
		
		if (record.contains(value)) {
			return true
		}
	}


	return false
}

fun saveRecord(arr: IntArray, v: Int, record: MutableMap<Int, Int>) {
	for (ele in arr) {
		record.put(ele, v - ele)
	}
}

• 어떻게 Optimization 을 할 수 있을까? 생각하다가 내 경우에는 Map Data Structure 를 이용하는 방법을 선택했다. 그 이유는, 저장하는데 걸리는 시간 복잡도: O(N), 추가 공간 저장: O(N) 의 공간복잡도만 사용하기 때문이다. Map 에서 Data 를 Search 하는데, O(1) 시간이 걸리므로 기존보다 빠르게 값을 찾을 수 있다고 생각했다.

Comment

나는 Map 을 썼지만, 답안 중 다른 사람들은 HashSet 을 쓰는 경우가 많았다.