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

[Tokwasp]

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

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

---

📌 문제 목록 [ 2단계 ]

번호	문제	정답률	링크
1	[ 1차 ] 캐시	66%	🔗 바로가기
2	이모티콘 할인 행사	42%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[pia01190]

📌 캐시

• 시간복잡도 ok -> for문으로 탐색
• 순서를 알아야하기 때문에 Queue 사용
• cache hit -> 기존 위치 제거 + 맨 뒤에 추가
• cache miss -> 맨 뒤에 추가 + cacheQueue.size() == cacheSize 일 때 poll()

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
        }
        
        List<String> cacheList = new LinkedList<>();
        int time = 0;
        
        for (int i = 0; i < cities.length; i++) {
            // cacheList가 비어있지않고 다 차지않은 경우
            if (cacheList.size() < cacheSize && !cacheList.isEmpty()) {
                if (cacheList.contains(cities[i])) {
                    time += 1;
                    cacheList.remove(cities[i]);
                    cacheList.add(cities[i]);
                } else {
                    time += 5;
                    cacheList.add(cities[i]);
                }
            } else if (cacheList.isEmpty()) { // cacheList가 비어있는 경우
                time += 5;
                cacheList.add(cities[i]);
            } else if (cacheList.size() == cacheSize) { // cacheList가 다 찬 경우
                if (cacheList.contains(cities[i])) {
                    time += 1;
                    cacheList.remove(cities[i]);
                    cacheList.add(cities[i]);
                } else {
                    time += 5;
                    cacheList.remove(0);
                    cacheList.add(cities[i]);
                }
            }
        }
        
        return time;
    }
}

• 리팩토링 후

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
        }
        
        Queue<String> cacheQueue = new LinkedList<>();
        int time = 0;
        
        for (int i = 0; i < cities.length; i++) {
            String city = cities[i];
            
            if (cacheQueue.contains(city)) {
                cacheQueue.remove(city);
                cacheQueue.add(city);
                time += 1;
            } else {
                if (cacheQueue.size() == cacheSize) {
                    cacheQueue.poll();
                }
                
                cacheQueue.add(city);
                time += 5;
            }
        }
        
        return time;
    }
}

📌 이모티콘 할인 행사

• users의 길이 : 100
• emoticons의 길이 : 7
• 할인율의 길이 : 4
  -> 완전 탐색

class Solution {
    public int[] solution(int[][] users, int[] emoticons) {
        int[] discount = {10, 20, 30, 40};
        int[] emoticonDiscount = new int[emoticons.length];
        
        return dfs(discount, emoticonDiscount, users, emoticons, 0);
    }
    
    private static int[] dfs(int[] discount, int[] emoticonDiscount, int[][] users, int[] emoticons, int count) {
        if (count == emoticons.length) {
            int joinCount = 0; // 이모티콘 플러스 서비스 가입 수
            int totalPrice = 0; //  이모티콘 매출액
            
            for (int i = 0; i < users.length; i++) {
                int minRate = users[i][0];
                int money = users[i][1];
                int price = 0;

                for (int j = 0; j < emoticons.length; j++) {
                    if (emoticonDiscount[j] >= minRate) {
                        price += emoticons[j] * (100 - emoticonDiscount[j]) / 100;
                    }
                }

                if (price >= money) {
                    joinCount++;
                } else {
                    totalPrice += price;
                }
            }

            return new int[] {joinCount, totalPrice};
        }

        int[] answer = {0, 0};
        for (int rate : discount) {
            emoticonDiscount[count] = rate;
            int[] result = dfs(discount, emoticonDiscount, users, emoticons, count + 1);
            answer = max(answer, result);
        }

        return answer;
    }
    
    private static int[] max(int[] answer, int[] result) {
        if (result[0] > answer[0]) {
            return result;
        } else if (answer[0] == result[0] && result[1] > answer[1]) {
            return result;
        }
        
        return answer;
    }
}

[Tokwasp]

🗂 [1차] 캐시

[ 시간 복잡도 ]

