고민의 흔적

32번 동전 0

내가 떠올린 풀이 해설

동전 값이 큰 동전부터 탐색을 하면서 k와 작거나 같은 동전이 나올 때까지 탐색하고 count 값은 k / (동전 값)으로 추가해주고 k % 동전 값으로 k의 값을 바꿔준다. 끝으로 count를 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek11047 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int []arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int div = 0;
		int cnt = 0;
		int max = 0;
		for(int i = n - 1; i >= 0; i--) {
			if(k >= arr[i]) {
				div = arr[i];
				cnt += k / div;
				k = k % div;
			}
		
		}
		System.out.println(cnt);
	}
}

33번 카드 정렬하기

내가 떠올린 풀이 해설

우선순위 큐를 활용해서 풀어야하는 문제이다. 2개의 값을 합해서 비교해야 한다. 문제의 조건대로 연산을 하면 (10+20) + (30 + 40)이다. 앞의 2개를 더한 값을 바로 사용하므로 더한 값을 큐에 계속 넣어줘야 한다. 그냥 큐를 사용하면 30은 맨 뒤로 들어가 곧바로 연산에 수행될 수 없다. 최소한의 비교를 하기 위해서는 낮은 값부터 먼저 더해야 하므로 오름차순으로 정렬된 상태에서 값을 더하기 위해 우선순위 큐를 사용해야 한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1715 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i = 0; i < n; i++) {
			int data = Integer.parseInt(br.readLine());
			pq.add(data);
		}
		int data1 = 0;
		int data2 = 0;
		int sum = 0;
		
		while(pq.size() != 1) {
			data1 = pq.remove();
			data2 = pq.remove();
			sum += data1 + data2;
			pq.add(data1 + data2);
		}
		System.out.println(sum);
	}
}

34번 수 묶기

내가 떠올린 풀이 해설

가능한 큰 수들 끼리 묶어야 결괏값이 커진다. 또한 음수끼리 곱하면 양수로 되는 성질을 고려해야 된다. 양수 우선순위 큐와 음수 우선순위 큐와 1의 개수 0의 개수를 카운트하는 변수를 만든다. 데이터를 4개 그룹에 분리해 저장 4개 그룹은 1보다 큰 양수, 1의 개수, 0의 개수, 음수이다. while문을 양수 우선순위 큐 크기가 2보다 작을 때까지 반복하는데 수 2개를 큐에서 뽑고 2 개수를 곱한 값을 결괏값에 더한다.

양수 우선순위 큐에 데이터가 남아있으면 이 데이터를 결과값에 더한다. 음수도 위의 양수와 같이 반복한다 만약 음수 우선순위 큐에 데이터가 남아 있고, 데이터 0이 1개도 없으면 이 데이터를 결과 값에 더한다. 마지막으로 숫자 1의 개수를 결괏값에 더함

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1744 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> minusPq = new PriorityQueue<>();
		
		int one = 0;
		int zero = 0;
		
		for(int i = 0; i < n; i++) {
			int data = Integer.parseInt(br.readLine());
			if(data > 1) {
				plusPq.add(data);
			}
			else if(data == 1) {
				one++;
			} 
			else if(data == 0) {
				zero++;
			}
			else {
				minusPq.add(data);
			}
		}
		int sum = 0;
		while(plusPq.size() > 1) {
			int first = plusPq.remove();
			int second = plusPq.remove();
			sum = sum + first * second;
		}
		if(!plusPq.isEmpty()) {
			sum = sum + plusPq.remove();				
		}
		while(minusPq.size() > 1) {
			int first = minusPq.remove();
			int second = minusPq.remove();
			sum = sum + first * second;
		}
		if(!minusPq.isEmpty()) {
			if(zero == 0) {
				sum = sum + minusPq.remove();				
			}
		}
		sum = sum + one;
		System.out.println(sum);
	}
}

35번 회의실 배정

내가 떠올린 풀이

예전에 풀었던 문제와 비슷한 문제여서 어렵지 않게 풀었다. 끝나는 시간으로 정렬을 하고 시작시간으로 정렬을 한다. 끝나는 시간을 기준으로 겹치지 않는 회의실을 선택한다. 

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1931 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Meet> list = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());	
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list.add(new Meet(x, y));
		}
		int cnt = 0;
		Collections.sort(list);
		int et = 0;
		for(Meet b : list) {
			if(b.x > et) {
				cnt++;
				et = b.y;
			}
		}
		System.out.println(cnt);
	}
}
class Meet implements Comparable<Meet> {
	int x;
	int y;
	Meet(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Meet o) {
		if(this.x == o.x) {
			return this.y - o.y;
		}
		return this.x - o.x;
	}
}

오늘의 회고

오늘은 그리디 알고리즘에 배워보는 시간이였습니다. 오늘 문제들도 쉽지 않은 문제들로 구성이 돼있어 힘들었습니다. 알고리즘을 풀면서 고민해도 답을 못 풀 경우에 답을 보고 다시 풀어야 되나 아니면 계속 고민해야 되나 라는 고민이 생기는데 계속 고민해 보는 것이 가장 좋은 방법이라고 생각하는데 저는 시간의 제약 때문에 답을 보고 다시 풀고 복습하고 공부하는 식으로 내 것으로 만들고 있습니다. 아직 풀 수 있는 문제가 많진 않지만 계속해서 공부하겠습니다.