10월 3주차 문제 [ 2단계 ]

[Tokwasp]

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

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

---

📌 문제 목록 [ 2단계 ]

번호	문제	정답률	링크
1	롤케이크 자르기	65%	🔗 바로가기
2	요격 시스템	41%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[sduddla]

1️⃣ 롤케이크 자르기

function solution(topping) {
    
    let result = 0; // 공평하게 자르는 방법의 수
    
    const right = new Map();
    for(const t of topping) {
        right.set(t, (right.get(t) || 0) + 1);
    }
    
    const left = new Map();
    
    // 왼쪽으로 하나씩 옮기면서 비교
    for(let i = 0; i < topping.length - 1; i++) {
        const t = topping[i];
        
        // 오른쪽에서 하나 빼기
        right.set(t, right.get(t) - 1);
        if(right.get(t) === 0) right.delete(t); // 다 쓴 토핑 삭제
        
        // 왼쪽에 추가
        left.set(t, (left.get(t) || 0) + 1);
        
        if(left.size === right.size) result++;
    }
    return result;
}

---

2️⃣ 요격 시스템

function solution(targets) {
    // [1, 4] [4, 5] [3, 7] [4, 8] [5, 12] [11, 13] [10, 14]
    
    // 끝나는 지점 오름차순 정렬
    targets.sort((a, b) => a[1] - b[1]);
    
    let count = 0;
    let point = -1; // 요격한 포인트 없음
    
    for(const [start, end] of targets) {
        if(start >= point) {
            count++;
            point = end;
        }
    }
    return count;
}

[dbrkdgus00]

롤 케이크 자르기

해결 방법

• 토핑 번호는 1~10000이므로 배열을 써서 토핑 개수를 관리한다.

• 처음엔 모든 토핑을 오른쪽 조각에 넣어두고, 종류 수도 센다.

• 하나씩 왼쪽 조각으로 옮기면서 왼쪽/오른쪽에 있는 토핑의 종류 수를 각각 센다.

• 두 조각의 종류 수가 같아지는 지점마다 정답을 1씩 증가시킨다.

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        // 1~10000번 토핑 종류이므로 배열 사용
        int[] left = new int[10001];   // 왼쪽 토핑 종류별 개수
        int[] right = new int[10001];  // 오른쪽 토핑 종류별 개수

        int leftTypeCount = 0;   // 왼쪽 토핑 종류 수
        int rightTypeCount = 0;  // 오른쪽 토핑 종류 수

        // 1. 먼저 전체를 오른쪽에 다 넣어두기
        for (int t : topping) {
            if (right[t] == 0) {
                rightTypeCount++; // 처음 등장한 토핑
            }
            right[t]++;
        }

        // 2. 하나씩 왼쪽으로 옮겨가며 비교
        for (int i = 0; i < topping.length; i++) {
            int t = topping[i];

            // 왼쪽으로 추가
            if (left[t] == 0) {
                leftTypeCount++;
            }
            left[t]++;

            // 오른쪽에서 제거
            right[t]--;
            if (right[t] == 0) {
                rightTypeCount--;
            }

            // 공평하게 나뉜 경우
            if (leftTypeCount == rightTypeCount) {
                answer++;
            }
        }

        return answer;
    }
}

요격 시스템

해결 방법

• 미사일의 끝나는 지점 기준으로 정렬
  -> 빨리 끝나는 것부터 처리하면 최소한의 요격 수로 커버

• 요격이 필요한 경우에만 카운트
  -> 직전 요격 위치보다 현재 미사일의 시작점이 더 크거나 같다면, 새로운 요격 미사일을 발사