• 캐시 크기: 30
• 최대 도시 수: 100,000
• 총 예상 연산: 30 * 100,000 = 3,000,000
• 이유: List 사용 시, 맨 앞 데이터 제거 O(N) * 최대 도시 수

[ 캐시 처리 주의 ]

• ❌: 맨 앞 데이터를 삭제 후 데이터 삽입
• ✅: 이미 캐시에 있는 데이터는 맨 뒤로 이동

반례 예시

• 입력: [1, 2, 3, 2, 1], 캐시 크기: 3
• 잘못된 방법 결과: 21
• 올바른 방법 결과: 17

class Solution {
    public int solution(int cacheSize, String[] cities) {
        List<String> list = new ArrayList<>();
        
        // 예외
        if(cacheSize == 0){
            return cities.length * 5;
        }
        
        int count = 0;
        for(int i = 0; i < cities.length; i++){
            String city = cities[i].toLowerCase();
            
            // 캐시O: 1점 + 캐시 데이터 제거
            // 캐시X: 5점
            if(list.contains(city)){
                count += 1; 
                list.remove(city);
            } else {
                count += 5;
            } 
            
            // 캐시가 가득찬 경우 맨앞 데이터 제거
            if(list.size() == cacheSize){
                list.remove(0);
            }
            list.add(city);
        }
        return count;
    }
}

---

[ 이모티콘 할인 행사 ] 😎

💡 접근 방법

• [ 그리디 1 ]

  • 플러스 구매 비용이 낮을수록 플러스 가입 확률 ↑
  • 플러스 구매 비용이 같다면 할인율이 낮을수록 이모티콘 더 많이 구매해 플러스 가입으로 이어질 것이라 가정
  • ❌ 예시 2번에서 정렬 이후 다음 단계 불명확

• [ 그리디 2 ]

  • 모든 이모티콘에 40% 할인 적용 후 총합 계산
  • ❌ 구체적인 할인 비율 조합 도출 불가

• [ DFS (완전 탐색) ]

  • 각 이모티콘 할인율: [ 10, 20, 30, 40 ] %
  • 경우의 수: 4^7 = 16,384
  • 각 조합별 모든 사용자(100명)의 구매 정보 계산 → 16,384 × 100 × 7 ≈ 1,100만
  • ⏱️ 전체 연산량: 충분히 계산 가능

public class EmoticonSales2 {
    private static final int[] DISCOUNT_PERCENT = {10, 20, 30, 40};

    private static int[] remember;
    private static int[] emoticons;
    private static int[][] users;

    private static List<Result> results;

    public int[] solution2(int[][] users, int[] emoticons) {
        this.emoticons = emoticons;
        this.users = users;
        this.remember = new int[emoticons.length];
        this.results = new ArrayList<>();

        dfs(0, emoticons.length);

        results.sort(Comparator.naturalOrder());
        Result result = results.get(0);
        return new int[]{result.purchaseCount, result.totalPrice};
    }

    private static void dfs(int depth, int targetDepth) {
        if (depth == targetDepth) {
            // 이모티콘 구매
            results.add(getPurchaseResult());
            return;
        }

        for (int i = 0; i < DISCOUNT_PERCENT.length; i++) {
            remember[depth] = DISCOUNT_PERCENT[i];
            dfs(depth + 1, targetDepth);
        }
    }

    private static Result getPurchaseResult() {
        int purchaseCount = 0;
        int resultPrice = 0;

        // 사람들 순회
        for (int row = 0; row < users.length; row++) {
            int totalPrice = 0;
            int percent = users[row][0];
            int plusPrice = users[row][1];

            // 이모티콘 구매 결정
            for (int index = 0; index < emoticons.length; index++) {
                int discountPercent = remember[index];
                int basicPrice = emoticons[index];

                // 구매 하는 이모티콘 할인 비율이라면
                if (discountPercent >= percent) {
                    int discountPrice = (int) (basicPrice * (100 - discountPercent) * 0.01);
                    totalPrice += discountPrice;
                }

                // 플러스 구매 가능하면 이모티콘 구매 중단
                if (totalPrice >= plusPrice) {
                    purchaseCount++;
                    totalPrice = 0;
                    break;
                }
            }
            // 구매 비용 누적
            resultPrice += totalPrice;
        }
        return new Result(purchaseCount, resultPrice);
    }

