9월 4주차 문제 [ 2단계 ]

[Tokwasp]

📢 이번 주 알고리즘 스터디 문제

이번 주에는 총 4문제를 풉니다.
(정답률은 프로그래머스 기준)

---

📌 문제 목록 [ 2단계 ]

번호	문제	정답률	링크
1	기능개발	67%	🔗 바로가기
2	더 맵게	62%	🔗 바로가기

---

🗓️ 발표

• 시간: 금요일 오전 10시
• 방식: 각자 풀이 공유 + 코드 리뷰

---

🚨 벌금 규칙

• 문제를 풀지 않은 경우 → 💸 1만 원

---

🔥 이번 주도 화이팅입니다!

[dbrkdgus00]

기능개발

해결 방법

• 각 작업의 완료 날짜 계산
  progresses[i]가 100이 되려면 며칠 걸리는지 계산해서 days 배열에 저장한다.
  공식: (100 - 진행도 + 속도 - 1) / 속도 -> 올림 처리

• 큐로 배포 그룹 나누기
  처음 작업을 기준으로, 그보다 늦게 끝나는 작업이 나올 때까지 함께 배포 가능한 개수를 센다.
  이후 기준을 갱신하며 반복한다.

• 결과 리스트에 추가
  각 배포마다 몇 개의 기능이 포함됐는지 List에 담고, 최종적으로 배열로 변환해 반환한다.

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        // 정답 담을 리스트 (몇 개씩 배포했는지)
        List<Integer> answer = new ArrayList<>();

        // 먼저 각 작업이 며칠 뒤에 끝나는지 계산
        int[] days = new int[progresses.length];
        for (int i = 0; i < progresses.length; i++) {
            int left = 100 - progresses[i]; // 남은 작업량
            int day = (left + speeds[i] - 1) / speeds[i]; // 올림 처리
            days[i] = day;
        }

        // 첫 번째 작업 기준으로 비교 시작
        int standard = days[0]; // 현재 배포 기준일
        int count = 1;          // 현재 배포될 기능 수

        // 두 번째 작업부터 반복
        for (int i = 1; i < days.length; i++) {
            if (days[i] <= standard) {
                // 현재 작업이 이전 배포 기준보다 빨리 끝나면 같이 배포
                count++;
            } else {
                // 새로 배포 시작
                answer.add(count);      // 이전 배포 개수 저장
                standard = days[i];     // 새 기준일
                count = 1;              // 새 배포 시작
            }
        }

        // 마지막 남은 배포도 추가
        answer.add(count);

        // 리스트를 배열로 변환해서 리턴
        int[] result = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            result[i] = answer.get(i);
        }

        return result;
    }
}

더 맵게

해결 방법

• 작은 숫자부터 꺼낼 수 있는 큐에 음식들을 전부 넣음

• 가장 작은 음식 2개를 꺼내서 섞음
  섞은 값 = 첫 번째 + (두 번째 × 2)

• 섞은 결과를 다시 큐에 넣음

• 가장 작은 음식이 K 이상이 될 때까지 계속 반복

• 반복 횟수를 세서 리턴

• 만약 다 섞었는데도 K 이상 못 되면 -1을 리턴

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        // 우선순위 큐: 작은 숫자가 먼저 나옴
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // scoville 배열 큐에 다 넣기
        for (int s : scoville) {
            queue.add(s);
        }

        int mixCount = 0;

        while (queue.size() > 1) {
            int first = queue.poll();  // 가장 작은 값 꺼냄

            // 이미 K 이상이면 끝냄
            if (first >= K) {
                return mixCount;
            }

            int second = queue.poll(); // 두 번째 작은 값
            int newFood = first + (second * 2); // 새로 만든 음식
            queue.add(newFood); // 다시 넣기
            mixCount++; // 횟수 +1
        }

        // 마지막 하나가 K보다 작으면 실패
        if (queue.peek() < K) {
            return -1;
        }

        return mixCount;
    }
}

[sduddla]

1️⃣ 기능개발

function solution(progresses, speeds) {
    // progresses - 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열
    // speeds - 각 작업의 개발 속도가 적힌 정수 배열
    // 각 배포마다 몇 개의 기능이 배포되는 지 return
    
    // 각 작업이 얼마나 걸리는 지
    let days = [];
    for(let i = 0; i < progresses.length; i++) {
        let leftPercent = 100 - progresses[i];
        let day = Math.ceil(leftPercent / speeds[i]);
        days.push(day);
    }
    
    // 배포
    let result = [];
    let count = 1;
    for(let i = 1; i < days.length; i++) {
        if(days[i] <= days[0]) { // 현재 기능이 기준 기능보다 늦게 끝나지 않으면(같이 배포 가능)
            count++; // 카운트
        } else { // 현재 기능이 기준 기능보다 늦게 끝날 경우
            result.push(count); // 지금까지 모은 기능 배포
            days[0] = days[i]; // 기준일 업데이트
            count = 1; // 새 배포 시작
        }
    }
    
    result.push(count); // 마지막 배포
    return result;
}

---

