Algorithm - Greedy Problems

이소라·2022년 8월 29일
0

Algorithm

목록 보기
16/77
post-custom-banner

Programmers Problem(lev.1) : 체육복

  • 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

    • 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.
      • 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
    • 제한사항
      • 전체 학생의 수는 2명 이상 30명 이하입니다.
      • 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
      • 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
      • 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
      • 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

  • 입출력 예

nlostreservereturn
5[2, 4][1, 3, 5]5
5[2, 4][3]4
3[3][1]2

Solution

function solution(n, lost, reserve) {
    let answer = 0;
    for (let student = 1; student <= n; student++) {
        if (!lost.includes(student)) {
            answer++;
            continue;
        }
        if (lost.includes(student) && reserve.includes(student)) {
            const reserveStudentIndex = reserve.indexOf(student);
            const lostStudentIndex = lost.indexOf(student);
            reserve.splice(reserveStudentIndex, 1);
            lost.splice(lostStudentIndex, 1);
            answer++;
            continue;
        }
        const prevStudent = student - 1;
        const nextStudent = student + 1;
        if (reserve.includes(prevStudent) && !lost.includes(prevStudent)) {
            findReserveStudent(reserve, prevStudent, lost, student);
            answer++;
            continue;
        } else if (reserve.includes(nextStudent) && !lost.includes(nextStudent)) {
            findReserveStudent(reserve, nextStudent, lost, student);
            answer++;
            continue;
        }
    }
    return answer;
}

function findReserveStudent(reserve, reserveStudent, lost, lostStudent) {
    const reserveStudentIndex = reserve.indexOf(reserveStudent);
    const lostStudentIndex = lost.indexOf(lostStudent);
    reserve.splice(reserveStudentIndex, 1);
    lost.splice(lostStudentIndex, 1);
    return reserve;
}
  • 풀이 과정
    1. lost 배열에 들어있지 않은 학생들은 체육복을 갖고 있음
      • 체육복을 갖고 있는 학생 수를 증가시킴
    2. lost 배열과 reserve 배열 둘 다에 들어 있는 학생들은 한 체육복을 잃어버려도 여분의 체육복을 갖고 있으므로 체육복을 갖고 있는 학생 수에 포함됨
      • lost 배열과 reserve 배열에서 해당 학생을 제거함
      • 체육복을 갖고 있는 학생 수를 증가시킴
    3. lost 배열의 학생의 앞 번호 학생이 reserve 배열에 포함되어 있고, lost 배열에 포함되어 있지 않는 경우 앞 번호 학생에게 체육복을 빌릴 수 있음
      • lost 배열에서는 해당 학생을 reserve 배열에서는 앞 번호 학생을 제거함
      • 체육복을 갖고 있는 학생 수를 증가시킴
    4. lost 배열의 학생의 뒷 번호 학생이 reserve 배열에 포함되어 있고, lost 배열에 포함되어 있지 않는 경우 뒷 번호 학생에게 체육복을 빌릴 수 있음
      • lost 배열에서는 해당 학생을 reserve 배열에서는 앞 번호 학생을 제거함
      • 체육복을 갖고 있는 학생 수를 증가시킴
  • n = 5, lost = [2, 4], reserve = [1, 3, 5]인 경우의 출력 결과
student No.student countlostreserve
11[ 2, 4 ][ 1, 3, 5 ]
22[ 4 ][ 3, 5 ]
33[ 4 ][ 3, 5 ]
44[][ 5 ]
55[][ 5 ]
  • n = 5, lost = [2, 4], reserve = [3]인 경우의 출력 결과
student No.student countlostreserve
11[ 2, 4 ][ 3 ]
22[ 4 ][]
33[ 4 ][]
54[ 4 ][]
  • 다른 풀이
function solution(n, lost, reserve) {
    let clothes = new Array(n).fill(1);
    
    lost.map((lostNumber) => clothes[lostNumber - 1] = 0);
    
    reserve.map((reserveNumber) => clothes[reserveNumber - 1] += 1);
    
    for (let i = 0; i < n; i++) {
        if (clothes[i] === 0 && clothes[i - 1] === 2) {
            clothes[i] = 1;
            clothes[i - 1] = 1;
        } else if (clothes[i] === 0 && clothes[i + 1] === 2) {
            clothes[i] = 1;
            clothes[i + 1] = 1;
        }
    }
    
    return clothes.filter((clothCount) => clothCount > 0).length;
}

Programmers Problem (lev.2) : 조이스틱

  • 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
    • ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
    • 조이스틱을 각 방향으로 움직이면 아래와 같습니다.
      • top : 다음 알파벳
      • down : 이전 알파벳 (A에서 아래로 이동하면 Z가 됨)
      • left : 문자열에서 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 위치가 됨)
      • rifht : 문자열에서 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 위취가 됨)
    • 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
    • 제한 사항
      • name은 알파벳 대문자로만 이루어져 있습니다.
      • name의 길이는 1 이상 20 이하입니다.

Solution

