42586 - 기능개발

info

• 문제 보기: 42586 - 기능개발
• 소요 시간: 20분 20초
• 풀이 언어: java
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

큐 그리디 구현

풀이 코드

info

• 메모리: 87900 KB
• 시간: 2 ms

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {  
        int cnt = 0;
        int day = 0;
        List<Integer> ansList = new ArrayList<>();
        for (int i = 0; i < progresses.length; ++i) {
            int p = progresses[i];
            int s = speeds[i];
            
            if (p + s*day > 99) ++cnt; // 1. can release
            else { // 2. can't release
                // save total releases (skip if 0)
                if (0 < cnt) ansList.add(cnt);
                cnt = 0;
                
                // calc required days to release
                day = (100-p) / s;
                if ((100-p) % s != 0) day += 1;
                
                ++cnt;
            }
        }
        ansList.add(cnt);
        
        return ansList.stream().mapToInt(i->i).toArray();
    }
}

풀이 해설

이게 왜 스택/큐 문제인지 모르겠다. 정 시뮬레이션처럼 풀이할거면 큐를 쓸 것 같긴 하다.

하지만 굳이 시뮬까지 돌릴 필요 없이 그리디하게 풀면 $O(n)$으로 컷이 난다.

⚡ Think GREEDY

맨 앞 녀석이 배포되는데 필요한 일자를 계산해주고

그 뒤의 녀석들은 해당 일자만큼 진행도를 올려서 100이상이면 같이 배포하고

안되면 배포 개수 카운터를 ansList에 저장 후 초기화한 뒤 다시 필요 일자를 계산해주면 되는 문제이다.

그리고 카운터 꼬다리값 꼭 처리해주세요

for (int i = 0; i < progresses.length; ++i) {
    ...
}
ansList.add(cnt);

return ansList.stream().mapToInt(i->i).toArray();

카운터 저장 조건이 배포 못할 때라서, 순회가 끝나면 무조건 꼬다리가 남는다.

메모

• 정 복습할거면 한번 읽어보고 넘기기