[프로그래머스 고득점 kit 2차 정리] 그리디 (탐욕 알고리즘)

꿀팁

미래를 고려하지 않고 현재 시점에서 가장 좋은 선택

그냥 상남자 알고리즘, 경주마 알고리즘 이라고 생각해도 됨
그리디는 '잔돈 계산문제' 이거 하나로 종결할 수 있음
우리가 현금을 쓸 때 알바분이 10원, 100원짜리로만 잔돈을 주면 당연하게도 지폐를 찾는 것처럼 '가장 큰 거 먼저 해결하자'가 그리디의 전부

어떻게 정렬을 잘해야 하는지도 관건 -> 회의 문제로 치면 어떤 회의가 가장 빨리 끝나느냐가 관건임

정렬을 잘해서 문제를 빠르게 푼다

그리디는 DP의 사촌 동생격으로 매우 빠르다는 장점이 있음
-> DP는 모든 최적해를 고려하지만, 그리디는 고려하지 않음

그리디 관련 추천 문제

---

(Lv.1) 체육복

여기에서 배운점 (문법정리)

두 배열의 중복값 제거 방법

lost = lost.filter ( v => !reserve.includes(v))
reserve = reserve.filter ( v => !lost.includes(v))

★ 이렇게 하는 것의 문제점 
lost가 중복 제거가 된 상태에서 reserve의 중복 제거를 수행하기 때문에 
각각 변수에 할당한 다음 제거를 해줘야만함

let realLost = lost.filter(v => !reserve.includes(v)).sort((a, b) => a - b);
let realReserve = reserve.filter(v => !lost.includes(v)).sort((a, b) => a - b);

sort 사용법

sort()는 문자열 기준이므로 sort( (a,b) => a-b)를 활용해주어야함

풀이

function solution(n, lost, reserve) {
    // 여벌 체육복을 가진 학생이 도난당한 경우를 먼저 처리
    let realLost = lost.filter(v => !reserve.includes(v)).sort((a, b) => a - b);
    let realReserve = reserve.filter(v => !lost.includes(v)).sort((a, b) => a - b);
    
    let answer = n - realLost.length; 

    // 여벌 체육복을 가진 학생이 도난당하지 않은 학생들에게 빌려주기
    for (let i = 0; i < realLost.length; i++) {
        for (let j = 0; j < realReserve.length; j++) {
            // 절대값을 사용하여 두 값의 차이가 1일 때 빌려주고 사용한 사람 splice로 제거
            // shift로 제거하면 매칭되지 않는 애가 제거 될 수 있음
            if (Math.abs(realLost[i] - realReserve[j]) === 1) { 
                answer++; 
                realReserve.splice(j, 1); 
                break; // 체육복을 빌려주면 다음 잃어버린 학생으로 이동
            }
        }
    }

    return answer;
}

1. 우선 확정된 거는 answer의 최댓값으로 전체 학생 중에 진짜로 잃어버린 애들의 수를 뺴주면 됨

2. 진짜로 갖고온 애들을 돌며, realLost와 resalReserve의 절댓값 차이가 1인 애들을 발견하면 answer값을 올려주고 realReserve에서 해당 값을 splice(i, 1)을 통해 지워줌

3. break를 통해 진행 중이던 반복문을 탈출함

다른 사람의 풀이

filter의 순회를 통해 각 값과 절대값 차이를 계산 후 reserve에서 하나한 지워가며 한 풀이, 깔끔 그 자체

function solution(n, lost, reserve) {      
    return n - lost.filter(a => {
        const b = reserve.find(r => Math.abs(r-a) <= 1)
        if(!b) return true
        reserve = reserve.filter(r => r !== b)
    }).length
}

(Lv.2) 조이스틱

여기에서 배운점 (문법정리)

각 알파벳들의 거리차이는 아스키 코드를 통해 표현하면 됨

Math.abs('A'.charCodeAt(0) - 'J'.charCodeAt(0))

이런식으로 사용하면 9라는 순서가 나오게 됨

풀이

