23.04.17. programmers 코딩테스트 문제 풀기[4]

두 개 뽑아서 더하기 문제

 

정수 배열 numbers가 주어질 때, numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성하는 문제다.

제한사항으로는 numbers의 길이는 2 이상 100 이하이고, numbers의 모든 수는 0 이상 100 이하이다.

입출력 예
numbers, result
[2,1,3,4,1], [2,3,4,5,6,7]

입출력 예 설명
2 = 1 + 1  (1이 numbers에 두 개)
3 = 2 + 1
4 = 1 + 3 
5 = 1 + 4 = 2 + 3 
6 = 2 + 4 
7 = 3 + 4 
따라서 [2,3,4,5,6,7] 을 return 

 

우선 문제와 제한사항, 입출력 예시를 살펴보고, 예외 케이스와 처리방법을 생각해보자. 제한사항에서 정수가 중복되지 않는다는 이야기가 없고, 수는 0일 수도 있다. 극단적으로 [0, 0] 이런게 들어올 수 있다는 뜻. 

 

그리고, 만들 수 있는 모든 수를 배열에 오름차순으로 담아야 하는데, 만들 수 있는 모든 수를 중복해서 담을 수 있는지에 대해서는 입출력 예 설명에서 중복을 제거하는 것으로 설명하고 있기 때문에 제거해줘야 한다.

 

내가 생각한 방법은 재귀함수를 사용하는 건데,

1. shift로 배열의 가장 앞 요소를 하나 빼서,

2. 뺀 나머지 배열의 각 요소에 더해준 다음

3. 더해진 배열과 shift로 요소 하나를 뺀 배열로 같은 계산을 반복하도록 함수를 재귀적으로 호출하는 것

4. 이때, 삼항연산자로 numbers의 length가 0이 될 때 마지막으로 더한 배열만 반환하도록 해서 재귀호출을 끝낸다. 

5  마지막으로 중복제거를 위해 Set으로 정의해주고 다시 배열로 바꾼 다음, 오름차순으로 정렬.

 

작성한 코드는,

function solution(numbers) {
    let first = numbers.shift()
    let res = numbers.map(num => first + num)
    return [...new Set(numbers.length > 1 ? [...res, ...solution(numbers)] : res)].sort()
}

console.log(solution([2, 1, 3, 4, 1])) // [ 2, 3, 4, 5, 6, 7 ]

설명해보면, 

 

우선 first에 numbers에서 shift된 가장 앞 요소를 넣어두고,

res 에는 map 메서드로 numbers의 가장 앞 요소가 빠진 배열에 first를 더해서 반환한다.

그 다음 return으로 가서, numbers의 길이가 1 이상이므로, [...res, ...solution(numbers)]에서, 다시 solution 함수가 호출되는데, 이때 numbers 인자는 shift로 가장 앞 요소가 빠진 numbers이다. 

 

계속 반복하면 shift로 다 빠져서, numbers.length가 0이 될 것이고, 그때는 res만 return되도록 되는 것으로 재귀호출이 끝난다.

 

과정을 내가 이해하는 방식으로 풀어 써 보면,

 

// 원래 함수와 달리, 재귀함수 설명을 쉽게하기 위해 아래와 같이 함수 변경
function solution(numbers) {
    let first = numbers.shift()
    let res = numbers.map(num => first + num)
    return numbers.length > 1 ? [...res, ...solution(numbers)] : res
}

console.log(solution([2, 1, 3, 4, 1]))

// 입력 numbers 가 [2,1,3,4,1] 일 때,

// 1번째 solution(numbers): 
numbers = [2,1,3,4,1] // 입력 값
first = 2
numbers = [1,3,4,1] // shift 후
res = [2+1, 2+3, 2+4, 2+1] 
numbers.length > 1 // 4, true
return [...[2+1, 2+3, 2+4, 2+1], ...solution([1,3,4,1])]

// 2번째 solution(numbers): 
numbers = [1,3,4,1] // 입력 값
first = 1
numbers = [3,4,1] // shift 후
res = [1+3, 1+4, 1+1]
numbers.length > 1 // 3, true
return [...[1+3, 1+4, 1+1], ...solution([3,4,1])]
// 누적 return은 [...[2+1, 2+3, 2+4, 2+1], ...[1+3, 1+4, 1+1], ...solution([3,4,1])]

