그리디 - 당장 좋은 것만 선택하는 그리디

거스름돈 문제

문제

N원을 여러 화폐단위로 거슬러주어라.

단, 가장 큰 화폐 단위부터 거슬러줘야할 때

해당 화폐로 거슬러주어야할 동전의 갯수는?

 

입력예시 : n=1260, 화폐단위들{500, 100, 50, 10}

출력예시 : 6

 

해결방법

큰 화폐 단위는 항상 작은 단위의 배수이므로

가장 큰 화폐 단위부터 가장 작은 화폐 단위까지 거슬러주는 작업만 하면된다.

 

거스름돈을 해당 화폐으로 나누면

몫 -> 해당 화폐로 거슬러줄 수 있는 돈,

나머지 -> 더 작은 단위로 거슬러주어야할 나머지 돈

 

    static int n = 1260;
    static int cnt = 0;
    static int[] coinTypes = {500, 100, 50, 10};

    public static void main(String[] args) {
		
        for (int i = 0; i < 4; i++) {
            int coin = coinTypes[i];
            cnt += n / coin;
            n %= coin;
        }

        System.out.println(cnt);
    }

 

---

큰 수의 법칙

 

문제

주어진 배열의 수들을 M번 더해서 가장 큰수를 만들어라

단, 특정 인덱스에 해당하는 수가 연속해서 K 번까지만 더해질수 있음

 

입력예시: m=8, k=3, 주어진배열 2 4 5 4 6 

출력예시: 46

 

해결방법

"가장 큰수를 K 번 더하고, 두번째로 큰 수를 한번 더하는 작업"을 반복하면 된다. 

 

이를 위해

이 반복되는 수를 먼저 찾는다. 

M을 K+1로 나눈 몫만큼 반복하고 나머지만큼 큰수만 더함

// 가장 큰 수가 더해지는 횟수 계산
// m / (k + 1) : 반복 횟수 
// cnt: 더해질 제일 큰 수의 갯수

int cnt = (m / (k + 1)) * k;	// 반복으로 더해질 제일 큰 수의 갯수
cnt += m % (k + 1);		// 반복 후 남아서 더해질 제일 큰 수의 갯수

    static int m = 8;
    static int k = 3;
    static int[] arr = {2, 4, 5, 4, 6};    

    public static void main(String[] args) {

        Arrays.sort(arr); // 입력 받은 수들 정렬하기
        int first = arr[arr.length - 1]; // 가장 큰 수
        int second = arr[arr.length - 2]; // 두 번째로 큰 수

        // 가장 큰 수가 더해지는 횟수 계산
        int cnt = (m / (k + 1)) * k;
        cnt += m % (k + 1);

        int result = 0;
        result += cnt * first; // 가장 큰 수 더하기
        result += (m - cnt) * second; // 두 번째로 큰 수 더하기

        System.out.println(result);
    }

 

 

 

---

숫자 카드 게임

문제

가장 큰 숫자가 쓰인 카드 한장을 뽑아야 함

이때 NxM 행렬로 놓인 카드에서 먼저 행을 자유롭게 선택하면 그 행에 있는 수 중 가장 작은 수가 뽑히게 됨

따라서 처음 행을 고를때 해당 행의 가장 작은수가 다른 행을 고를 때보다 큰수가 되도록 골라야 함

 

해결방법

모든 행의 가장 작은 수를 찾은 후, 그 작은수 중 가장 큰수를 찾으면 된다. 

    static int n = 3;		// 행 갯수
    static int m = 3;		// 열 갯수
    static int[] arr = {3, 1, 2,
               	    4, 1, 4,
               	    2, 2, 2};

//    static int n = 2;		// 행 갯수
//    static int m = 4;		// 열 갯수
//    static int[] arr = {7, 3, 1, 8, 3, 3, 3, 4};

    public static void main(String[] args) {

        int result = 0;
        
        // 한 줄씩 확인하기
        for (int i = 0; i < n; i++) {
            // 현재 줄에서 '가장 작은 수' 찾기
            int min_value = 10001;
            for (int j = 0; j < m; j++) {
                int x = arr[i*m + j];
                min_value = Math.min(min_value, x);
            }
            // '가장 작은 수'들 중에서 가장 큰 수 찾기
            result = Math.max(result, min_value);
        }

        System.out.println(result);
    }

 

 

