5. [중복순열] 가위바위보
가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.
입력
없음
출력
- 2차원 배열(arr[i])을 리턴해야 합니다.
- arr[i]는 전체 경우의 수 중 한 가지 경우(총 세 번의 선택)를 의미하는 배열입니다.
- arr[i]는 'rock', 'paper', 'scissors' 중 한 가지 이상을 요소로 갖는 배열입니다.
- arr[i].length는 3
주의사항
최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.
쉽게 생각해 올림픽 순위 결정 방식을 참고하면 됩니다.
금메달('rock')이 은메달('paper')보다 우선하고, 은메달('paper')이 동메달('scissors')보다 우선합니다.
입출력 예시
let output = rockPaperScissors();
console.log(output);
/*
[
["rock", "rock", "rock"],
["rock", "rock", "paper"],
["rock", "rock", "scissors"],
["rock", "paper", "rock"],
// ...etc ...
]
*/Advanced
가위바위보 게임의 수를 나타내는 양의 정수 rounds가 인자로 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 리턴하도록 함수를 작성해 보세요.
풀이
function rockPaperScissors (k) {
// 입력값 안들어 오면 3으로, 매개변수를 k = 3 이렇게 기본값도 가능
k = k || 3;
let arr =[[]]
// 한 판씩 진행해 나가면 이전의 조합에 가위 또는 바위 또는 보가 붙는다(3배됨)
function rockPaperScissor (n, arr) {
if(n === 0) return arr;
let result = [];
for(let i = 0 ; i < arr.length; i++) {
result.push([...arr[i], 'rock'])
result.push([...arr[i], 'paper'])
result.push([...arr[i], 'scissors'])
}
return rockPaperScissor(n-1, result)
}
return rockPaperScissor(k, arr)
};재귀함수 만들 때 리턴 주의해서 꼭 넣어주자
그리고 처음에 `arr = [ [], [], [] ]` 이렇게 했더니 같은 조합이 3개씩 나왔다...
6. [순열] 새로운 치킨 소스 레시피
개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다. 그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다. 그 소문은 다음과 같다.
N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.
이 소문을 참고하여 '비밀의 승승장구 치킨 소스'가 될 수 있는 경우의 수를 모두 반환하는 함수를 작성하세요.
입력
-인자 1: stuffArr
Number 타입의 재료를 담은 배열
요소는 0과 1로만 이루어진 숫자이며, 항상 1로 시작합니다.
요소는 중복될 수 없습니다.
요소의 길이는 20 이하입니다.
배열의 길이는 2 이상 10 이하입니다.
ex) [111, 110, 1010, 10, 10110]
-인자 2: choiceNum
Number 타입의 1 이상 stuffArr 길이 이하의 자연수
재료를 선택할 수 있는 수를 뜻합니다.
ex) 2
출력
Number 타입을 반환해야 합니다.
stuffArr가 [1, 10, 11000, 1111] 이고, choiceNum은 2라면 사용 가능한 재료는 [1, 10, 1111] 입니다. 조합할 수 있는 경우의 수는 6 가지입니다.
주의사항
만약, 주어진 재료 모두 사용할 수 없다면 빈 배열[]을 반환해야 합니다.
만약, 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다.
조합 및 요소는 작은 숫자 -> 큰 숫자로 정렬합니다.
예시로 [1, 10, 11000, 1111]이 요소로 들어왔다면, 0이 세 개인 11000을 제외하고 [1, 10, 1111] 순서가 되어야 하며,
[ [1, 10], [1, 1111], [10, 1], [10, 1111], [1111, 1], [1111, 10] ]을 반환해야 합니다.
입출력 예시
const output1 = newChickenRecipe([1, 10, 1100, 1111], 2);
console.log(output1);
/*
[
[1, 10], [1, 1100], [1, 1111],
[10, 1], [10, 1100], [10, 1111],
[1100, 1], [1100, 10], [1100, 1111],
[1111, 1], [1111, 10], [1111, 1100]
];
*/
const output2 = newChickenRecipe([10000, 10, 1], 3);
console.log(output2); // []
const output3 = newChickenRecipe([11, 1, 10, 1111111111, 10000], 4);
console.log(output3);
/*
[
[1, 10, 11, 1111111111],
[1, 10, 1111111111, 11],
[1, 11, 10, 1111111111],
[1, 11, 1111111111, 10],
[1, 1111111111, 10, 11],
[1, 1111111111, 11, 10],
[10, 1, 11, 1111111111],
[10, 1, 1111111111, 11],
[10, 11, 1, 1111111111],
[10, 11, 1111111111, 1],
[10, 1111111111, 1, 11],
[10, 1111111111, 11, 1],
[11, 1, 10, 1111111111],
[11, 1, 1111111111, 10],
[11, 10, 1, 1111111111],
[11, 10, 1111111111, 1],
[11, 1111111111, 1, 10],
[11, 1111111111, 10, 1],
[1111111111, 1, 10, 11],
[1111111111, 1, 11, 10],
[1111111111, 10, 1, 11],
[1111111111, 10, 11, 1],
[1111111111, 11, 1, 10],
[1111111111, 11, 10, 1],
]
*/문제풀이
function newChickenRecipe(stuffArr, choiceNum) {
// 0이 3개 이상 제외
filtered = stuffArr.filter(el => [...String(el)].filter(el => el === "0").length < 3);
// 앞에 문제 코드 재활용
const arr = [[]];
function recipe (n, arr) {
if(n === 0) return arr;
let result = [];
for(let i = 0 ; i < arr.length; i++) {
for(let j = 0; j < filtered.length; j++){
// 중복 포함은 제외하기
if(!arr[i].includes(filtered[j])) {
result.push([...arr[i], filtered[j]])
}
}
}
return recipe(n-1, result)
}
return recipe(choiceNum, arr)
}정해진 횟수만큼 조합이나 순열을 만들때 이 코드를 재활용하면 좋을 것 같다.
function 순열조합 (n, arr) {
if(n === 0) return arr;
let result = [];
for(let i = 0 ; i < arr.length; i++) {
for(let j = 0; j < filtered.length; j++){
// 중복 포함은 제외하기, 만약 조합이면 이부분은 제외
if(!arr[i].includes(조합해야하는숫자[j])) {
result.push([...arr[i], 조합해야하는숫자[j]])
}
}
}
return 순열조합(n-1, result)
}
7. [조합] 블랙잭은 지겨워
평범한 블랙잭 게임에서 수시로 패배하자 흥미가 떨어진 김코딩은 박타짜에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다. 새로운 룰은 다음과 같습니다.
1. 숫자로 이루어진 카드를 여러 장 받습니다.
2. 3장씩 카드를 고르고, 3장에 적힌 숫자들의 합이 소수인지 확인합니다.
3. 받아든 카드로 만들 수 있는 소수의 개수가 많은 사람이 이기게 됩니다.
예로, [1, 2, 3, 4]라는 카드를 받았을 때 만들 수 있는 숫자는 6, 7, 8, 9이고, 소수는 7 하나이기 때문에 가지고 있는 소수의 개수는 1개입니다. [2, 3, 4, 8, 13]라는 카드를 받았을 때 만들 수 있는 숫자는 9, 13, 18, 14, 19, 23, 15, 20, 24, 25이고, 소수는 13, 19, 23 총 3개이기 때문에 가지고 있는 소수의 개수는 3개입니다. 게임을 진행하기 전에 소수에 대해 아무런 지식이 없는 박타짜는 게임을 며칠 미룬 뒤, 게임의 룰을 따르는 함수를 만들기로 했습니다. 소수에 약한 박타짜를 도와 여러 장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.
function boringBlackjack(cards) {
// 카드 3장씩 뽑아서 더해준다(중복방지를 위해 앞의 카드인덱스+1 해줌)
const sum = []
for(let i = 0 ; i < cards.length; i++) {
for(let j = i + 1 ; j < cards.length; j++) {
for(let k = j + 1 ; k < cards.length; k++) {
sum.push([cards[i] + cards[j] +cards[k]]);
}
}
}
//소수 판별 함수
function isPrime(number) {
// for 문 조건을 number/2인 이유는 약수처럼 대칭 관계이기때문
// number/2 까지만 비교해 보아도 소수 판별이 가능하다
for (let i = 2; i < number/2; i++) {
if (number % i === 0) return false;
}
return true;
}
// 소수 몇개인지
let count =0
for(let i = 0 ; i < sum.length; i++) {
if (isPrime(sum[i])) count++
}
return count;
}처음에 카드를 다뽑고 map이랑 reduce로 3장 더해줬는데 다시 보니 처음부터 합친 값으로 배열을 만드는게 훨씬 간편했다..
어떤걸 참과 거짓으로 판단해야할 때는 함수로 만들어서 활용하는데 보기 훨씬 깔끔한 것 같다
원래 소수 판변할 때 항상 모든 숫자를 순회했는데 반만 순회해도 된다는 것 기억해두기!
8. [GCD] 빼빼로 데이
오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 M개와 누드 빼빼로 N개를 구매하여 아침 일찍 출근길에 나섰습니다. 팀장은 자신보다 먼저 출근해 있는 직원들에게 구매한 빼빼로를 전부 나누어 주려고 합니다. 단, 서로 질투하는 경우를 만들지 않기 위해 모든 직원들에게 공평하게 빼빼로를 나누어 주려고 합니다. 직원들은 각각의 빼빼로를 똑같은 개수만큼 받아야 합니다. 빼빼로를 쪼개서 줄 수는 없습니다. 하지만 회사에 도착하기 전이라 몇 명의 직원들이 있는지 모르는 상황입니다. 팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.
출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.
출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다. 여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.
function divideChocolateStick(M, N) {
// 직원수가 최대공약수의 약수
// 최대공약수 구하기기
function GCD(a, b){
while(b !== 0){
let r = a % b;
a = b;
b = r;
}
return a;
}
const gcd = M >= N ? GCD(M, N) : GCD(N, M);
// 최대공약수의 약수를 사람수로해서 배열에 넣어주기기
const result = [];
// 약수는 대칭 관계이므로 반만 알면 반대 값도 반복문을 돌리지 않아도 구 할 수 있따.
const small = Math.floor(Math.sqrt(gcd))
for(let i = 1; i <= small; i++) {
if(gcd % i === 0){
result.push([i, M/i, N/i])
if(i*i !== gcd) {
result.push([gcd/i, M/(gcd/i), N/(gcd/i)])
}
}
}
// 사람수로 나눈 빼빼로 수 넣어주기
result.sort((op1, op2) => op1[0] - op2[0]);
return result
}최대 공약수 구하는 공식 기억해두기
9. (Advanced) [멱집합] 집밥이 그리워
김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다. 밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.
function missHouseMeal(sideDishes) {
// 사전순으로 결과값이 나와야하므로 우선 정렬
sideDishes.sort()
// 결과 담을 배열
const result = [[]]
// 한가지 음식을 더하지 않아거 하나 더하는 경우의 수 2개
function powerSet(arr, nemu) {
for(let i = 0; i < arr.length; i++){
result.push([...arr[i], nemu])
}
}
// 모든 메뉴를 돌면서 담을건지 않담을 건지 판단하며, 각 경우마다 결과에 추가해줌
for(let j = 0; j < sideDishes.length; j++){
powerSet([...result], sideDishes[j])
}
result.sort()
return result
}
마치며
그래도 이번 알고리즘은 다 풀어서 기분 좋았다ㅎ
이번 문제들은 어느정도 패턴이 있어서 하나 푸니깐 다음 문제에 활용할 수 있어서 다 풀 수 있던것 같다.
참고
코드스테이츠 코플릿 알고리즘
'CS > 알고리즘' 카테고리의 다른 글
| 알고리즘 연습문제 (0) | 2023.04.05 |
|---|---|
| 빅오 표기법 (Big O Natation) (0) | 2023.03.28 |