// 3번째 solution(numbers):
numbers = [3,4,1] // 입력 값
first = 3
numbers = [4,1] // shift 후
res = [3+4, 3+1]
numbers.length > 1 // 2, true
return [...[3+4, 3+1], ...solution([4,1])]
// 누적 return은 [...[2+1, 2+3, 2+4, 2+1], ...[1+3, 1+4, 1+1], ...[3+4, 3+1], ...solution([4,1])]

// 4번째 solution(numbers):
numbers = [4,1] // 입력값
first = 4
numbers = [1] // shift 후
res = [4+1]
numbers.length > 1 // 1, false
return [4+1]
// 누적 return은 [...[2+1, 2+3, 2+4, 2+1], ...[1+3, 1+4, 1+1], ...[3+4, 3+1], ...[4+1]]

// callback 되며 누적된 return은 결과적으로, 
[...[2+1, 2+3, 2+4, 2+1], ...[1+3, 1+4, 1+1], ...[3+4, 3+1], ...[4+1]] // 으로 된다. 
// spread로 표현했으니, 다시 배열로 바꾸고, 더하기를 한 결과로 표현하면

return [3, 5, 6, 3, 4, 5, 2, 7, 4, 5] 가 된다.

// 그 다음 위 배열의 중복을 제거하기 위해,
[...new Set([3, 5, 6, 3, 4, 5, 2, 7, 4, 5])] 
// 처리 해 주고, 중복제거된 배열을 sort()하면 원하는 결과를 얻는다.

실제 함수에는 return값에 Set()안에 삼항연산자로 재귀함수 호출을 했으니,

매번의 함수 실행 시 return할 때 중복제거를 해주고 정렬도 하니 비효율적인 코드인 것. 재귀함수 연습이니까...

 

실제로는 

// 이 함수 기준으로는 return을 풀어보면,
function solution(numbers) {
    let first = numbers.shift()
    let res = numbers.map(num => first + num)
    return [...new Set(numbers.length > 1 ? [...res, ...solution(numbers)] : res)].sort()
}

// 입력 numbers 가 [2,1,3,4,1] 일 때,

// 1번째 solution(numbers): 
numbers = [2,1,3,4,1] // 입력 값
first = 2
numbers = [1,3,4,1] // shift 후
res = [2+1, 2+3, 2+4, 2+1] 
numbers.length > 1 // 4, true
return [...new Set( [...[2+1, 2+3, 2+4, 2+1], ...solution([1,3,4,1])] )].sort()

// 2번째 solution(numbers): 
numbers = [1,3,4,1] // 입력 값
first = 1
numbers = [3,4,1] // shift 후
res = [1+3, 1+4, 1+1]
numbers.length > 1 // 3, true
return [...new Set( [...[1+3, 1+4, 1+1], ...solution([3,4,1])]) ].sort()

// 3번째 solution(numbers):
numbers = [3,4,1] // 입력 값
first = 3
numbers = [4,1] // shift 후
res = [3+4, 3+1]
numbers.length > 1 // 2, true
return [...new Set( [...[3+4, 3+1], ...solution([4,1])]) ].sort()

// 4번째 solution(numbers):
numbers = [4,1] // 입력값
first = 4
numbers = [1] // shift 후
res = [4+1]
numbers.length > 1 // 1, false
return [...new Set( [4+1] )].sort()

// return ------------------------------------------------------------------

// 4번째 return:
return [...new Set( [5] )].sort()
return [...{5}].sort()
return [5].sort()
return [5]

// 3번째 return:
return [...new Set([...[7, 4], ...[5]])].sort()
return [...new Set([7,4,5])].sort()
return [...{7,4,5}].sort()
return [7,4,5].sort()
return [4,5,7]

// 2번째 return:
return [...new Set([...[4, 5, 2], ...solution([3,4,1])])].sort()
return [...new Set([...[4, 5, 2], ...[4,5,7]])].sort()
return [...new Set([4, 5, 2, 4,5,7])].sort()
return [...{4, 5, 2, 7}].sort()
return [4, 5, 2, 7].sort()
return [2, 4, 5, 7]

// 1번째 return:
return [...new Set([...[3, 5, 6, 3], ...solution([1,3,4,1])])].sort()
return [...new Set([...[3, 5, 6, 3], ...[2, 4, 5, 7])].sort()
return [...new Set([3, 5, 6, 3, 2, 4, 5, 7])].sort()
return [...{3, 5, 6, 2, 4, 7}].sort()
return [3, 5, 6, 2, 4, 7].sort()
return [2, 3, 4, 5, 6, 7]

 

이런 과정을 통해 계산된다.