문제

• 링크

  title: "코딩테스트 연습 - 야근 지수"
  image: "https://image.freepik.com/free-vector/landing-page-template-for-a-website_23-2147782747.jpg"
  description: "회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요."
  url: "https://school.programmers.co.kr/learn/courses/30/lessons/12927"
  

---

문제 풀이

문제 접근

처음 문제를 접했을 때, 가장 큰 작업량을 우선적으로 줄여야 피로도를 최소화할 수 있다고 생각했습니다.
따라서, 작업량을 내림차순 정렬한 후 가장 큰 값부터 감소시키는 방법을 고민했습니다.

• 초기 접근 방법:
  • 작업량을 내림차순 정렬
  • 가장 큰 값을 선택하여 n시간 동안 반복해서 1씩 감소
  • 감소 후 다시 정렬 반복
• 문제점 발견:
  • 매 반복마다 Arrays.sort() 사용 → 시간 복잡도 O(n * m log m)
  • 효율성 테스트에서 실패 (특히 n과 작업량 개수가 클 때 시간 초과 발생)
• 개선 아이디어:
  가장 큰 값을 빠르게 찾아서 수정하려면 힙 자료구조 사용이 적합합니다.
  자바의 우선순위 큐(PriorityQueue)를 최대 힙 형태로 사용하면,
  가장 큰 값 추출 & 삽입을 O(log m)으로 처리할 수 있어 효율성 문제 해결에 도움이 됩니다.

---

간단한 수도 코드 정리

1. works 배열을 최대 힙에 추가
2. n 시간 동안 반복:
   - 가장 큰 값 추출
   - 값이 0이면 반복 중단 (작업 끝)
   - 값 감소 후 힙에 다시 추가
3. 남은 작업량 제곱 합을 계산하여 반환

---

풀이 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        // 최대 힙 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        // 작업량 큐에 추가
        for (int work : works) {
            pq.offer(work);
        }

        // N 시간 동안 가장 큰 작업량 처리
        for (int i = 0; i < n; i++) {
            int max = pq.poll(); // 가장 큰 값 추출
            if (max == 0) break;  // 남은 작업이 없으면 중단
            pq.offer(max - 1);    // 작업량 감소 후 재삽입
        }

        // 야근 피로도 계산
        long answer = 0;
        for (int work : pq) {
            answer += (long) work * work;
        }

        return answer;
    }
}

---

오류 해결

❌ 발생한 문제:

• 문제 상황:
  초기 코드에서는 매 반복마다 Arrays.sort()를 호출했습니다.

  Arrays.sort(sortWorks, Collections.reverseOrder());
  

• 에러 원인:
  • Arrays.sort()의 시간 복잡도: O(m log m)
  • 이를 n번 반복하면 O(n * m log m)으로 비효율적
  • 결국, 효율성 테스트 실패 (시간 초과) 문제 발생

---

✅ 해결 과정:

• 최대 힙 사용 (PriorityQueue) → O(log m)로 개선
• 정렬 반복 제거 후, 가장 큰 값 추출 및 삽입만 반복

✅ 결과: 효율성 통과 + 빠른 실행 시간 확보!

---

느낀점 & 회고

• 처음엔 단순히 정렬로 접근했지만, 효율성 문제를 고려하지 못했던 점을 깨달았습니다.
• 문제에서 “가장 큰 값을 반복적으로 선택”하는 상황이라면 힙 자료구조를 떠올려야 한다는 교훈을 얻었습니다.
• 실제로 우선순위 큐를 활용하니, 시간 초과 문제가 깔끔하게 해결되었습니다! 😎

---

✅ 앞으로도 비슷한 문제에서 정렬 반복 대신 우선순위 큐 사용을 적극 고려하기!