---

1이 될 때까지

문제

주어진 수 N이 1이 될때까지

"1을 빼거나",

"k로 나누거나"

두 과정을 수행하는 최소 횟수를 구하라

 

입력예시 n= 25 k=5

출력예시 2

 

해결방법

나눌때가 무조건 횟수를 줄인다.

따라서 나누어 떨어지면 나누고, 

아니면 나누어 떨어질때까지 1씩 빼는 과정을 반복한다. 

//target: N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼야되는 수
int target = (n / k) * k;

    static int n = 25;
    static int k = 5;

    public static void main(String[] args) {
        int result = 0;
        
        while (true) {
        
            // N이 K로 나누어 떨어지는 수가 될 때까지만 "1씩 빼기"
            int target = (n / k) * k;
            result += (n - target);
            n = target;
            
            // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
            if (n < k) break;
            
            // "K로 나누기"
            result += 1;
            n /= k;
        }

        // 마지막으로 남은 수에 대하여 1씩 빼기
        result += (n - 1);
        System.out.println(result);
    }

 

---

모험가 길드 (핵심 유형)

문제 

N명의 모험가가 모험을 떠날때 떠날 수 있는 그룹의 최대값을 구하라

이때 공포도가 X인 모험가는 반드시 X 명 이상으로 그룹을 구성할 수 있다

 

모험가 공포도 각각: 2 3 1 2 2

출력예시 : 2

 

해결방법

낮은 공포도 모험가부터 그룹에 포함시키면서

현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면,

그룹 결성(1. 총 그룹수 증가시키기, 2. 현재 그부에 포함된 모험가 수 초기화)

-> 이 작업 반복

    public static ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(2);	// 사실 add는 메인함수 내에서 구현해야함
    arrayList.add(3);
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(2);

 

    public static void main(String[] args) {

        Collections.sort(arrayList);

        int result = 0; // 총 그룹의 수
        int count = 0; // 현재 그룹에 포함된 모험가의 수

        for (int i = 0; i < arrayList.size(); i++) { // 공포도를 낮은 것부터 하나씩 확인하며
        
            count += 1; // 현재 그룹에 해당 모험가를 포함시키기
            
            if (count >= arrayList.get(i)) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
                result += 1; // 총 그룹의 수 증가시키기
                count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
            }
            
        }

        System.out.println(result);
    }

 

---

곱하기 혹은 더하기(Facebook 인터뷰 기출)

문제 

왼쪽부터 하나씩 숫자를 확인하며 곱하기 더하기를 연산자를 넣어 만들 수 있는 수 중 가장 큰 수는

 

입력예시 : 0 2 9 8 4

출력예시 : 576

해결방법

연산해야할 다음 숫자(시작숫자)가

0혹은 1일 경우 더하기,

나머지숫자면 곱하기를한다.

    static String str = "02984";

    public static void main(String[] args) {
        long result = str.charAt(0) - '0';
       
        for (int i = 1; i < str.length(); i++) {
            // 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
            int num = str.charAt(i) - '0';
            if (num <= 1 || result <= 1) {
                result += num;
            }
            else {
                result *= num;
            }
        }

        System.out.println(result);
    }

 

 

---

문자열 뒤집기 (핵심 유형)

문제 

0과1로만 된 숫자를 연속해서 하나 이상의 숫자를 뒤집어

전부 같은수 만들기위해 최소로 뒤집는 횟수는?

 

입력예시 :  0001100

출력 : 1

해결방법

왼쪽부터 쭉 확인하며 무조건 이전과 다른 원소 나왔을 경우 카운트하면 최소값이다. 

 

    public static String str = "0001100";

   public static int count0 = 0; // 전부 0으로 바꾸는 경우
   public static int count1 = 0; // 전부 1로 바꾸는 경우
   
   public static void main(String[] args) {

        // 첫 번째 원소에 대해서 처리
        if (str.charAt(0) == '1') {
            count0 += 1;
        }
        else {
            count1 += 1;
        }

        // 두 번째 원소부터 모든 원소를 확인하며
        for (int i = 0; i < str.length() - 1; i++) {
            if (str.charAt(i) != str.charAt(i + 1)) {
                // 다음 수에서 1로 바뀌는 경우
                if (str.charAt(i + 1) == '1') count0 += 1;
                // 다음 수에서 0으로 바뀌는 경우
                else count1 += 1;
            }
        }

        System.out.println(Math.min(count0, count1));
    }

 