function solution(name) {
    let ans = 0;
    
    // UpDown 계산 함수
    for (let i=0; i < name.length; i++) {
        // 1. A보다 클수록 아스키 코드값은 올라가므로
        // 2. Z가 가장 크므로 거기에서 현재 빼주기
        ans += Math.min(
            name[i].charCodeAt(0) - 'A'.charCodeAt(0), 
            'Z'.charCodeAt(0) - name[i].charCodeAt(0) + 1
        );
    }

    // 커서 이동 계산 함수
    let minMove = name.length - 1; // 온전히 오른쪽으로만 이동했을 때 나오는 최댓값
    
    for (let i = 0; i < name.length; i++) {
        let next = i + 1;
        
        // A 갯수 카운팅
        while (next < name.length && name[next] === 'A') {
            next++; 
        }
        
        // i : 여태까지 이동해놨던 수
        // (i * 2) + (name.length - next) : 오른쪽으로 이동하다가 왼쪽으로 되돌아가는 경우
        // (name.length - next) * 2 + i : 왼쪽으로 이동했다가 다시 오른쪽으로 이동하는 경우
        minMove = Math.min(
            minMove,
            (i * 2) + (name.length - next),  // i만큼 온 걸 다시 되돌아 가고 반대편으로 가는 것
            (name.length - next) * 2 + i   // 오른쪽으로 온 만큼 다시 되돌아가고 
        );
    }

    ans += minMove; // 커서 이동 횟수 추가

    console.log('최종 정답:', ans);
    return ans;
}

updown 계산까지는 쉽다해도 커서 이동이 굉장히 까다로웠던 문제 같다

min의 인자로 세 개를 넣어
1. 정석
2. 왼쪽 가서 오른쪽으로 이동
3. 오른쪽 가서 왼쪽 이동

이렇게 중 가장 적은 값을 따져서 더해주면 됨

---

(Lv.2) 큰 수 만들기

여기에서 배운점 (문법정리)

string으로 된 숫자들을 정수배열로 바꾸는 방법

// ex number = '1924'
number = number.split('').map( v => Number(v))

반복문 진행하다가 조건에 부합하면 다시 처음으로 하는 방법 ★

    let i = 1;
    while (i < number.length) {
        if (stack.length === k) break;

        if (number[i-1] < number[i]) {
            stack.push(...number.splice(i-1, 1))
            i = 1;
        } else {
            i++
        }
    }

slice와 splice의 차이

[slice - 남기겠다]
let stack = [9, 8, 7, 6, 5, 4];
let k = 2;

stack = stack.slice(0, stack.length - k);
console.log(stack); // [9, 8, 7, 6]

0번째 인덱스부터 stack.length -k까지만 "남기겠다"

[splice - 자르겠다]
let stack = [9, 8, 7, 6, 5, 4];
let k = 2;

stack.splice(stack.length - k, k);
console.log(stack); // [9, 8, 7, 6]

stack.length-k부터, k까지를 "자를거임"

slice는 새로운 배열을 생성하고 splice는 원본 배열을 반환함

풀이

function solution(number, k) {
    let stack = [];
    
    // 어떻게 됐던 얘는 i가 number의 길이가 될 때까지만 반복
    for (let i = 0; i < number.length; i++) {
        let num = number[i];

        // 🔹 스택이 비어있지 않고
        // k가 남아 있으며
        // 스택의 '마지막 값'이 현재 탐색하는 값보다 작다면 제거
        while (stack.length > 0 && k > 0 && stack[stack.length - 1] < num) {
            stack.pop();
            k--;
        }

        stack.push(num); // 현재 숫자를 추가
    }
    
    // 🔹 아직 제거할 숫자가 남아 있으면 뒤에서 k개 삭제
    // ex. 만약 '9876'처럼 앞이 더 작은 경우가 없을 땐 뒤에서 k개 삭제
    // slice는 새로운 배열을 생성하고 splice는 원본 배열을 변경하지만
    // 여기에선 어차피 return만 하면 되니까 slice를 사용
    return stack.slice(0, stack.length - k).join('')
}

