프로그래머스 - 기능개발 (JAVA)

프로그래머스 기능개발 풀이 과정
큐 두 개를 굴리다가 인덱스 동기화 실수로 1차에 틀렸다.
2차에서 큐 하나로 정리하며 통과

---

1트 (오답)

→ progresses와 speeds를 각각 별도의 Deque에 담는다.
→ 매 라운드마다 전체 순회하며 속도를 더한 뒤, 앞에서부터 100 이상인 항목을 꺼내 카운트한다.

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Deque<Integer> pg = new LinkedList<>();
        Deque<Integer> sp = new LinkedList<>();

        for(int i=0; i<speeds.length; i++) {
            pg.offer(progresses[i]);
            sp.offer(speeds[i]);
        }

        List<Integer> list = new ArrayList<>();
        while(!pg.isEmpty()) {
            int size = pg.size();
            int cnt = 0;

            for(int i=0; i<size; i++) {
                int curProg = pg.poll();
                int curSpd = sp.poll();

                pg.offer(curProg+curSpd);
                sp.offer(curSpd);
            }

            for(int i=0; i<size; i++) {
                int cur = pg.peek();

                if(cur >= 100) {
                    pg.poll();
                    cnt++;
                }
                else break;
            }
            if(cnt > 0) list.add(cnt);
        }

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

        return answer;
    }
}

위 풀이의 결과

• 발상 자체는 맞다. 큐를 라운드 단위로 순회하며 진도를 갱신하고, 앞에서부터 완료된 기능을 꺼내 묶는다는 흐름은 올바르다.
• 문제는 속도 큐(sp)를 함께 굴리는 과정에서 인덱스 동기화가 어긋난다는 점이다. 진도와 속도를 각각 분리된 덱에 넣고 poll → offer를 반복하면, 라운드가 거듭될수록 pg와 sp의 원소 순서가 뒤섞인다.
  • 진도 업데이트 루프에서 pg.poll()과 sp.poll()을 같이 꺼내 더한 뒤 다시 offer한다.
  • 이때 완료 판정 루프에서 pg.poll()로 꺼낸 원소에 대응하는 속도가 sp에서도 동시에 빠져야 하는데, 그냥 놔두니 두 덱 사이에 원소 수 불일치가 생긴다.

---

2트 (정답)

→ 속도 덱을 없앴다.
→ 앞 작업이 100을 넘어야만 뒤 작업도 덱에서 빠져나올 수 있으므로, 덱에서 빠져나간 수만큼 speeds 앞부분을 건너뛰면 현재 덱에 남아 있는 작업의 속도를 정확히 참조할 수 있다.

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        // 우선 순서대로 큐에 작업진도 삽입
        Deque<Integer> dq = new LinkedList<>();
        for(int pro : progresses) {
            dq.offer(pro);
        }

        // 작업진도 최신화
        List<Integer> list = new ArrayList<>();
        while(!dq.isEmpty()) {
            int size = dq.size();

            for(int i=0; i<size; i++) {
                dq.offer(dq.poll() + speeds[speeds.length - size + i]); // 기존작업의 개수 - 현재 큐 사이즈 + i = 해당 작업의 속도
            }

            // 앞에서부터 검사하며, 100이 넘으면 카운트, 안 넘는 즉시 반복 탈출
            int cnt = 0;
            for(int i=0; i<size; i++) {
                if(dq.peek() >= 100) {
                    dq.poll();
                    cnt++;
                }
                else break;
            }

            // 카운트가 0보다 클 경우 리스트 추가
            if(cnt>0) list.add(cnt);
        }

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

        return answer;
    }
}

위 풀이의 핵심: speeds[speeds.length - size + i]

이 문제의 배포 조건은 앞 작업이 100을 넘어야만 뒤 작업도 함께 배포된다는 것이다. 즉 덱에서 빠져나오는 순서는 반드시 앞에서부터이고, 중간이나 뒤에서 먼저 빠져나오는 일은 없다.

이러한 특성을 반영해서, 현재 덱에 size개의 원소가 남아 있다는 건 speeds 배열의 앞에서부터 speeds.length - size개가 이미 완료돼 빠져나갔다는 의미가 된다. 따라서 지금 덱의 i번째 원소에 해당하는 속도는 speeds[speeds.length - size + i]로 정확히 역산할 수 있다. 속도 덱을 따로 굴릴 필요 없이, 빠져나간 수만큼 원배열의 시작점을 밀면 그만이다.

• 배포 순서의 특성(앞이 완료돼야 뒤도 빠져나옴) 파악 → 덱 이탈 순서가 보장됨을 확인
• 빠져나간 수 = speeds.length - size 로 시작 인덱스 역산

---

1트에서 두 덱을 함께 굴리다 꼬인 건, 완료 판정 시점에 속도 덱을 동기화하지 않아서였다. 하지만 진짜 핵심은 그 앞에 있었다. 이 문제는 앞 작업이 100을 넘어야만 뒤 작업도 빠져나올 수 있다는 조건 덕분에, 덱의 이탈 순서가 항상 보장된다. 그걸 파악하고 나면 속도 덱 자체가 필요 없어진다는 게 자연스럽게 따라온다. 문제의 조건을 자료구조 설계에 연결해서 생각하는 연습이 더 필요하다고 느꼈다.