[알고리즘] 이코테 - 그리디(Greedy)

이것이 취업을 위한 코딩 테스트다 [PART02 그리디] 문제 풀이

1. 큰 수의 법칙 (2023.05.30)

• 2019 국가 교육기관 코딩 테스트

주어진 배열을 오름차순으로 정렬한 뒤 가장 큰 값(배열 마지막 값) K 번 더한 뒤에, 두번째로 큰 값을 그 다음 가장 큰 값을 1번 더한 뒤 다시 가장 뒤에 있는 값을 K번 더한다.

🍵 코드

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

public class Main{
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		String[] NMK = sc.nextLine().split(" ");
		ArrayList<Integer> arr = new ArrayList<>();
		

		for(int i=0; i<Integer.parseInt(NMK[0]); i++){
			arr.add(sc.nextInt());
		}
		
		Collections.sort(arr);		

 		int result = 0;
		int tempK = Integer.parseInt(NMK[2]);

		for(int i=0; i<Integer.parseInt(NMK[1]); i++){
			if(tempK > 0)){
				result += arr[0];
				tempK--
			}
			else{
				result += arr[1];
				tempK=Integer.parseInt(NMK[2]);
			} 			
		}
		
		System.out.println(result);

	}
}

2. 숫자 카드 게임 (2023.05.31)

• 2019 국가 교육기관 코딩 테스트

한 행을 하나의 배열로 생성하여 해당 행에서 가장 작은 값을 꺼내둔다. 다음 입력되는 행에서 가장 작은 값과 기존 행들의 가장 작은 값들을 비교하여 더 큰 값을 결과로 저장한다. 마지막 행이 입력될 때까지 반복한 뒤에 모든 입력이 종료되면 결과를 출력한다.

🍵 코드

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

public class MyClass {
    public static void main(String args[]) {
      
        Scanner sc = new Scanner(System.in);
      
        String[] NM = sc.nextLine().split(" ");
      
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
      
        int max = 0;
      
        for(int i=0; i<Integer.parseInt(NM[0]); i++){
            arr.add(new ArrayList<Integer>());
         
            for(int j=0; j<Integer.parseInt(NM[1]); j++){
                arr.get(i).add(sc.nextInt());
            }
            
            Collections.sort(arr.get(i));
        
            if(max <= arr.get(i).get(0)){
                max = arr.get(i).get(0);
            }
            
        }
        
        System.out.println(max);
        
    }
}

3. 1이 될 때까지 (2023.06.02)

• 2018 E 기업 알고리즘 대회

주어진 N이 K로 나누어 떨어지는 값이라면 N을 K로 나누고, N이 K로 나누어 떨어지지 않는 값이라면 1을 뺀다.

🍵 코드

import java.util.Scanner;
	
public class MyClass {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        String[] NK = sc.nextLine().split(" ");
        int N = Integer.parseInt(NK[0]);
        int K = Integer.parseInt(NK[1]);

        int quotient = N;
        int count = 0;
        
        while(quotient != 1){
            if(quotient % K == 0){
                quotient /= K;
            }
            else{
                quotient--;
            }
            count++;
        }
        
        System.out.println(count);
    }
}