동전 값이 큰 동전부터 탐색을 하면서 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;
}
}
오늘의 회고
오늘은 그리디 알고리즘에 배워보는 시간이였습니다. 오늘 문제들도 쉽지 않은 문제들로 구성이 돼있어 힘들었습니다. 알고리즘을 풀면서 고민해도 답을 못 풀 경우에 답을 보고 다시 풀어야 되나 아니면 계속 고민해야 되나 라는 고민이 생기는데 계속 고민해 보는 것이 가장 좋은 방법이라고 생각하는데 저는 시간의 제약 때문에 답을 보고 다시 풀고 복습하고 공부하는 식으로 내 것으로 만들고 있습니다. 아직 풀 수 있는 문제가 많진 않지만 계속해서 공부하겠습니다.
import java.io.*;
import java.util.*;
public class Baek1874 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int [n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int [] arr2 = arr.clone();
Arrays.sort(arr2);
Stack<Integer> stack = new Stack<>();
int i = 0;
int j = 0;
//System.out.println(stack);
//stack = 1
while(j != n) {
if(stack.isEmpty()) {
stack.push(arr2[i]);
System.out.println("+");
}
if(arr[j] != stack.peek()) { //i 가 [0] 4 != 1 true
stack.push(arr2[i + 1]); // arr2[1] = 2 i = 1
System.out.println("+");
i++;
}
else if(arr[j] == stack.peek()) {
stack.pop();
System.out.println("-");
j++;
}
else {
System.out.println("NO");
}
}
}
}
내가 떠올린 풀이 해설
배열을 하나 더 만들어서 복사해서 정렬한 다음 배열 인덱스 탐색하는 i와 j를 만들어서 문제를 풀려고 했다.
peek으로 스택 최상단에 있는 수와 비교했을 때 복사한 배열의 수와 다르면 push 하고 같으면 pop을 하려고 했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1874 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int num = 1;
boolean result = true;
Stack<Integer> stack = new Stack<>();
StringBuffer bf = new StringBuffer();
for(int i = 0; i < n; i++) {
int su = arr[i];
if(su >= num) {
while(su >= num) {
stack.push(num++);
bf.append("+\\n");
}
stack.pop();
bf.append("-\\n");
}
else {
int k = stack.pop();
if(k < su) {
System.out.println("NO");
result = false;
break;
}
else {
bf.append("-\\n");
}
}
}
if(result) {
System.out.println(bf.toString());
}
}
}
문제점
예제 출력 1번은 내가 짠 코드로 가능했지만 예제 출력 2번은 구현하지 못했다.
인덱스로 배열을 탐색했을 때 인덱스가 다음으로 이동했을 때 비교하기 전 인덱스로 다시 돌아가는 것을 구현하지 못했다.
12번 문제 오큰수 구하기
잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek17298 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> stack = new Stack<>();
//int i = 1;
stack.push(arr[0]);
for(int j = 1; j < n; j++) {
for(int i = 1; i < n; i++) {
if(stack.peek() < arr[i]) {
stack.push(arr[i]);
System.out.print(arr[i] + " ");
while(stack.size() != 1) {
stack.pop();
}
stack.push(arr[i]);
}
else if(stack.peek() > arr[i]) {
}
else {
System.out.print("-1 ");
//i++;
}
}
}
br.close();
}
}
내가 떠올린 풀이 해설
위에 풀었던 문제와 비슷한 방식을 떠올렸다. 이중 for문으로 for문이 돌면서 스택에 peek으로 젤 위에 값과 배열의 다음 값을 비교하는데 배열의 값이 크면 스택에 push 했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek17298 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n]; //수열배열 생성
int [] answer = new int [n]; //정답 배열 생성
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> stack = new Stack<>();
stack.push(0); // 처음에는 항상 스택이 비어 있으므로 최초 값을 push해 초기화
for(int i = 1; i < n; i++) {
//스택이 비어있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우
while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
answer[stack.pop()] = arr[i]; // 정답 배열에 오큰수를 현재 수열로 저장하기
}
stack.push(i); //신규 데이터 push
}
while(!stack.isEmpty()) { //반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지
answer[stack.pop()] = -1; //스택에 쌓인 index에 -1을 넣고
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < n; i++) {
bw.write(answer[i] + " ");
}
bw.close();
br.close();
}
}
문제점
위와 똑같은 문제가 있었다. 인덱스로 탐색을 해서 그 전으로 돌아와서 비교하는 법을 모르겠다.
그 전으로 돌아오지 못해 처음 5와 7을 잘 출력이 되는데 그 뒤로부터는 비교할 수가 없어서 -1, -1이 출력됩니다.
풀이를 보면 저번과 같이 BufferedWriter로 출력하는 것을 볼 수가 있는데 System.out.print로 출력을 할시 시간 초과가 발생합니다
13번 문제 카드 게임
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2164 {
public static void main(String[] args) throws IOException{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Integer> que = new LinkedList<>();
for(int i = 1; i <= n; i++) {
que.offer(i);
}
while(que.size() != 1) {
que.poll();
que.offer(que.poll());
}
System.out.println(que.poll());
}
}
내가 떠올린 풀이 해설
큐에 대한 선입 선출의 개념을 알고 있으면 쉽게 풀 수 있는 문제라고 생각한다. 카드의 개수의 최대가 500,000이므로 시간 복잡도의 제약도 크지 않다.
오늘의 회고
오늘은 자료구조의 알고리즘을 풀어봤는데 조건에 따라 구현하는 방법이 어려웠습니다. 책에 있는 문제들이 기본 문제도 있지만 많이 어려운 문제도 있어 시간이 오래 걸리는 것 같습니다. 알고리즘 공부하면서 느끼는 점은 시간이 지날수록 알고리즘 공부에 대한 방향성이 조금씩은 잡혀가고 있는 것 같습니다. 내일은 오늘 풀었던 문제 복습과 스택, 큐, 덱에 대한 오늘보단 쉬운 5문제를 풀겠습니다.