    static class Result implements Comparable<Result> {
        private int purchaseCount;
        private int totalPrice;

        public Result(int purchaseCount, int totalPrice) {
            this.purchaseCount = purchaseCount;
            this.totalPrice = totalPrice;
        }

        public int compareTo(Result another) {
            int result = another.purchaseCount - this.purchaseCount;
            if (result != 0) return result;
            return another.totalPrice - this.totalPrice;
        }
    }
}

[sduddla]

1️⃣ [1차] 캐시

• 소문자로 처리
• 캐시 히트일 경우 -> 기존 위치를 제거해서 맨 뒤로 추가(최신)
• 캐시 미스일 경우 -> 새 도시를 맨 뒤로 추가하고 cache.length > cacheSize일 때 맨 앞(가장 오래된) 삭제

function solution(cacheSize, cities) {
    let cache = [];
    let time = 0;
    
    for(let city of cities) {
        city = city.toLowerCase(); // 대소문자 구분 x - 소문자로 처리
        
        if(cache.includes(city)) {
            // 캐시 히트
            time += 1;
            cache = cache.filter(c => c !== city); // 기존 위치 제거
            cache.push(city); // 맨 뒤로 추가
        } else {
            // 캐시 미스
            time += 5;
            cache.push(city);
            if(cache.length > cacheSize) { // 오래된 거 제거
                cache.shift();
            }
        }
    }
    return time;
}

[dbrkdgus00]

캐시

해결 방법

• 캐시를 저장할 리스트를 만든다.
  -> 가장 최근에 사용한 도시는 리스트의 맨 뒤에 오도록 관리한다.

• 도시 이름을 하나씩 순서대로 보면서 처리한다.
  대소문자를 구분하지 않기 때문에, 먼저 소문자로 바꾼다.

• 리스트 안에 해당 도시가 이미 있으면 (cache hit)
  기존 위치에서 삭제한 뒤,
  리스트 맨 뒤에 다시 추가한다 (가장 최근 사용 표시).
  실행 시간은 +1

• 리스트에 해당 도시가 없으면 (cache miss)
  실행 시간은 +5
  캐시가 가득 찼다면 맨 앞의 도시(가장 오래된) 를 삭제한다.
  그 다음, 새 도시를 리스트 맨 뒤에 추가한다.

• 도시들을 모두 처리한 뒤, 누적된 총 실행 시간을 반환한다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {

        // 총 실행 시간
        int time = 0;

        // 캐시를 저장할 리스트
        List<String> cache = new ArrayList<>();

        // 도시 하나씩 처리
        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase();  // 대소문자 구분 X

            // 캐시에 있는 경우 -> hit
            if (cache.contains(city)) {
                cache.remove(city);         // 위치 제거 
                cache.add(city);            // 가장 최근 사용 -> 맨 뒤로
                time += 1;                  // hit는 시간 +1
            }
            // 캐시에 없는 경우 -> miss
            else {
                time += 5;                  // miss는 시간 +5

                // 캐시가 가득 찼다면, 가장 오래된 거 제거 (맨 앞)
                if (cacheSize > 0 && cache.size() == cacheSize) {
                    cache.remove(0);       // 제일 앞에 있는 게 가장 오래됨
                }

                // 캐시 크기가 0이 아닐 경우만 추가
                if (cacheSize > 0) {
                    cache.add(city);       // 새 도시 추가 
                }
            }
        }

        return time;
    }
}

이모티콘 할인 행사

해결방법

• 가능한 모든 할인율 조합을 만든다.

• 각 할인 조합마다 사용자 반응을 시뮬레이션

• 시뮬레이션 결과를 바탕으로 최적의 결과를 갱신

• 가장 좋은 결과([최대 가입자 수, 최대 매출액])를 배열로 반환