2️⃣ 더 맵게

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    // 값 추가
    push(value) {
        this.heap.push(value); // 끝에 넣기
        let index = this.heap.length - 1;
        
        while(index > 0) { // 부모랑 비교해서 더 작으면 계속 위로 올리기
            let parentIndex = Math.floor((index - 1) / 2);
            if(this.heap[parentIndex] <= this.heap[index]) break;
            
            // 교환
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }
    
    // 최소값 꺼내기
    pop() {
        if(this.heap.length === 0) return null;
        if(this.heap.length === 1) return this.heap.pop();
        
        let min = this.heap[0]; // 루트값 (제일 작은 값)
        this.heap[0] = this.heap.pop(); // 마지막 원소 루트로
        
        let index = 0;
        while(true) {
            let left = index * 2 + 1;
            let right = index * 2 + 2;
            let small = index;
            
            if(left < this.heap.length && this.heap[left] < this.heap[small]) {
                small = left;
            }
            if(right < this.heap.length && this.heap[right] < this.heap[small]) {
                small = right;
            }
            if(small === index) break;
            
            // 교환
            [this.heap[index], this.heap[small]] = [this.heap[small], this.heap[index]];
            index = small;
        }
        
        return min;
    }
    
    // 최소값 반환
    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
    
    // 힙 크기 반환
    size() {
        return this.heap.length;
    }
}

function solution(scoville, K) {
    // 모든 음식의 스코빌 지수 k 이상으로
    // 섞은 횟수 최소, 불가능 -1
    
    let heap = new MinHeap();
    for(let s of scoville) heap.push(s);
    
    let count = 0;
    while(heap.size() > 1 && heap.peek() < K) {
        let first = heap.pop();
        let second = heap.pop();
        let newFood = first + second * 2;
        heap.push(newFood);
        count++;
    }
    return heap.peek() >= K ? count : -1;
}

[pia01190]

📌 기능개발

• 각 배포마다 몇 개의 기능이 배포되는지 ArrayList를 사용
• 일수 계산 후 기준일보다 크면 list에 add + count 초기화 / 작으면 count 증가

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> days = new ArrayList<>();
        int totalDay = calculateDays(progresses[0], speeds[0]);
        int count = 1;
        
        for (int i = 1; i < progresses.length; i++) {
            int day = calculateDays(progresses[i], speeds[i]);
            
            if (day > totalDay) {
                days.add(count);
                totalDay = day;
                count = 1;
            } else {
                count++;
            }
            
            if (i == progresses.length - 1) {
                days.add(count);
            }
        }
        
        int[] result = new int[days.size()];
        for (int i = 0; i < days.size(); i++) {
            result[i] = days.get(i);
        }
        
        return result;
    }
    
    private int calculateDays(int progresses, int speeds) {
        return ((100 - progresses) % speeds == 0) ?
            (100 - progresses) / speeds :
            (100 - progresses) / speeds + 1;
    }
}

📌 더 맵게

• 가장 작은 지수 2개를 꺼내 계산 후 맨 앞에 add 하기 위해 Deque 사용 -> 정렬이 되지않아 실패
• 우선순위 큐 사용

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> score = new PriorityQueue<>();
        for (int i : scoville) {
            score.add(i);
        }
        
        int count = 0;
        while (score.peek() < K && score.size() > 1) {
            int min = score.poll();
            int second = score.poll();
            score.add(min + second * 2);
            count++;
        }
        
        if (score.poll() < K) {
            return -1;
        }
        
        return count;
    }
}

[Tokwasp]

[ ⚙️ 기능 개발 ]

[ 구현 방법 ]

• 남은 작업 일수 책정 ( 100 - 진행도 / 스피드 )
• 큐에서 작업 일수를 꺼냈을 때 만약 7일이라면 7일 이하의 작업은 한번에 처리 가능
• 큐에 작업이 없을 때까지 반복
• 시간복잡도: 최대 작업 개수 : 100

public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>();
        
        // 남은 작업 퍼센트 / 스피드 = 남은 작업 일수
        for(int i = 0; i < progresses.length; i++){
            int progress = 100 - progresses[i];
            int speed = speeds[i];
            
            // 안나누어 떨어지면 + 1일
            if(progress % speed == 0){
                queue.add(progress / speed);    
            } else {
                queue.add((progress / speed) + 1);
            }
        }
  
        List<Integer> results = new ArrayList<>();
        while(!queue.isEmpty()){
            int num = queue.poll();
            int count = 1;
            
            // 앞의 남은 일수보다 작다면 처리 가능
            while(!queue.isEmpty() && queue.peek() <= num){
                queue.poll();
                count++;
            }
            results.add(count);
        }
        return results.stream().mapToInt(Integer::intValue).toArray();
    }

---

🌶️ [더 맵게]

[ 구현 방법 ]

• 알고리즘: 우선순위 큐 활용 ( 가장 작은 값을 두 개 꺼내야 하기 때문 )
• 시간 복잡도: 1,000,000 * log N ( 100만 개의 데이터 + 정렬 log N )

public int solution(int[] scovilles, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < scovilles.length; i++){
            pq.add(scovilles[i]);
        }
        
        int count = 0;
        while(pq.size() != 1){
            int scoville1 = pq.poll();
            int scoville2 = pq.poll();
            
            if(scoville1 >= K){
                return count;
            }
            pq.add(scoville1 + scoville2 * 2);
            count++;
        }
        
        // 예외 처리
        if(pq.poll() < K){
            return -1;
        }
        return count;
    }