알고리즘 공부 2일 차(기능 개발)

시작

이전에 봤던 주식 가격 문제와는 다르게 이해하는데 시간이 들지는 않았다.

문제 인식

내가 이해한 내용이다

1. progresses는 현재 진행된 작업 상태이다.
   [93, 30, 55]는 현재 첫번째 작업이 93% 완료되었고 두번째 작업은 30% 완료되었다는 말이다.
2. speeds는 하루에 진행 가능한 작업량이다.
   [1, 30, 5]는 하루에 작업이 가능한 작업량이다.
   하루가 진행되었을 때 첫번째 작업량은 1%가 늘어 94%가 되고 두번째 작업량은 30%가 늘어 60%가 된다.
3. 작업량이 100%가 되는 시점에 배포되는 작업의 수를 측정한다.
4. 단 이전 작업량이 100%가 안된다면 이전 작업량이 100%가 될 때 같이 배포된다.
   두번째 작업은 3일 뒤에 100%가 되지만 첫번째 작업은 7일이 지나야 100%가 되기 때문에 7일이 지나고 첫번째 작업량과 같이 배포된다.
5. 따라서 배포되는 작업의 수는 7일뒤에 2개, 9일 뒤에 1개로 [2, 1]이 된다.

문제 해결

문제를 해결하기 위해 구글을 검색을 했고 그 중 Stack/Queue와 관련된 코드를 찾았다.
다음은 내가 참고한 블로그이다. https://bangu4.tistory.com/299

import java.util.*;
class Solution {
    public int[] solution(int[] p, int[] s) {
    	
        Queue<Integer> q = new LinkedList<>();
        for (int i=0;i<p.length;i++)
            q.add((int) Math.ceil((100.0 - p[i]) / s[i]));
        
        List<Integer> res = new ArrayList<>();
        int cnt=0,top=q.peek();
        for (Integer i : q) {
            if(top>=i)
                cnt++;
            else{
                res.add(cnt);
                top = i;
                cnt=1;
            }
        }
        res.add(cnt);

        
        int[] answer = new int[res.size()];
        for(int i=0;i<res.size();i++)
            answer[i] = res.get(i);

        return answer;
    }
}

코드 해석

내가 해석한 내용이다.

public int[] solution(int[] p, int[] s) {
	Queue<Integer> q = new LinkedList<>();
	for (int i=0;i<p.length;i++)
		q.add((int) Math.ceil((100.0 - p[i]) / s[i]));

int 리스트 두개를 받는다.
q라는 이름의 새로운 queue 리스트를 만든다.
p의 배열의 크기만큼 시도를 한다.(for)
((100 - 현재 진행률) / 일일 작업량)을 한 후 나온 값과 같거나 큰 값 중 가장 작은 정수를 q에 대입한다.

List<Integer> res = new ArrayList<>();
int cnt=0,top=q.peek();
for (Integer i : q) {
	if(top>=i)
		cnt++;
	else{
		res.add(cnt);
		top = i;
		cnt=1;
	}
}
res.add(cnt);

res라는 이름의 새로운 리스트를 만든다.
cnt는 정수 타입이고 0이다. top은 q의 가장 처음 데이터이다.
q의 값을 i에 대입하고 q에서 대입할 값이 없을 때 까지 반복한다.(for)
만약 처음 데이터가 i보다 크거나 같으면 cnt가 1을 더한다.
처음 데이터가 i보다 작으면 res에 cnt값을 대입하고 top은 i로, cnt는 1로 변경한다.
res에 cnt를 추가한다.

소감

아직 직접 코드를 짜는것은 어렵게 느껴진다.
하지만 다른 사람의 코드를 보고 이해하는것은 이전에 문제를 풀어본 경험 덕분인지 시간이 많이 줄었다.