문제 설명
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 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 | 학생드르이 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2)이 삼총사가 될 수 있으므로, 5를 return합니다. | ||
[-1, 1, -1, 1] | 0 | 삼총사가 될 수 있는 방법이 없습니다. |
문제 풀이
풀이 언어 : C++
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> number) {
int answer = 0;
int sum=0;
for(int i=0; i<number.size()-2; i++)
{
for(int j=i+1; j<number.size()-1; j++)
{
for(int k=j+1; k<number.size(); k++)
{
sum=number[i]+number[j]+number[k];
if(sum==0)
{
answer+=1;
}
}
}
}
return answer;
}
n개의 숫자 중 3개를 중복 없이 뽑는 방법을 생각해내는 것이 핵심이었다. 3개의 숫자를 뽑아내야 하기 때문에 for문 3개로 구현할 수 있다.
for문으로 i번째 수를 먼저 잡는다. 그리고 이 i는 0~number.size()-2만큼 돌린다. 그 다음 j는 i가 아닌 i보다 하나 뒤인 i+1부터 시작해 number.size()-1만큼 돌린다. i+1~number.size()-1이 돌아가는 것이다. 마지막으로 k는 i와 j도 아닌 j보다 하나 뒤인 j+1에서 부터 시작해서 number.size()만큼 돌린다. 이렇게 반복문을 돌리며 가장 안쪽의 for문에서 i, j, k번째 숫자를 모두 더해 0인지 확인하고 0이라면 answer를 증가시킨다.
다 짜고 나니 별로 어렵지 않아보이지만 반복문을 어디서 시작할지 얼마나 돌릴지 생각하는 꽤 어려웠다. 예시르 들어보자. 입출력 예 1처럼 [-2, 3, 0, 2, -5]가 number로 주어졌다면 i는 일단 -2를 가리키면서 시작한다. 그리고 그 안에 j는 3을 가리킨다. k는 0을 가리킨다. 가장 안쪽의 k 반복문이 돌아가면 (-2, 3, 0), (-2, 3, 2), (-2, 3, -5)이다. k의 반복문이 끝나고 j로 반복문으로 돌아가면 j는 +1이 되어 2가 된다. 그 다음 k 반복문이 돌아가면 (-2, 0, 2), (-2, 0, -5)이다. 이런식으로 뒤로 돌아가지 않고 하나씩 앞으로 가고 그 앞에 있는 숫자로 순서대로 조합하면 3개씩 묶음인 모든 경우를 볼 수 있다.
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/131705
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
'Code KATA > 알고리즘 코드카타' 카테고리의 다른 글
[2025.01.20] 가장 가까운 같은 글자 (0) | 2025.01.20 |
---|---|
[2025.01.17] 문자열 내 맘대로 정렬하기 (0) | 2025.01.17 |
[2025.01.15] 시저 암호 (0) | 2025.01.15 |
[2025.01.14] 크기가 작은 부분 문자열 (0) | 2025.01.14 |
[2025.01.11] 이상한 문자 만들기 (0) | 2025.01.10 |