[Programmers][Java]삼총사

728x90

Programmers_Level_1

2023.12.15 - [코딩테스트/프로그래머스] - [Programmers][Java]최대공약수와 최소공배수

2023.12.16 - [코딩테스트/프로그래머스] - [Programmers][Java]같은 숫자는 싫어

2023.12.16 - [코딩테스트/프로그래머스] - [Programmers][Java]3진법 뒤집기

2023.12.17 - [코딩테스트/프로그래머스] - [Programmers][Java]예산

2023.12.18 - [코딩테스트/프로그래머스] - [Programmers][Java]이상한 문자 만들기

2023.12.18 - [코딩테스트/프로그래머스] - [Programmers][Java]크기가 작은 부분문자열

2023.12.21 - [코딩테스트/프로그래머스] - [Programmers][Java]삼총사

🏁 Programmers_Level_1
📖 삼총사

❔ 문제 설명

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다.

이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다.

예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다.

또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다.

따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

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

🚫 제한 사항

⁕ 3 ≤ number의 길이 ≤ 13
⁕ -1,000 ≤ number의 각 원소 ≤ 1,000
⁕ 서로 다른 학생의 정수 번호가 같을 수 있습니다.

✅ 입출력 예

number	result
[-2, 3, 0, 2, -5]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

📃 입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

학생들의 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2) 이 삼총사가 될 수 있으므로, 5를 return 합니다.

입출력 예 #3
삼총사가 될 수 있는 방법이 없습니다.

💻 내 작성 코드

class Solution {
    public int solution(int[] number) {
        int size = number.length;
        int count = 0;
        int sum = 0;
        for(int i = 0; i < size; i++){
            sum = number[i];
            for(int k = i+1; k < size; k++){
                sum += number[k];
                for(int j = k+1; j < size; j++){
                    if(sum + number[j] == 0) count++;
                }
                sum = number[i];
            }
            sum = 0;
        }
        return count;
    }
}

위 코드는 '브루트 포스' 방식으로 문제를 해결했습니다. 브루트 포스란 모든 가능한 경우의 수를 직접 탐색해보는 방식을 의미합니다. 코드에서는 3중 for문을 통해 가능한 모든 3명의 조합을 확인하며, 각 조합의 합이 0인 경우 카운트를 증가시킵니다. 이 방식은 가장 직관적이고 이해하기 쉬운 방법이지만, 배열의 크기가 커질수록 연산량이 기하급수적으로 증가하게 됩니다. 이로 인해 성능상의 문제가 발생할 수 있습니다.

💻 다른 사람의 풀이

import java.util.Arrays;

public class Solution {
    int count = 0;

    public int solution(int[] number) {
        Arrays.sort(number);
        boolean[] visited = new boolean[number.length];
        backtrack(number, visited, 0, 0, 0);
        return count;
    }

    private void backtrack(int[] number, boolean[] visited, int start, int depth, int sum) {
        if (depth == 3) {
            if (sum == 0) {
                count++;
            }
            return;
        }

        for (int i = start; i < number.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            backtrack(number, visited, i + 1, depth + 1, sum + number[i]);
            visited[i] = false;
        }
    }
}

이 코드는 백트래킹 알고리즘을 사용하여 문제를 해결합니다. 백트래킹 알고리즘은 가능한 모든 해결책을 탐색하는데 사용되는 알고리즘입니다. 이 알고리즘은 해결책을 찾을 때까지 가능한 모든 경로를 탐색하고, 해결책이 아니라고 판단되면 이전 단계로 돌아와 다른 경로를 탐색합니다.

int count = 0;

총 경우의 수를 저장할 변수를 선언합니다.

public int solution(int[] number) {...}

이 함수는 주어진 배열에서 합이 0이 되는 세 숫자의 조합의 수를 찾는 함수입니다. 배열을 정렬하고, 백트래킹 함수를 호출하여 합이 0이 되는 세 숫자의 조합의 수를 찾습니다.

private void backtrack(int[] number, boolean[] visited, int start, int depth, int sum) {...}

이 함수는 백트래킹을 수행하는 함수입니다.

if (depth == 3) {...}: 세 숫자를 선택했을 때, 그 합이 0인지 확인합니다. 만약 합이 0이라면, 경우의 수를 하나 증가시킵니다.
for (int i = start; i < number.length; i++) {...}: 배열의 각 숫자에 대해 백트래킹을 수행합니다. 만약 해당 숫자가 이미 선택되었다면, 다음 숫자로 넘어갑니다. 아니라면, 해당 숫자를 선택하고, 백트래킹을 계속 진행합니다.
visited[i] = true;: 해당 숫자를 선택했음을 표시합니다.
backtrack(number, visited, i + 1, depth + 1, sum + number[i]);: 다음 숫자와 함께 백트래킹을 계속 진행합니다. 선택한 숫자의 수와 그 합을 갱신합니다.
visited[i] = false;: 백트래킹이 끝나면, 해당 숫자의 선택을 취소합니다. 이렇게 하면, 다른 경로에서 해당 숫자를 다시 선택할 수 있습니다.

이렇게 백트래킹 알고리즘을 사용하면, 주어진 배열에서 합이 0이 되는 세 숫자의 조합의 수를 효율적으로 찾을 수 있습니다.

📒 배운 점

위 코드와 문제를 통해 배울 수 있는 몇 가지 핵심 개념과 기술들이 있습니다.

백트래킹

위 코드는 백트래킹 알고리즘을 사용하여 해결했습니다. 백트래킹은 가능한 모든 해결책을 탐색하는 알고리즘으로, 문제의 조건을 만족하는 해결책을 찾으면 해당 해를 반환하고, 그렇지 않으면 이전 상태로 돌아가 다른 해결책을 탐색합니다. 이 문제에서는 합이 0이 되는 세 숫자의 조합을 찾는 것이었습니다.

재귀 호출

백트래킹 알고리즘은 재귀 호출을 통해 구현되었습니다. 재귀 호출은 함수가 자신을 다시 호출하는 것으로, 위 코드에서는 백트래킹 함수가 자신을 호출하여 가능한 모든 조합을 탐색하였습니다.

조합의 탐색

이 문제에서는 주어진 배열에서 세 숫자의 조합을 찾아야 했습니다. 이를 위해 백트래킹 알고리즘을 사용하여 모든 가능한 조합을 탐색하였습니다. 여기서 중요한 점은 각 조합이 유일해야 한다는 것입니다. 이를 위해 선택한 숫자를 표시하고, 백트래킹이 끝나면 선택을 취소하는 방법을 사용하였습니다.

조건의 확인

백트래킹 알고리즘을 사용하여 모든 가능한 조합을 탐색한 후, 각 조합이 문제의 조건을 만족하는지 확인하였습니다. 이 문제에서는 세 숫자의 합이 0이 되는지를 확인하였습니다.

코드의 유연성

백트래킹을 사용하는 코드는 문제의 요구사항이 바뀌었을 때 더 유연하게 대응할 수 있습니다. 예를 들어, 3개가 아닌 4개의 숫자의 합이 0이 되는 경우를 찾는 문제로 변한다면, 백트래킹을 사용하는 코드는 단지 'depth == 3'을 'depth == 4'로 변경하면 되지만, 중첩 루프를 사용하는 코드는 루프를 한 개 더 추가해야 합니다.

이런 개념과 기술들을 이해하고 사용하는 것은 문제 해결 능력을 향상시키는 데 중요합니다. 특히 백트래킹과 재귀 호출은 많은 알고리즘 문제에서 사용되는 핵심 기술입니다.