• 요격은 해당 미사일의 끝점에서 발사하면 가장 많은 미사일을 커버할 수 있음

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // 1. 끝나는 시점을 기준으로 오름차순 정렬
        Arrays.sort(targets, (a, b) -> a[1] - b[1]);

        int count = 0;         // 요격 미사일 수
        int lastShot = 0;      // 마지막 요격 위치

        for (int[] target : targets) {
            int start = target[0];
            int end = target[1];

            // 현재 미사일이 아직 요격 안된 경우
            if (start >= lastShot) {
                count++;          
                lastShot = end;  // [start, end) 범위니까 end 에서 쏘면 됨
            }
        }

        return count;
    }
}

[Tokwasp]

🧩 [ 롤케이크 자르기 ]

⚙️ 문제 풀이

• 케이크를 두 조각으로 나눌때 토핑의 종류 개수가 같게 나눠지는 경우의 수
• 종류와 개수 기록 위해 배열 사용
• 시간 복잡도: O(N) = 100만

class Solution {
    public int solution(int[] toppings) {
        int[] cake = new int[10001];
        int cake1Topping = 0;
        
        // 토핑이 몇 종류 몇개 인지 파악 하기
        for(int i = 0; i < toppings.length; i++){
            int topping = toppings[i];
            
            if(cake[topping] == 0){
                cake1Topping++;
            }
            cake[topping]++;
        }

        int[] cake2 = new int[10001];
        int cake2Topping = 0;
        int total = 0;
        
        // 케이크 나누기
        for(int i = 0; i < toppings.length; i++){
            int topping = toppings[i];
            
            cake[topping]--;
            if(cake[topping] == 0){
                cake1Topping--;
            }
            
            if(cake2[topping] == 0){
                cake2Topping++;
                cake2[topping]++;
            }
            
            // 자른 케이크의 토핑 개수가 같다면
            if(cake1Topping == cake2Topping){
                total++;
            }
        }
        return total;
    }
}

---

[ Map 풀이 ]

class Solution {
    public int solution(int[] toppings) {
        Map<Integer, Integer> yourToppingMap = new HashMap<>();

        // input 처리
        for(int i = 0; i < toppings.length; i++){
            int topping = toppings[i];
            yourToppingMap.put(topping, yourToppingMap.getOrDefault(topping, 0) + 1);
        }

        // 내 케이크
        Map<Integer, Integer> myToppingMap = new HashMap<>();

        int count = 0;
        for(int i = toppings.length - 1; i >= 0; i--){
            int topping = toppings[i];
            myToppingMap.put(topping, myToppingMap.getOrDefault(topping, 0) + 1);

            // 상대편 토핑 줄이기
            int nextTopping = yourToppingMap.get(topping) - 1;
            if(nextTopping == 0){
                yourToppingMap.remove(topping);
            } else {
                yourToppingMap.put(topping, nextTopping);
            }

            if(yourToppingMap.size() == myToppingMap.size()){
                count++;
            }
        }
        return count;
    }
}

---

[ 요격 시스템 ]

⚙️ 문제 풀이

• [ 1, 10 ] / [ 2, 3 ] = 1개
• [ 1, 10 ] / [ 11, 12 ] = 2개
• 요격 끝점과 다음 요격의 시작점과 관련
• [ 1, 10 ] / [ 2, 3 ] / [ 3, 7 ] = 2개
• [ 1, 10 ] / [ 2, 3 ] / [ 3, 7 ] / [ 8, 13 ] = 3개
• 요격의 시작점이 이전 요격 끝점보다 이하라면 요격 추가
• 아닌 경우 [ 1, 10 ] / [ 2, 11 ] or [ 1. 10 ] / [ 2, 5 ]
• 두 경우 모두 이전 끝점과 현재 끝점 중 작은것으로 갱신

class Solution {
     public int solution(int[][] targets) {
        Arrays.sort(targets, (a,b) -> a[0] - b[0]);

        int count = 1;
        int end = targets[0][1];

        for (int row = 1; row < targets.length; row++) {
            int start = targets[row][0];
            int currentEnd = targets[row][1];

            if (end <= start) {
                count++;
                end = currentEnd;
            } else {
                end = Math.min(end, currentEnd);
            }
        }

        return count;
    }
}