이코테 0717 - 그리디 기출 문제

HyeJi9908·2022년 7월 17일
0

[JAVA] ThisIsCodingTest

목록 보기
8/12

📚 모험가 길드

import java.util.*;

public class Java0717_2 {
	
	public static void main(String[] args) {
		
		ArrayList<Integer> arr = new ArrayList<>();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			arr.add(sc.nextInt()); 
		}
		
		Collections.sort(arr);
		int answer =0;
		
		int sum=0;
		for(int i:arr) {
			sum++;
			if(sum>=i) {
				answer++;
				sum=0;
			}
		}
		System.out.print(answer);
		
	}
}

📚 곱하기 혹은 더하기

import java.util.Scanner;

public class Java0717_3 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		char[] charArr= sc.nextLine().toCharArray();
		
		int sum=0;
		for(int i=0;i<charArr.length;i++) {
			
			int a = charArr[i] -'0';

			if(a>1&&sum>1) sum*=a;
			else sum+=a;
		}
		System.out.print(sum);
		
	}
}

📚 문자열 뒤집기

import java.util.Scanner;

public class Java0717_4 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String str = sc.next();
	
		int cnt0=0; // 모두 0으로 바꿀때
		int cnt1=0; // 모두 1로 바꿀 때
		
		if(str.charAt(0)=='0') cnt1++;
		else cnt0++;
		
		for(int i=0;i<str.length()-1;i++) {
			if(str.charAt(i)!=str.charAt(i+1)) {
				if(str.charAt(i+1) == '0') cnt1++;
				else cnt1++;
			}
		}
		
		System.out.print(Math.min(cnt0, cnt1));
	}
}

📚 만들 수 없는 금액

// 1씩 증가시켜 그 값을 특정 동전의 조합들로 만들수 있는지 도출하는 로직은 어렵다
// 예를 들어 1 1 2 3 9 으로 8원을 만들려 하면 
// 1,1,2,3 원을 모두 합쳐 만들 수 있는 금액이 최대 7원이기에 불가능
// 따라서 만들수 없는 금액 최소값은 8원

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

public class Java0717_5 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = sc.nextInt(); 
		}
		
		Arrays.sort(arr);  
		
		int target=1;
		for(int i=0;i<n;i++) {
			
			if(target < arr[i]) break;
			target +=arr[i];
			
		}
		
		System.out.print(target);
		
	}
}

📚 볼링공 고르기

import java.util.Scanner;

public class Java0717_6 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		int m= sc.nextInt();
		
		int[] arr = new int[11]; // 1~10 무게별 공 갯수 
		for(int i=1;i<=10;i++) {
			int x = sc.nextInt();
			arr[x]++;
		}
		
		int answer =0;
		for(int i=1;i<=m;i++) {
			
			n -= arr[i]; // 무게 i의 공 갯수 빼기
			answer+= n*arr[i];
		}
		
		System.out.print(answer);
		
	}
}

📚 무지의 먹방 라이브 - 그리디&우선순위 큐

문제풀이 영상 17:00부터

k = 7, food_times = [2,4,3]이면
1. [2,3,4] 로 오름차순 정렬해놓고
가장 금방먹을 수 있는 음식 부터 다먹는다는 로직
2. 2의 먹는시간이 소요되는 음식을 다먹기 위해 세 번(음식갯수)를 거치는 걸 두 바퀴(해당음식 먹는시간) 반복해야함 -> 2*3 = 6의 시간 소요
3. k - 6 =1 남음
4. 남은 음식 [3,4]. 이전의 음식을 먹느라 [1,2] 됨.

이제 1의 먹는시간 음식을 마저 처리하기 위해 두 번 거치는 걸 한 바퀴 반복 -> 1*2 = 2의 시간 소요
근데 k=1이니까 이 동작은 못함. 4번 과정 까지만 함.
[1,2]을 1번 과정 하기전 순서로 되돌리면 [2,1][2,1]에서 (k - total) % length))번째 인덱스 ,즉 (7-6)%3 = 1
인덱스는 0부터니까 food_times =[2,4,3]의 4 먹을 차례

// 무지의 먹방라이브
// foodtimes를 우선순위 큐에 넣기. 그냥 반복문 돌리기엔 범위가 메우 크다.

package ThisIsCodingTest;

import java.util.*;

class Food implements Comparable<Food>{
	
	private int time;
	private int idx;
	
	public Food(int time, int idx) {
		this.time = time;
		this.idx = idx;
	}
	
	public int getIdx() {
		return this.idx;
	}
	
	public int getTime() {
		return this.time;
	}

	@Override // 짧은 시간 소요되는 음식 우선으로!(오름차순)
	public int compareTo(Food o) {
		 
		return this.time - o.time;
	}
	
	
}

public class Java0717_7 {
    public int solution(int[] food_times, long k) {

    	// 시간이 작은 음식부터 뺄 수 있도록 우선순위 큐 
        PriorityQueue<Food> q = new PriorityQueue<>();
        
        long total = 0;	 // 전체음식을 먹는 시간        
        for(int i=0;i<food_times.length;i++) {
        	q.add(new Food(food_times[i],i+1));
        	
        	if( total <=k ) total+= food_times[i];
        }
        if(total <= k) return -1;
        // 전체음식을 먹는 시간보다 k가 크거나 같다면 -1   
        
        total =0;  				// 먹기 위해 사용한 시간
        long previous =0; 		// 직전에 다 먹은 음식 시간
        long length = food_times.length;	// 남은 음식 갯수
        
        // ((pq.peek().getTime() - previous) * length)
        // = ( 현재 음식 시간 - 이전 음식 시간 )*현재 음식 갯수 
        // = 이전음식을 다 먹고 남은 현재음식을 마저 다 먹는 데 소요되는 시간
        // 위 시간 + 이전음식을 다 먹느라 소요한 시간(total) 이 k보다 작을 때만 while문
        while(total + ((q.peek().getTime() - previous)* length) <= k){
        	
        	int nowTime = q.poll().getTime();
        	total += (nowTime - previous)*length;
        	length--; // 다 먹은 음식 제외
        	previous = nowTime;
        }
        
        // 이제 남은 음식중에서 몇벙째 음식이 당첨되는지 
        ArrayList<Food> answer = new ArrayList<>();
        while(!q.isEmpty()) answer.add(q.poll());
        
        Collections.sort(answer, new Comparator<Food>() { 
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.getIdx(), b.getIdx());
                // 남은 음식 인덱스기준 오름차순 정렬
                // (문제에서 무지는 음식번호 순서대로 먹는다 했으니까)
            }
        });
        
        return answer.get((int) ((k - total) % length)).getIdx();
    }
}

0개의 댓글