[Kotlin] 삼총사 (프로그래머스 알고리즘)

 

 

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131705

 

 

 

---

 

접근

 

• 주어진 number 배열의 원소 중 합쳤을 때 0이 되는 세 쌍의 개수를 리턴하는 문제다.
• 반복문을 여러 개 써서 앞의 수를 더하는 배열에 넣고, 앞의 수보다 적은 두번째 값을 찾아 더하고, 남은 값과 같은 세번째값을 더하고, 배열에서 해당 1/2/3번째 값을 삭제 뒤(중복 제외) count++ 를 하는 방식 정도로밖에 생각이 안 난다.
• 머리가 아예 안 돌아가는 문제다. 이 문제를 해결하기 위한 효율적인 함수가 있을까?
• 문제를 잘못 봤다! 중복 구성이 가능한 문제였다.

 

 

---

 

성공 코드

 

class Solution {
    fun solution(number: IntArray): Int {
        
    var answer = 0
    for(i in 0 until number.size - 2){
        for (j in i+1 until number.size - 1){
            for (k in j+1 until number.size){
                if(number[i] + number[j] + number[k] == 0) answer ++
            }
        }
    }
    return answer   
    }
}

 

---

 

설명

딱히 다른 함수를 사용하여 풀이하는 문제가 아니었다. 삼중 조건문을 이용하여 풀 수 있었다.
다른 사람들의 풀이를 보면서 '저렇게 구현하면 세 쌍을 구현할 때 중복된 원소가 들어가는 게 아닌가?' 의문이 들었는데, 애초에 중복이 가능한 문제였다. 발문을 제대로 보자.

 

1. 첫 번째 수는 인덱스 0부터 뒤에서 2번째까지 반복한다.
2. 두 번째 수는 인덱스 첫 번째 수+1부터 뒤에서 1번째까지 반복한다.
3. 세 번째 수는 인덱스 두 번째 수+1부터 맨 끝까지 반복한다.
4. 이렇게 3중 for문을 구성하며 세 수를 합쳐서 0이 될 때마다 answer의 숫자를 1개씩 올린다.
5. 모든 for문이 완료되었으면 answer를 리턴한다.

 

여전히 남은 궁금증이 있다.

• (1) 만약 중복된 원소로 쌍을 만들 수 없을 땐 어떻게 구현하는가?
• (2) 일반적으로 알려진 클린코드를 위한 depth는 최대 2이다. 이 문제에서는 depth를 어떻게 줄여야 할까?

 

 

(1) 중복되지 않은 원소로만 조합하기

fun funSolution(number: IntArray): Int {
    var answer: Int = 0
    val sumMap = HashMap<Int, HashSet<Pair<Int, Int>>>()

    for (i in 0 until number.size - 1) {
        for (j in i + 1 until number.size) {
            val sum = number[i] + number[j]
            val pair = Pair(number[i], number[j])
            if (sumMap.containsKey(-sum)) {
                val pairs = sumMap[-sum]!!
                for (existingPair in pairs) {
                    if (existingPair.first != number[i] && existingPair.second != number[i] &&
                        existingPair.first != number[j] && existingPair.second != number[j]
                    ) {
                        answer++
                    }
                }
            }
            sumMap.computeIfAbsent(sum) { HashSet() }.add(pair)
        }
    }

    return answer
}

• 가장 간단한 방법은 이미 계산한 조합을 저장하고 다시 계산하지 않도록 하는 것이다.
  이를 위해 이미 계산한 조합을 저장하는 HashSet이나 HashMap을 사용할 수 있다.
• 이 코드는 먼저 두 원소의 합을 계산하고, 이를 Key로 해시맵에서 찾는다.
  만약 해당 합의 반대값이 이미 해시맵에 있는 경우, 그 합을 만들 수 있는 원소들의 조합을 찾는다.
  그리고 이를 통해 세 개의 원소로 구성된 조합을 찾게 된다.
• 아직 자세히는 모르겠지만, 이런 방법이 있다 정도로 찾아보았다.

 

 

(2) Depth 낮추기

• 다른 사람의 풀이도 딱히 depth를 낮춘 게 보이지 않는다.
  이 문제의 정답을 구현하기 위해선 필연적으로 높은 depth가 필요한 걸까?

 

 

---

 

다른 방법

 

class Solution {
    fun solution(number: IntArray) = number.indices.sumOf { i1 ->
        (i1 + 1 until number.size).sumOf { i2 ->
            (i2 + 1 until number.size).count { i3 ->
                number[i1] + number[i2] + number[i3] == 0
            }
        }
    }
}

• number.indices
  - number 배열의 인덱스 범위를 반환한다. 이는 0부터 number.size - 1까지의 범위를 나타낸다.
• sumOf { i1 -> ... }
  - 첫 번째 인덱스 i1에 대한 인덱스 범위의 합을 계산한다. 이 합은 두 번째 고차 함수 내에서 사용된다.
• (i1 + 1 until number.size)
  - 첫 번째 인덱스 i1 다음부터 number 배열의 끝까지의 인덱스 범위를 반환한다.
• sumOf { i2 -> ... }
  - 두 번째 인덱스 i2에 대한 인덱스 범위의 합을 계산한다. 이 합은 세 번째 고차 함수 내에서 사용된다.
• (i2 + 1 until number.size)
  - 두 번째 인덱스 i2 다음부터 number 배열의 끝까지의 인덱스 범위를 반환한다.
• count { i3 -> ... }
  - 세 번째 인덱스 i3에 대한 조건을 만족하는 요소의 개수를 반환한다.
• number[i1] + number[i2] + number[i3] == 0
  선택한 세 개의 숫자의 합이 0이 되는지 확인한다. 만약 조건을 만족하면 해당 요소는 count된다.