221025 [프로그래머스] :: 폰켓몬, 연속 부분 수열 합의 개수, 피로도

폰켓몬

👾 문제 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

👾 제한 사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

👾 나의 답안

function solution(nums) {
    const set = Array.from(new Set(nums));
    return set.length < nums.length / 2 ? set.length : nums.length / 2;
}

 

• set으로 중복 제거
• nums의 길이를 2로 나눈 값이  set의 길이보다 크면 set의 길이 반환, 그렇지 않으면 nums.length / 2 반환

 

연속 부분 수열 합의 개수

👾 문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

👾 제한 사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

 

👾 나의 답안

function solution(elements) {
    const elementsLoop = [...elements, ...elements];
    const arr = [];
    for (let i = 0; i < elements.length; i++) {
        for (let j = 0; j < elements.length; j++) {
            let k = i + j;
            arr.push(elementsLoop.slice(j, k).reduce((a, c) => a + c, 0));
        }
    }
    return Array.from(new Set(arr)).length;
}

 

• 원형 수열이므로 elements를 두 번 반복
• 이중 for문 사용, j부터 k까지의 합을 배열 arr에 push해 주고 set으로 중복 제거 후 길이 반환
• 하나하나 값 구해서 넣는 거라 효율성 테스트에서 빨간 불 뜰 줄 알았더니 아니네 나온 지 얼마 안 돼서 그런가 봄

 

피로도

👾 문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

👾 제한 사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

 

닉값 제대로 하는 문제

 

👾 나의 답안

function solution(k, dungeons) {
    const arr = [];
    const checked = new Array(dungeons.length).fill(0);

    function DFS(k, dungeons, checked, cnt) {
        arr.push(cnt);
        for (let i = 0; i < dungeons.length; i++) {
            if (!checked[i] && k >= dungeons[i][0]) {
                checked[i] = 1;
                DFS(k - dungeons[i][1], dungeons, checked, cnt + 1);
                checked[i] = 0;
            }
        }
    }
    DFS(k, dungeons, checked, 0);
    return Math.max(...arr);
}

 

• 모든 경우의 수를 담을 arr과 방문한 던전을 체크할 checked 선언
• 경우의 수 cnt를 arr에 전부 push, 아직 방문하지 않은 던전이고 현재 피로도(k)보다 최소 필요 피로도가 작으면 방문 체크
• 재귀 함수 사용, 현재 피로도에서 소모 피로도를 빼고 cnt 값에 1 더하고 계속 돌아줌, 모든 경우의 수를 구하기 위해 다시 방문해야 하므로 방문 체크 해제
• 경우의 수 중 최댓값 반환
• 문제 옆에 DFS라고 쓰여 있으면 나도 모르게 스킵해 버리지만... 왠지 나 DFS랑 좀 친해졌을지도