---

만들 수 없는 금액 (K 대회 기출)

문제 

주어진N개의 동전을 이용하여 만들수 없는 금액(양의정수)중 최솟값을 구하라

 

입력예시 : 3 2 1 1 9

출력예시 : 8

해결방법7

1부터 answer-1까지 모든 금액을 만들수 있을때 answer 짜리 동전이 주어지면, 

1부터 answer-1+answer까지 모든 금액을 만들 수 있다. 

 

    static int[] array = {3, 2, 1, 1, 9};

    public static void main(String[] args) {
        int answer = 1;
        Arrays.sort(array);

        for(int i=0; i<array.length; i++){

            if(answer < array[i]) break;    // 만들수 없는 금액을 찾았을때 종료

            answer = answer + array[i];     // 만들 수 있는 가장 작은수들을 차례로 만든다
        }

        System.out.println(answer);
    }

 

---

볼링공 고르기 (S 기관 입학 테스트)

문제 

N개의 볼링공이 주어질때 두 사람이 고를 수 있는 볼링공 번호의 경우의 수를 구하세요

이때 N개의 볼링공에는 최대 무게M인 공의 무게가 적혀있습니다. 

 

볼링공 무게: 1 3 2 3 2

출력예시 : 8

 

볼링공 무게 : 1 5 4 3 2 4 5 2

출력예시 : 25

해결방법

각 무게마다의 볼링공의 갯수 담을 수 있는 배열을 따로 선언해야함

 

 

 

    public static int[] total_arr = {1, 5, 4, 3, 2, 4, 5, 2};
    //    public static int[] total_arr = {1, 3, 2, 3, 2};

    public static int[] arr = new int[11]; // 1부터 10까지의 무게마다의 볼링공의 갯수 담을 수 있는 배열

    public static void main(String[] args) {

        int result = 0;
        
        Arrays.sort(total_arr);
        int len = total_arr.length;
        int m = total_arr[len-1];

        for(int i = 0; i<len; i++){
            int weight = total_arr[i];
            arr[weight]++;
        }
        

        // 1부터 m까지의 각 무게에 대하여 처리
        for (int i = 1; i <= m; i++) {
            len -= arr[i]; 			// 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
            result += arr[i] * len; 	// B가 선택하는 경우의 수와 곱해주기
        }

        System.out.println(result);
    }

 

---

무지의 먹방 라이브 (카카오)

문제 

먹방을 시작한지 K 초 후 중단되었다가.. 다시 시작되었을때 몇번 음식부터 섭취해야 하는가

이때, 음식의 회전판은 번호가 증가하는 순서대로 무지 앞으로 가져다 놓아짐(마지막번호 후 다시 1번 음식으로);

이때 음식이 없으면 다음으로 섭취해야할 가장 가까운 번호의 음식이 가져다 놓아짐

 

입력 food_times: [3, 1, 2], k=5

출력 1

 

해결방법

 

class Food implements Comparable<Food> {

    private int time;
    private int index;

    public Food(int time, int index) {
        this.time = time;
        this.index = index;
    }

    public int getTime() {
        return this.time;
    }

    public int getIndex() {
        return this.index;
    }

    // 시간이 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) return -1;


        // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
            pq.offer(new Food(food_times[i], i + 1));
        }


        summary = 0; // 먹기 위해 사용한 시간
        long previous = 0; // 직전에 다 먹은 음식 시간
        long length = food_times.length; // 남은 음식의 개수


        // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
        while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
            int now = pq.poll().getTime();
            summary += (now - previous) * length;
            length -= 1; // 다 먹은 음식 제외
            previous = now; // 이전 음식 시간 재설정
        }


        // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
        ArrayList<Food> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        
        // 음식의 번호 기준으로 정렬
        Collections.sort(result, new Comparator<Food>() { 
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.getIndex(), b.getIndex());
            }
        });
        
        return result.get((int) ((k - summary) % length)).getIndex();
    }
}