02/13 알고리즘 공부(42) - 삼총사

조건

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.( 3 ≤ number의 길이 ≤ 13, -1,000 ≤ number의 각 원소 ≤ 1,000, 서로 다른 학생의 정수 번호가 같을 수 있습니다.)

알고리즘 예상

1. number의 원소 중 3개를 이용한 모든 배열을 만든다.
2. 해당 배열 중 합이 0인 배열의 개수를 answer에 저장한 후 반환한다.

 

초기 코드

class Solution {
    fun solution(number: IntArray): Int {
        var answer: Int = 0
        return answer
    }
}

 

내 코드

class Solution {
    fun solution(number: IntArray): Int {
        var answer: Int = 0
        var comArray : Array<IntArray> = arrayOf()
        
        for(i in number.indices){
            for(j in i+1..number.size-1){
                for(k in j+1..number.size-1){
                    comArray += intArrayOf(number[i], number[j], number[k])
                }
            }
        }
        comArray.forEach{i -> if(i.sum()==0) answer++ }
        return answer
    }
}

반복문을 이용해 중복되지 않는 모든 배열을 만들어 그 합이 0인 개수를 반환했다. comArray변수가 필요치 않은 것 같아 지워보기로 했다.

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

배열을 만들 필요도 없이 3중첩의 for문에서 순열을 만들 수 있었다.

다른 사람의 풀이

class Solution {
    fun solution(number: IntArray): Int {
        var answer: Int = 0

        var threeMusketeersCount = 0

        for ((i,n) in number.withIndex()) {
            for ((j, m) in number.withIndex()) {
                for ((k, l) in number.withIndex()) {
                    if ((i < j) && (j < k)) {
                        if (n + m + l == 0) {
                            threeMusketeersCount++
                        }
                    }
                } 
            }
        }
        return threeMusketeersCount
    }
}

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

 

개선점 또는 배운점

1. 풀이가 다르진 않지만 사용한 메소드에서 차이가 좀 났다. .withIndex()를 이용해 변수 두개를 사용했고 if문 두개를 이용해 중복을 검사했다.
2. 아래 풀이의 for문 조건에서 i가 마지막 두 인덱스가 될 수 없기 때문에 2를 빼주었다. in a .. b를 사용한다면 3을 빼주면 될 것이다.

 

개선된 코드

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