[이것이 코딩테스트다] 11. 그리디 알고리즘 - 유형별 기출문제 풀이 (JAVA)

이것이 취업을 위한 코딩테스트다.

 

 

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

(원본 소스코드 : https://github.com/ndb796/python-for-coding-test/)

 

 

 

1. 모험가 길드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        int[] arr = new int[num];
        
        for (int i = 0; i < num; i++) {
        	arr[i]=(sc.nextInt());
        }

        // 배열 정렬
        Arrays.sort(arr);

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

        for (int i = 0; i < num; i++) { 
            count += 1; // 현재 그룹에 해당 모험가를 포함시키기
            if (count >= arr[i]) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
                result += 1; // 총 그룹의 수 증가시키기
                count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
            }
        }

        System.out.println(result);
    }

}

 

2. 곱하기 혹은 더하기

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		String str = sc.nextLine();
		String[] arr = str.split("");
		
		// 곱셈 or 덧셈
		// 0 or 1가 들어간 연산에서는 더하기가 곱셈보다 좋음
		// 그러므로 두 숫자중 1 이하가 있는 경우 더하기로 연산하고 
		// 두 숫자가 모두 2 이상인 경우 곱셈으로 연산한다.
		int result = Integer.parseInt(arr[0]);
		
		for(int i=1;i<arr.length;i++) {
			int num = Integer.parseInt(arr[i]);
			
			if(num >= 2 && result >= 2) {
				result *= num;
			}else {
				result += num;
			}
		}
		
		System.out.println(result);
	}

}

 

3. 문자열 뒤집기

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc  = new Scanner(System.in);
		
		String str = sc.nextLine();
		
		// 0으로 이루어진 그룹과 1로 이루어진 그룹 중 적은 그룹의 수를 찾으면 해결 가능
		// 그룹? 연속된 숫자의 모임

		int count0 = 0;	// 0의 그룹 카운 
		int count1 = 0;	// 1의 그룹 카운트 
		
		String[] strArr = str.split("");
		
		// 처음 원소만 num에 넣고 해당 숫자 카운트 증가 
		String num = strArr[0];
		if(num.equals("0")) {
			count0++;
		}else{
			count1++;
		}
		
		// 2번째 원소부터 반복 시작
		// 이전 숫자와 현재 숫자가 다르면 해당 숫자 카운트 증가 및 이전 숫자 변경
		for(int i=1;i<strArr.length;i++) {
			if(!num.equals(strArr[i])) {
				if(strArr[i].equals("0")) {
					count0++;
				}else {
					count1++;
				}
				num=strArr[i];
			}
		}
		
		//결과 출력
		if(count0>count1) {
			System.out.println(count1);
		}else {
			System.out.println(count0);
		}
	}

}

 

4. 만들 수 없는 금액

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int[] arr = new int[num];
		
		for(int i=0;i<num;i++) {
			arr[i] = sc.nextInt();
		}
		
		// 배열 정렬
		Arrays.sort(arr);
		
		int target = 1;
		for(int i=0; i<arr.length;i++) {
			if(arr[i]>target) {
				break;
			}
			target += arr[i];
		}
		
		System.out.println(target);
	}

}

 

5. 볼링공 고르기

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int maxW = sc.nextInt();
		
		// 지문에 볼링공 무게는 1~10까지만 존재한다고함.
		// 필자는 볼링공의 최대 무게를 10 넘어서도 생각함.
		int[] weightArr = new int[maxW];
		int[] arr = new int[num];
		
		int result = 0;
		for(int i=0;i<num;i++) {
			arr[i]=sc.nextInt();
		}
		
		// 1짜리 공의 수를 첫번째배열에 넣고
		// 2짜리 공의 수를 두번째배열에 넣는 방식 이용
		// 반복이 끝나면 아래의 배열은 볼링공의 무게별 갯수
		for(int i=0;i<arr.length;i++) {
			weightArr[arr[i]-1]++;
		}
		
		// 볼링공 총 갯수에서 현재 무게 볼링공의 갯수를 빼는 이유
		// 같은 무게끼리는 조합하면 안되기 때문에 무게 볼링공의 갯수에서 같은 무게의 볼링공 수만큼 빼주고 곱한다.
		
		// num변수 즉, 총 볼링공 갯수에다가 계속 빼는 이유
		// num 변수를 다시 원래 갯수로 하고 특정 무게의 볼링공 갯수를 빼면 계산했던 경우가 포함됨.
		// 포함하지 않도록 원래 갯수로 초기화하지 않고 num 변수를 계속 빼는 것
		for(int i=0;i<maxW;i++) {
			num -= weightArr[i];
			result += (weightArr[i]*num);
		}
		
        // 결과 출력
		System.out.print(result);
	}

}

 

6. 무지의 먹방 라이브

import java.util.*;

// 음식 클래스 선언
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) {
        if(this.time < other.time)
            return -1;
        else 
            return 1;
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        // 우선순위 큐 선언
        PriorityQueue<Food> pq = new PriorityQueue<>();
        
        // 모든 음식을 먹는데 필요한 시간
        long summary = 0;
        
        // 모든 음식을 먹는데 필요한 시간 구하기 & 우선순위 큐에 넣기
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
            pq.offer(new Food(food_times[i], i + 1));
        }
        
        // 만약, 모든 음식을 먹는데 필요한 시간보다 k가 같거나 크다면 -1 반환(먹을 수 있는 음식이 없음)
        if (summary <= k) 
            return -1;

        // 지금까지의 음식을 먹은 시간
        summary = 0; 
        
        // 이전 음식을 먹는데 걸리는 시간
        long previous = 0; 
        
        // 현재 남아있는 음식의 갯수
        long length = food_times.length; 

        // (지금까지의 음식을 먹은 시간 + (현재 음식을 먹는데 걸리는 시간 - 이전 음식을 먹는데 걸리는 시간) * 현재 남아있는 음식의 갯수) 가 k보다 작거나 같을 때
        // peek()은 꺼내는 것이 아닌 확인만 함
        while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
            // 큐에서 꺼내고
            int now = pq.poll().getTime();
            
            // 지금까지 음식을 먹는데 필요한 시간에 더해준다.
            summary += (now - previous) * length;
            
            // 하나의 음식을 다 먹었으니 -1 처리
            length -= 1; 
            
            previous = now; 
        }

        // 음식 번호대로 정렬을 하기위해 ArrayList 이용
        ArrayList<Food> result = new ArrayList<>();
        
        // 우선순위 큐에 남아있는 음식들을 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();
    }
}

 

답안을 보지 않고 풀기 때문에 답안 소스코드와 다를 수 있으니 참고용으로만 봐주시면 감사하겠습니다.

 

좋은 조언은 환영합니다.