코딩테스트 29일차
삼총사
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다. 한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
function solution(number) {
var answer = 0;
function backtrack(start, count, sum) {
if (count === 3 && sum === 0) {
answer++;
return;
}
if (count > 3 || start >= number.length) {
return;
}
for (var i = start; i < number.length; i++) {
var current = number[i];
backtrack(i + 1, count + 1, sum + current);
}
}
backtrack(0, 0, 0);
return answer;
}✏️풀이
solution 함수는 주어진 학생들의 번호 배열을 입력으로 받고, 삼총사를 만들 수 있는 방법의 수를 반환합니다.
backtrack 함수는 재귀적으로 호출되는 백트래킹 함수입니다. 현재 선택한 학생의 인덱스 start, 선택한 학생의 수 count, 선택한 학생들의 번호 합 sum을 매개변수로 받습니다.
첫 번째 조건문인 if (count === 3 && sum === 0)은 학생을 3명 선택하고 선택한 학생들의 번호 합이 0인 경우를 검사합니다. 이 경우 answer 변수를 증가시켜 삼총사를 만들 수 있는 방법의 수를 카운트하고 함수를 종료합니다.
두 번째 조건문인 if (count > 3 || start >= number.length)은 선택한 학생의 수가 3을 초과하거나 인덱스 start가 학생들의 번호 배열의 길이를 초과한 경우 함수를 종료합니다.
for 반복문은 선택한 학생의 인덱스 start부터 학생들의 번호 배열의 끝까지 반복합니다. 현재 학생의 번호를 current 변수에 저장하고, backtrack 함수를 재귀적으로 호출합니다. 이 때, 다음 학생을 선택하기 위해 start를 i + 1로 업데이트하고, 선택한 학생의 수를 1 증가시키며 선택한 학생들의 번호 합에 current 값을 더해줍니다.
backtrack 함수의 호출이 종료되면 solution 함수에서는 answer 값을 반환하여 삼총사를 만들 수 있는 방법의 수를 출력합니다.
나머지가 1이 되는 수 찾기
자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.
function solution(n) {
for (let x = 1; ; x++) {
if (n % x === 1) {
return x;
}
}
}✏️풀이
solution 함수는 n을 매개변수로 받습니다.
for 루프를 사용하여 x를 1부터 시작하여 무한히 증가시킵니다.
if 문을 사용하여 n을 x로 나눈 나머지가 1인지 확인합니다.
만약 나머지가 1이라면 x를 반환하고 함수를 종료합니다.
루프를 계속 반복하며 x를 증가시키고 조건을 만족하는 x를 찾을 때까지 실행됩니다.
