🖋️ 그리디 알고리즘 풀이

체육복

• 일부 학생이 체육복을 도난
• 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주기
• 체육복이 없으면 수업을 들을 수 없음
• 체육 수업을 들을 수 있는 학생수 최대 구하기

학생들의 번호는 체격 순으로 매김
바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려주기 가능 
체육복이 도난당한 학생만 빌릴 수 있음

• 전체 학생의 수 n
• 체육복을 도난당한 학생들의 번호가 담긴 배열 lost
• 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve
• 체육수업을 들을 수 있는 학생의 최댓값을 return

• 그리디 코드

function solution(n, lost, reserve) {
    
    // 빌려야 하는 사람
    const noReserveStds = lost.filter((num) => !reserve.includes(num)).sort((a, b) => a -b);
    
    // 빌려줄 수 있는 사람
    let reserveStds = reserve.filter((num) => !lost.includes(num)).sort((a, b) => a -b);
    
    const answer = noReserveStds.filter((_lost) => {
        const lend = reserveStds.find((_reserve) => Math.abs(_lost - _reserve) === 1);
        
        if (!lend) return _lost;

        reserveStds = reserveStds.filter((v) => v !== lend);
    });
    
    return n - answer.length;
}

• 해석

@ 그리디 

- 지역 최적 선택
가장 가까운 학생에게 옷을 빌려주기 => 지역 최적의 선택을 만들기 
미래의 가능성을 내다보거나 결정을 재고하기 위해 되돌아가지 않음
각 결정은 현재 상태(빌린 바로 옆에 있는 사람)를 기반으로 이루어짐

- 단순성과 효율성
탐욕스러운 선택은 간단
물건을 빌려줄 수 있는 가장 가까운 학생을 찾기 
이러한 단순성은 복잡한 계산이 필요 없는 효율적인 솔루션으로 이어지는 경우


@ 정렬

- 정렬하지 않으면 알고리즘이 학생을 가장 일치하지 않는 사람과 
짝을 지어 잠재적으로 쌍이 형성되었더라도 도움을 받을 가능성이 없는 
다른 학생이 남을 수 있음

- 두 배열을 모두 정렬하면 알고리즘이 
항상 가장 가까운 학생을 쌍으로 연결

조이스틱

• 조이스틱으로 알파벳 이름을 완성
• 맨 처음엔 길이만큼 A로만 이루어짐
• 이름에 대해 조이스틱 조작 최소 횟수 구하기

@ 조이스틱을 각 방향으로 움직이기
	▲ - 다음 알파벳
	▼ - 이전 알파벳 
       		 (A에서 아래쪽으로 이동하면 Z로)
	◀ - 커서를 왼쪽으로 이동 
       		 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
	▶ - 커서를 오른쪽으로 이동
       		 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

• 만들고자 하는 이름 name
• 이름에 대해 조이스틱 조작 횟수의 최솟값을 return

• 코드

function solution(name) {
    const alpha = Array.from({length : 26}, (_, i) => String.fromCharCode('A'.charCodeAt(0) + i))
    let min_move = name.length - 1;
  
    return [...name].reduce((acc, cur, i) => {
        const cnt = Math.min(alpha.indexOf(cur), 26 - alpha.indexOf(cur));
        let idx = i + 1;
        
        // 연속으로 'A'가 있을 때 이동
        while (idx < name.length && name[idx] === 'A') {
            idx++;
        }
      
        // 일련의 'A'를 통해 앞으로 이동하는 것보다
        // 한 지점 이후 뒤로 이동하는 것이 더 빠른지 여부를 계산
        min_move = Math.min(min_move, i*2+name.length-idx, i+2*(name.length - idx));
        
        return acc + cnt;
    }, 0) + min_move;
}

• 해석

@ 변경수
    알파벳 앞부터 idx, 뒤부터 idx 중 최솟값 


@ 최소 이동 수
  'A'의 존재와 문자열 내 위치를 고려하여 
  필요한 전체 최소 이동을 추적
  
  - 순서대로		  	    => name.length - 1
  	 	ex ) name = "BCDEF"
        
  - 뒤로 돌아 가기	    => i * 2 + name.length - idx
    	ex ) name = "BAAAB"
        
        - 각 문자를 현재 문자까지 변경하기 위해 앞으로 이동 후(i)
        - 처음으로 뒤로 이동 후(i) 
        - 다시 끝으로 앞으로 이동하는 경우(name.length - idx)
         	ㄴ> 이미 이동한 수 + A 의 개수 제외한 name.length

  - 뒷 부분 먼저 입력(*)  => i + 2 * (name.length - idx)
      	ex ) name = "AAAACC"

		- 처음에 특정 지점까지 앞으로 이동한 다음 
          나머지 문자열을 처리하기 위해 
          랩을 하는 시나리오에서 필요한 이동 수

큰 수 만들기

• 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하기
  
  
• 문자열 형식으로 숫자 number
• 제거할 수의 개수 k
• number에서 k 개의 수를 제거했을 때
  만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return
  
  

• 코드

function solution(number, k) {
    let count = 0;
    const answer = [];

    for (let num of [...number]) {
        // k 미만으로 제외할 때 
        // answer 마지막 요소가 number[i] 보다 크면 방출
        while (count < k && num > answer.at(-1)) {                     			  answer.pop();
           count++;
        }

        // number - k 제외한 수 이하면 추가
        if (answer.length < number.length - k) {
            answer.push(num);
        }
    }

    return answer.join('');
}

• 더 좋은 코드

function solution(number, k) {
    const answer = [];
    let head = 0;
    let del = k;

    answer.push(number[head++]);
    while(answer.length < number.length - k || head < number.length) {
        // del 이 남아있고 
        // answer 의 마지막 요소가 number[head] 보다 작은 경우
        // Stack 의 LIFO 구조 이용
        if(del && answer.at(-1) < number[head]) {
            answer.pop();
            del--;
            continue;
        }
        // number 를 추가와 head++
        answer.push(number[head++]);
    }

    return answer.slice(0, number.length - k).join('');
}