[프로그래머스] PCCP 기출문제 1번(붕대감기)

※ 주의
정확한 답변도 아니거니와 개인적으로 풀어본 방식대로 기록하는 내용이므로 참고만 부탁드립니다.

 

 

[PCCP 기출문제] 1번 / 붕대 감기

https://school.programmers.co.kr/learn/courses/30/lessons/250137

프로그래머스

 

탐욕 알고리즘 (Greedy Algorithm)

 그리디 알고리즘은 최적해를 구하기 위해 항상 현재 상황에서 가장 좋아 보이는 선택을 하는 알고리즘입니다. 이 알고리즘은 각 단계에서 지금 당장 가장 이익이 큰 선택을 하는 것을 목표로 합니다. 그리디 알고리즘은 간단하고 직관적이며 일반적으로 실행 시간이 짧은 특징을 가지고 있습니다.

그리디 알고리즘은 다음과 같은 특징을 가지고 있습니다:

탐욕 선택 속성(Greedy-choice property): 각 단계에서 가장 이익이 큰 선택을 합니다.
최적 부분 구조(Optimal substructure): 각 단계에서의 선택이 전체 문제의 최적해를 구하기 위한 부분 문제의 최적해로 이어지는 경우에만 사용할 수 있습니다.

 

 하지만 그리디 알고리즘은 항상 최적해를 보장하지는 않습니다. 때로는 지금 당장의 선택이 나중에는 부적절한 선택으로 이어질 수 있기 때문입니다. 따라서 그리디 알고리즘을 사용할 때에는 주의가 필요합니다. 문제의 특성에 따라 그리디 알고리즘이 적합한지 판단하고 사용해야 합니다.

그리디 알고리즘은 다양한 문제에 적용될 수 있습니다. 예를 들면, 최소 신장 트리(Minimum Spanning Tree), 최단 경로(Shortest Path), 탐욕적 스케줄링(Greedy Scheduling) 등의 문제에 그리디 알고리즘이 사용될 수 있습니다.

 

문제 풀이

1. 각 구간은 크게 피해 구간과 회복 구간으로 나누어집니다.

2. 피해 구간을 음수, 회복 구간을 양수로 나누어 볼 수 있습니다.

3. 피해 구간 도달 시 최소 체력(0)에 대해 고려해야 하며, 0이 된 경우 즉각 다음 작업을 종료합니다.

4. 회복 구간  도달 시 최대 체력(health)에 대해 고려해야하며, 최대 체력을 넘어선 경우 최대 체력(health)으로 치환해주어야 합니다.

 

입출력 예 #1

입출력 예 #1

 

입출력 예 #2

입출력 예 #2

 

입출력 예 #3

입출력 예 #3

 

입출력 예 #4

입출력 예 #4

 

 

Solution.js

function solution(bandage, health, attacks) {
    var answer  = health;   // 현재 체력
    let amounts = [];       // 각 구간별 증가/감소 체력 양
    
    let st = 0;         // 회복 시작 시간
    for(let attack of attacks){
        let aTime   = attack[0];    // 공격받은 시간
        let aHit    = attack[1];    // 피해량
        
        // 최초 공격 이전까지의 회복량은 무시 (계속 MAX이므로)
        // 추가 회복 이후 연속 기준이 초기화 됨. 총 횟수 = (회복시간 /  시전시간) * 추가 회복량
            let bHealth = (aTime - st) * bandage[1] + Math.floor((aTime - st) / bandage[0]) * bandage[2];
        amounts.push(bHealth)
        
        // 피해량 추가
        amounts.push(aHit * (-1));
        
        st = aTime + 1;
    }
    
    // 체력 계산
    for(let amount of amounts){
        // 최대 체력 보다 높은 경우 = 최대 체력으로 변환
        if(answer + amount > health){
            answer = health;
            
        // 1보다 낮은 경우 = 사망
        } else if (answer + amount < 1){
            answer = -1;
            break;
            
        // 일반적인 체력 증가/감소
        } else {
            answer = answer + amount;
        }
    }
    
    return answer;
}

코드 실행 결과