function solution(name) {
    const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    const reverse = 'ZYXWVUTSRGPONMLKJIHGFEDCBA';
    const nameArray = name.split('');
    let topDownMove = 0;
    let leftRightMove = name.length - 1;
    nameArray.forEach((str, index) => {
        const alphabetIndex = alphabet.indexOf(str);
        const reverseIndex = reverse.indexOf(str);
        if (alphabetIndex < reverseIndex) {
            topDownMove += alphabetIndex;
        } else {
            topDownMove += reverseIndex + 1;
        }
        const nameLength = name.length;
        let nextIndex = index + 1;
        while(nextIndex < nameLength && name[nextIndex] === 'A') {
            nextIndex++;
        }
        leftRightMove = Math.min(leftRightMove, (index * 2) + nameLength - nextIndex);
        leftRightMove = Math.min(leftRightMove, (nameLength - nextIndex) * 2 + index);
    });
    
    const answer = topDownMove + leftRightMove;
    return answer;
}
  • 풀이
    • 위, 아래 이동 횟수
      • 해당 문자열을 맞추기 위해 위로 조작했을 때 걸린 이동횟수와 아래로 조작했을 때 걸린 이동횟수를 비교해서 더 작은 이동횟수를 선택함
      • 이래로 조작했을 때 걸린 이동횟수 선택시, 방향을 바꾸기 위한 이동횟수가 더해지므로 1을 더함
    • 왼쪽, 오른쪽 이동 횟수
      • 모두 왼쪽으로만 조작했을 경우, 걸린 이동횟수는 문자열 길이 - 1임
      • 왼쪽으로 조작하다가 A가 나올 경우 오른쪽으로 조작했을 경우, 걸린 이동횟수는 (왼쪽 이동 횟수 * 2) + 문자열 길이 - 연속된 A의 길이임
      • 오른쪽으로 조작하다가 A가 나올 경우 왼쪽으로 조작했을 경우, 걸린 이동횟수는 (문자열 길이 - 연속된 A의 길이) * 2 + 왼쪽 이동 횟수임
      • 위 세가지 경우의 이동횟수를 비교하여 가장 작은 이동횟수를 선택함

Programmers Problem(lev.2) : 큰 수 만들기

  • 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
    • 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
    • 제한 조건
      • number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
      • k는 1 이상 number의 자릿수 미만인 자연수입니다.

Solution

function solution(number, k) {
    const stack = [];
    
    for (let index = 0; index < number.length; index++) {
        const digit = number[index];
        
        while(k > 0 && stack[stack.length - 1] < digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    stack.splice(stack.length - k, k); // pop이 k보다 적게 되었을 경우, splice로 남은 k를 제거함
    const answer = stack.join('');
    return answer;
}
  • 풀이
    • 스택을 사용하여 스택의 마지막 요소와 자릿수를 비교함
      • 스택의 마지막 요소가 자릿수보다 작다면, 마지막 요소를 빼고 자릿수를 넣고 k값을 감소시킴
      • 스택의 마지막 요소가 크다면, 그대로 두고 자릿수를 스택에 추가함
    • 모든 자릿수 비교 과정이 끝난 후에도 k값이 양수라면, stack에서 끝에서부터 남은 k만큼 삭제함
    • stack의 모든 숫자를 합쳐서 문자열로 만듬

Leetcode Problem : Assign Cookies

  • Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
  • Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
    • example 1
      Input: g = [1,2,3], s = [1,1]
      Output: 1Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
      And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
      You need to output 1.

Solution

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g.sort((a,b) => a - b);
    s.sort((a,b) => a - b);
    let childIndex = 0;
    let contentChildrenCount = 0;
    
    for (let cookieIndex = 0; cookieIndex < s.length; cookieIndex++) {
        if (s[cookieIndex] >= g[childIndex]) {
            childIndex++;
            contentChildrenCount++;
        }
        if (childIndex === g.length) {
            break;
        }
    }

    return contentChildrenCount;
};



LeetCode Problem : Split a String in Balanced Strings

  • Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

  • Given a balanced string s, split it into some number of substrings such that:

  • Each substring is balanced.

  • Return the maximum number of balanced strings you can obtain.

Constraints

  • 2 <= s.length <= 1000
  • s[i] is either 'L' or 'R'.
  • s is a balanced string.

Examples

  • Example 1

    • Input: s = "RLRRLLRLRL"
    • Output: 4
    • Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

  • Example 2

    • Input: s = "RLRRRLLRLL"
    • Output: 2
    • Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'. Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
    let countOfBalancedStr = 0;
    let countOfR = 0;
    let countOfL = 0;

    for (let i = 0; i < s.length; i++) {
        const str = s[i];
        if (str === 'R') {
            countOfR++;
        } else {
            countOfL++;
        }

        if (countOfR === countOfL) {
            countOfBalancedStr++;
            countOfR = 0;
            countOfL = 0;
        }
    }

    return countOfBalancedStr;
};
profile
이소라
이전 포스트

Algorithm - Greedy

다음 포스트

Algorithm - Exhausitive Search

post-custom-banner

0개의 댓글