다른사람의 풀이

const solution = (number, k) => {
    const stack = [];
    let count = 0;
    for (let i = 0; i < number.length; i++) {
        const item = number[i]
        // stack이 초기에 비어있으면 push 한다.
        if (stack.length === 0) {
            stack.push(item)
            continue;
        }
        // stack에 쌓인 최근 값이 들어와야할 값보다 크거나 같을때까지 꺼낸다.
        while (stack[stack.length - 1] < item) {
            stack.pop()
            count++
            // 만약 숫자를 빼야할만큼 뺐다면 완성된 값을 반환한다.
            if (count === k) return stack.join("") + number.slice(i, number.length)
            // 스택이 비어있으면 루프를 멈추고 스택에 아이템을 추가한다.
            if (stack.length === 0) break;
        }
        stack.push(item)
    }
    // 만약
    return stack.join("").slice(0, number.length - k + count)
}

나와 동일한 로직을 가졌지만 차근차근 하나씩 풀어서 로직을 짠 게 인상적이었음
continue를 통해 조건문을 계속 진행하고 중간에 while문에서 완성이 된다면 그때 답을 return하며 그리고 stack이 채워지지 않을 땐 break를 통해 반복문 자체를 멈춘 후에

마지막에는 동일하게 (만약 숫자가 내림차순으로 진행된다면) 뒤에서부터 잘라서 넣는 것

---

(Lv.2) 구명보트

여기에서 배운점

투포인터 용법을 사용할 때 그리디에서 쓸 수 있게 두 합이 limit보다 작으면
slim을 하나 올려서 몸무게가 적은 사람도 태워주고 그렇지 않다면 뚱뚱한 애들은 무조건 태우는 식

    while (slim <= fat) {
        // 양끝의 합이 limit보다 작다면 왼쪽 사람 (제일 작은 애) 추가
        if (people[slim] + people[fat] <= limit) {
            // 왼쪽 증가 (제일 작은 애 제거)
            slim++; // 가벼운 사람 함께 태우기
        }
        
        //  오른쪽 감소 (제일 큰 애 제거)
        fat--; 
        ans++; 
    }

생각보다는 쉬웠던 문제이고 그리디의 장단점을 잘 보여주는 것 같음

풀이

function solution(people, limit) {
    people = people.sort( (a,b) => a-b);
    let ans = 0;
    
    let slim = 0;
    let fat = people.length - 1;

    while (slim <= fat) {
        // 양끝의 합이 limit보다 작다면 왼쪽 사람 (제일 작은 애) 추가
        if (people[slim] + people[fat] <= limit) {
            // 왼쪽 증가 (제일 작은 애 제거)
            slim++; // 가벼운 사람 함께 태우기
        }
        
        //  오른쪽 감소 (제일 큰 애 제거)
        fat--; 
        ans++; 
    }
    
    return ans;
}

stack이나 다른 것 활용할 필요도 없이

1. sorting으로 오름차순으로 정렬
2. 둘 합이 작다면 작은 애도 같이 태우기
3. 큰애는 무조건 태움

---

(Lv.3) 단속 카메라

풀이

function solution(routes) {
    // 진출 시점으로 정렬 (빨리 나가는 순)
    routes = routes.sort( (a, b) => a[1] - b[1])
    
    
    // 가장 빨리 나가는 경우에 우선 설치
    let camera = 1;
    let lastCameraPosition = routes[0][1];
    
    for(let i=1; i<routes.length; i++) {
        if (routes[i][0] > lastCameraPosition) {
            lastCameraPosition  = routes[i][1];
            camera++
        }
    }
    
    return camera
}

풀고나서 또잉 했던 문제

1. 처음에 나가는 곳에 카메라를 설치하고
2. 그 후로 지나가는 애들마다 카메라를 주는데
3. 걔네가 나가는 시점이 카메라 안쪽 범위에 있으면 새로 설치를 하지 않고
4. 카메라를 지나서 나가면 당연하게 카메라를 설치 해줘야함