Algorithm - Programmers Problems (week 5)

이소라·2023년 2월 7일

Algorithm

목록 보기

39/77

Problem : 괄호 회전하기

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다.
  - 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
- 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다.
  - 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- s의 길이는 1 이상 1,000 이하입니다.
입출력 예
- 입력 : s = "[](){}"
- 출력 : 3
- 설명 : 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열
0	`"[](){}"`	O
1	`"](){}["`	X
2	`"(){}[]"`	O
3	`"){}[]("`	X
4	`"{}[]()"`	O
5	`"}[](){"`	X

Solution

function solution(s) {
    let answer = 0;
    const brackets = s.split('');
    const closeBracketPair = {']':'[', ')':'(', '}':'{'};
    
    const isBracketsVaild = (brackets) => {
        const stack = [];
        
        for (let i = 0; i < brackets.length; i++) {
            const bracket = brackets[i];
            if (!closeBracketPair[bracket]) {
                stack.push(bracket);
                continue;
            }
            if (stack[stack.length - 1] !== closeBracketPair[bracket]) {
                return false;
            }
            stack.pop();
        }
        
        return !stack.length;
    };
    
    for (let i = 0; i < s.length; i++) {
        if (isBracketsVaild(brackets)) {
            answer++;
        }
        brackets.push(brackets.shift());
    }
    
    return answer;
}

Problem : N으로 표현

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.

Solution

문제 풀이 (참고 : [프로그래머스] 동적계산법 - N으로 표현 문제 풀이 (feat.JS))
- 숫자 N(1<= N <= 8)의 개수에 따라 구할 수 있는 연산의 수를 모두 확인함
- 가장 작은 경우부터 확인하여 number가 되면 그 때의 N의 개수를 반환함

숫자 N 개수	연산 종류
1	N
2	NN, N + N, N - N, N/N
3	NNN, NN + N, NN - N, NNN, NN/N, N + N + N, N + N - N, N + NN, N + N/N, N - N + N, N - NN, N - N/N, ... [1결과(연산)2결과, 2결과(연산)1결과]
4	[1결과(연산)3결과, 2결과(연산)3결과, 3결과(연산)1결과]

코드 구현 과정
1. N 개수 별 만들 수 있는 경우의 수를 저장하는 자료구조 Set을 만듬
2. N의 개수를 1씩 증가시키면서, N의 개수에 만들 수 있는 경우의 수를 Set에 저장함
  - 예) N의 개수가 3일 때의 연산의 경우의 수 = N의 개수가 1일 때의 연산 결과와 N의 개수가 2일 때의 연산 결과를 사칙연산
3. N의 개수에 대한 경우의 수 Set에서 number를 포함한다면, 그 때의 N의 개수를 반환함

function solution(N, number) {
    let answer = 0;
    const memo = Array.from({length : 9}, () => new Set());
    
    if (N === number) {
        return 1;
    }
    
    memo.forEach((element, index) => {
       if (index) {
           return element.add((Number(String(N).repeat(index))));
       } 
    });
    
    for (let count = 1; count <= 8; count++) {
        for (let prevCount = 1; prevCount < count; prevCount++) {
            for (let element1 of memo[prevCount]) {
                for (let element2 of memo[count - prevCount]) {
                    memo[count].add(element1 + element2);
                    memo[count].add(element1 - element2);
                    memo[count].add(element1 * element2);
                    memo[count].add(Math.floor(element1 / element2));
                }
            }
        }
        if (memo[count].has(number)) {
            return count;
        }
    }
    return -1;
}

Problem : 징검다리 건너기

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
- 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
- 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
- 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
- k는 1 이상 stones의 길이 이하인 자연수입니다.

Solution

문제 풀이 (참고 : JS 풀이 공유 및 왜 이진탐색 문제인가?)
- 단순히 for 문을 돌려서 푸니까 시간초과됨
- 배열의 크기와 디딤돌 최대 칸 수가 최대 200,000까지임
- 배열 원소의 값 최대 200,000,000 => log2(200,000,000) ~ 27.5
  - 이분탐색(binary search)로 풀어야 함

function solution(stones, k) {
    let left = 1;
    let right = 200000000;

    while(left <= right) {
        const mid = Math.floor((left + right) / 2);

        let skipCount = 0;
        for(let i = 0; i < stones.length; i++) {
            if(stones[i] - mid <= 0) {
                skipCount += 1;
            } else {
                // 건너뛰는 돌이 연속되지 않아서 skipCount 초기화
                skipCount = 0;
            }

            if(skipCount === k) {
                // 건너뛰는 돌이 k개 이상일 경우, 건너 뛸 수 없으므로 loop 종료
                break;
            }
        }

        if(skipCount === k) {
            // mid 값이 크기 때문에 최대값의 범위를 줄여줌
            right = mid - 1;
        } else {
            // mid 값이 작기 때문에 최소값의 범위를 늘려줌
            left = mid + 1;
        }
    }

    return left;
}

Problem : 구명보트

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
- 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

Solution

문제 풀이
- 구명보트를 최대한 적게 사용하여 모든 사람을 구출해야 함 (=구명포트의 limit만큼 꽉 채워서 운반해애 함)
  - 제일 무거운 사람과 제일 가벼운 사람을 조합해서 운반할 수 있음
  - 제일 무거운 사람과 제일 가벼운 사람의 조합이 limit 이하면 둘 다 운반하고, limit 초과일 경우 제일 무거운 사람만 운반함
  - 효율성을 위해 two pointer를 사용함

function solution(people, limit) {
    let answer = 0;
    let left = 0;
    let right = people.length - 1;
    people.sort((a,b) => a - b);
    
    while (left <= right) {
        if (left === right) {
            answer++;
            break;
        }
        
        if (people[left] + people[right] <= limit) {
            left += 1;
            right -= 1;
        } else {
            right -= 1;
        }
        
        answer++;
    }
    return answer;
}

Problem : 위장

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
- 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.

Solution

문제 풀이 (참고: 수학적으로 푸는 방법 궁금하신분들 설명드립니다.(코드 없음))
- 각각 옷의 개수가 a, b일 때의 조합의 개수 : (a + b) + ab
- 각각 옷의 개수가 a, b, c일 때의 조합의 개수 : (a+b+c) + (ab+bc+ca) + (abc)
- n차식(n = 옷의 종류의 개수) 계수들의 합
  - 각각의 옷의 개수가 a, b, c라면, (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)라는 식에서의 계수들의 합
  - x에 1을 대입하면, (1+a)(1+b)(1+c)이 되고 맨 앞 x3 의 계수는 정잡 포함되지 않으므로 마지막에 1을 빼줌

function solution(clothes) {
    let cases = 1;
    const clothMap = new Map();
    clothes.forEach(([clothName, clothType]) => {
        const sameTypeClothes = clothMap.get(clothType);
        sameTypeClothes ? clothMap.set(clothType, [...sameTypeClothes, clothName]) : clothMap.set(clothType, [clothName]);
    });
    
    for (let [clothType, clothes] of clothMap.entries()) {
        cases *= clothes.length + 1;
    }
    
    return cases - 1;
}