[프로그래머스] 삼총사 Kotlin

안녕하세요. 이번에는 프로그래머스 삼총사 문제를 풀어보려고 합니다.

 

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

프로그래머스

---

Problem

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

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

 

[제한 사항]

○ 3 ≤ number의 길이 ≤ 13

○ -1,000 ≤ number의 각 원소 ≤ 1,000

○ 서로 다른 학생의 정수 번호가 같을 수 있습니다.

사진 1. 입출력 예

---

Solution

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

 이번 문제는 for문을 사용해서 문제에 접근해 보았습니다. 

 

1. 다른 사람 코드

class Solution {
    var answer = 0
    lateinit var visited: BooleanArray
    lateinit var number: IntArray

    fun solution(number: IntArray): Int {
        answer = 0
        visited = BooleanArray(number.size)
        permulation(number, 0, 0, 0)
        return answer
    }

    fun permulation(number: IntArray, start: Int, size: Int, sum: Int) { //숫자 조합
        if (size == 3) { //3개 뽑고 합이 0이면 answer++
            if (sum == 0) {
                answer++
            }
            return
        }
        
        for (i in start until number.size) { //start 변수를 선언해서 그 다음 반복문 실행 시 앞에 인덱스를 점프하고 실행
            if (!visited[i]) {                          //visited를 통해 중복으로 선택 불가능
                permulation(number, i + 1, size + 1, sum + number[i])
                visited[i] = false
            }
        }
    }
}

  for문이 아닌 다른 방식으로 푼 문제가 있어서 가져왔습니다. 재귀적으로 접근한 문제였습니다. visited [i]로 방문체크를 하면서 중복 방문이 안되도록 하면서 size가 3일 때 합이 0이면 answer++를 카운트시키는 방법으로 접근하였습니다. 첫 번째 코드는 중복을 방지하기 위한 추가처리가 필요하지 않고 두 번째 코드는 visited로 중복을 방지하였습니다. 

---

Performance

1. 내가 작성한 코드	2. 다른 사람 코드