java 알고리즘 스터디 6주차 - 그리디

1715 카드 정렬하기

📌문제 링크

https://www.acmicpc.net/problem/1715

💡 문제 풀이

카드 개수가 적은 것부터 합치면 비교 횟수를 최소로 할 수 있다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
        
        // 개수가 적은 것끼리 합치기 위해 우선순위 큐 사용
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		
		for (int i = 0; i < N; i++) {
			queue.offer(Integer.parseInt(br.readLine()));
		}

		int sum = 0;
		int tmp = 0;
		while (queue.size() > 1) {
        	 // 카드 합치기
			 tmp = queue.poll() + queue.poll();
             // 합친 횟수 누적
			 sum += tmp;
             // 합친 카드 묶음 다시 큐에 넣기
			 queue.offer(tmp);
			
		}
		
		
		System.out.println(sum);
	}
}

2141 우체국

📌문제 링크

https://www.acmicpc.net/problem/2141

💡 문제 풀이

마을을 위치 순으로 정렬한 다음 인구 수가 절반을 넘어가는 곳이 각 사람들까지의 거리의 합이 최소가 되는 위치이다.
여기서 중요한 것은 마을의 위치가 같을 수도 있다는 것!! 이거때문에 자꾸 틀렸다..
마을의 위치가 같을 경우 인구 수가 적은 순서대로 정렬해줘야 한다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		StringTokenizer stk;
		int x, a;
		long sum = 0;
		
        // 마을의 위치, 인구 수 순서로 저장
		int[][] village = new int[N][2];

		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			x = Integer.parseInt(stk.nextToken());
			a = Integer.parseInt(stk.nextToken());

			village[i][0] = x;
			village[i][1] = a;
            // 총 인구 수 계산
			sum += a;
		}
		
        // 마을의 위치 순서대로, 위치가 같다면 인구 수가 적은 순서대로 정렬
		Arrays.sort(village, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return Integer.compare(o1[1], o2[1]);
				} else {
					return Integer.compare(o1[0], o2[0]);
				}
			}
		});

		long people = 0;
        // 총 인구 수가 홀수일 때 절반이 넘어가는 경우를 계산하기 위해 +1하고 절반으로 나눔
		long half = (sum+1)/2;
		
        // 인구 수 누적합 계산
		for (int i = 0; i < N; i++) {
			people += village[i][1];
			
            // 인구 수가 절반이 넘어가는 곳이 우체국을 세울 위치
			if (people >= half) {
				System.out.println(village[i][0]);
				break;
			}
		}

	}

}

19598

📌문제 링크

https://www.acmicpc.net/problem/19598

💡 문제 풀이

회의 시작 시간과 종료 시간을 각각 우선순위 큐에 넣어놓고, 시작 시간을 pop하면 회의실 개수를 늘리고 종료 시간을 pop하면 회의실 개수를 줄인다.
이 과정을 반복하면서 회의실 개수가 최대일 때를 출력한다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	private static class Meeting implements Comparable<Meeting> {
		int time;
		boolean isStart;
		public Meeting(int time, boolean isStart) {
			super();
			this.time = time; // 회의 시간
			this.isStart = isStart; // 시작시간이면 true, 종료시간이면 false
		}
        
        // 시간 순서대로 비교
		@Override
		public int compareTo(Meeting o) {
			return Integer.compare(time, o.time);
		}
		
		
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer stk;
        
        // 시간 순서대로 저장하기 위해 우선순위 큐 사용
		PriorityQueue<Meeting> queue = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			queue.offer(new Meeting(Integer.parseInt(stk.nextToken()), true));
			queue.offer(new Meeting(Integer.parseInt(stk.nextToken()), false));
		}
		
		int room = 0; // 현재 사용중인 회의실 개수
		int answer = 0; // 최대 회의실 개수
        
		Meeting cur;
		while(!queue.isEmpty()) {
			cur = queue.poll();
			
            // 시작 시간이면 회의실 개수 늘리기
			if (cur.isStart) {
				room++;
                // 최댓값 갱신
				answer = Math.max(answer, room);
                
            // 종료 시간이면 (회의가 끝나면) 회의실 개수 줄이기
			} else {
				room--;
			}
		}
		
		System.out.println(answer);
		
	}
}