탐욕법

탐욕법은 DP처럼 최적해를 구하는데 사용되지만.

DP 처럼 모든 경우가 아닌 어떤 상황의 최대값을 규칙을 찾아 구한다.

그렇기 때문에 효율적이나, 그 만큼 정확하진 못하다.

탐욕법은 DP와 달리 배열을 순회하며, 그 배열을 직접 조절하여 답을 찾는 경우가 많다.

조건에 맞는 배열을 만든 후 답을 출력 하는 패턴을 가지는게 일반적이다.

패턴을 찾기 위해서 배열 정렬을 자주 사용한다.

체육복

맨 앞과 맨 뒤의 학생의 경우에 index를 벗어나는 경우만 신경 써주자.

나머지는 lost가 reserve를 만날때, 값을 수정해주며 답을 찾으면 된다.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> students(n,1);
    
    for(auto a : reserve){
        students[a-1]++;
    }    
    for(auto a : lost){
        students[a-1]--; 
    }
    
    for(int i=0; i<students.size();i++){ 
        if(i!=0&&students[i]==0){ //맨 앞이 인덱스를 벗어나는 경우
            if(students[i-1]==2){
                students[i]++; 
                students[i-1]--;
                continue; 
            }
        }
        if(i!=students.size()-1&&students[i]==0){  // 맨 뒤가 인덱스를 벗어나는 경우
            if(students[i+1]==2){ 
                students[i]++; 
                students[i+1]--;
            }
        }
                   
    }
    
    for(auto a : students){
        a>0 ? answer++:0;
    }
       
    return answer;
}

조이스틱

DP로 푸는 것 처럼 보이지만 제한시간을 충족하기 위해서 탐욕법으로 풀어야 한다.

모든 인자를 돌면서, 정방향으로 알파벳을 변화시켜야 하는지, 역방향으로 변화시켜야 하는지 판단하여 그 수를 누적한다.

 

그 후에 따로 인자를 정방향으로 이동하며 작업할지 , 역방향으로 이동하여 작업할지 계산해 준다.

 

이 때, 각 조건들을 따로 접근한다는 것이 핵심이다.

 

function solution(name) {
    let answer = 0;
    let length, reverseLength;
 
    answer = Array.from(name).reduce((count, char) => {
        if (char !== 'A') {
            if (char.charCodeAt(0) - 'A'.charCodeAt(0) < 'Z'.charCodeAt(0) - char.charCodeAt(0) + 1) {
                count += char.charCodeAt(0) - 'A'.charCodeAt(0);
            } else {
                count += 'Z'.charCodeAt(0) - char.charCodeAt(0) + 1;
            }
        }
        return count;
    }, 0);
 
    for (let i=1; i < name.length; i++) {
        if (name[i] !== 'A') {
            reverseLength = name.length - i;
            break;
        }
    }
 
    for (let i=name.length; i > 0; i--) {
        if (name[i] !== 'A') {
            length = i;
            break;
        }
    }
 
    return answer + (length < reverseLength ? length : reverseLength);
}

큰 수 만들기

모든 인자를 반복하며, 조건에 충족한 값을 배열에 담아 답을 찾는다.

이 때 조건 중에 재밌는 점은

N 번쨰 자리 수는 배열의 맨뒤에서 부터 N번 이상 인덱스에 위치해야 하는 점이다.

ex) 12345 시 넷째 자리 수를 만들려면 천의 자리 수는 1 혹은 2 만 가능하다.

이를 이용하여 k를 자리수에 맞춘 값으로 사용할 수 있다.

 

마지막 splice 조건은

(10000, 2) 와 같은 경우에 100이 나와야 하는데

0 == 0 와 같이 같은 경우가 갯수보다 많이 나오는 경우는 처리 할수 없게 되기 때문에

마지막에 splice를 통해서

N개부터 K만큼 버린다.

function solution(number, k) {
    const array = [];
    for (let i = 0; i < number.length; i++) {
        var target = number[i];
        while (k > 0 && array.length > 0 && array[array.length - 1] < target) {
            array.pop();
            k--;
        }
        
        array.push(target);
    }
    array.splice(array.length - k, k);
    var answer = array.join('');
    answer
    return answer;
}

구명보트

구명보트를 최적으로 탈 조건은

가장 가벼운 사람과 가장 무거운 사람을 동시에 태웠을 때 태울 수 있어야 한다.

이를 위해 정렬 한다.

(한번에 최대 두명씩 탈 수 있기 때문에 가장 무거운 사람 둘을 태워도 크게 의미 없다.)

그렇기 때문에

for문의 인덱스는 만약 동시에 탈땐 i가 증가하고

아닐 경우에는 j가 뒤에서부터 하나씩 줄어든다.

i 가 증가함은 동시에 탈수 있었음을 의미하게 되어 다음과 같은 답을 리턴한다.

function solution(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}

단속 카메라

경로 상의 겹치는 지점을 찾는 문제이다.

출발 지점 혹은 끝지점을 기준으로 정렬을 한 후

나머지 지점을 변경해가며 답을 찾아 나간다.

 

아래의 코드는 출발지점이 작은 순, 곧 가장 긴 입구 순으로 정렬을 했다.

그리고 그 입구의 출구를 통과 가능한 출구로 지정 한 후에

다음번 째 경로의 입구가 통과 가능한 출구에 속해 있을 때, 

통과가 가능하다.

 

주의 할 점은 통과 가능한 출구 지점이 더 좁아 질 수 있다는 점이다.

문제를 예시로 들면

첫 번째 통과 가능한 출구는 15까지 이지만,

[-14,-5] 를 통과 할 경우에

통과 가능한 출구는 -5로 바뀐다.

function solution(routes) {
    var answer = 0;
 
    routes.sort(function(a, b) { 
        return a[0] - b[0];
    });
 
    while(routes.length > 0){ 
        let end = routes[0][1]; 
        answer++;
        for(var i=0; i<routes.length;i++){ 
            if(end >= routes[i][0]){ 
                if(end > routes[i][1]){ 
                    end = routes[i][1];
                }
                routes.shift()
                i--;
            }
        }
    }
 
    return answer;
}