배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 제거하는 것에서 PriorityQueue를 떠올렸습니다.
PriorityQueue는 add를 하면 오름차순으로 정렬이 되는 Queue입니다. PriorityQueue에 넣어서 값을 비교해서 절댓값이 작은 값을 출력하고 절댓값이 같을 때는 수의 작은 값을 출력하는 문제다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11286 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int a1 = Math.abs(o1);
int a2 = Math.abs(o2);
if(a1 == a2) {
return Integer.compare(o1, o2);
}
else {
return Integer.compare(a1, a2);
}
}
});
for(int i = 0 ; i < n ; i++) {
int num = Integer.parseInt(br.readLine());
if(num == 0) {
if(que.size() == 0) {
System.out.println(0);
}
else {
System.out.println(que.poll());
}
}
else {
que.add(num);
}
}
}
}
문제점
PriorityQueue에 add를 하면 PriorityQueue의 성질 때문에 add 한 순으로오름차순으로 정렬이 되는데 거기서 절댓값을 어떻게 비교 어떻게 해야될지를 떠올리지 못했다. compare를 사용해서 절댓값 문제를 해결할 수 있었다. 정렬 문제에서 compare를 이용하는 문제가 많으므로 compare를 공부를 하자.
오늘의 회고
오늘은 그동안 푼 문제 복습과 1문제 밖에 풀지 못했습니다. 알고리즘을 처음 공부하는데 이해하고 문제를 해결하는 방식을 떠올리는 것이 많이 어려운것 같습니다. 포기 하지 않고 하반기까지 실력을 향상 시키는 것을 목표로 꾸준히 달려보겠습니다.
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
System.out.println(list);
}
}
잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
int [] aArr = new int[aSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
aArr[i] = Integer.parseInt(st.nextToken());
}
int [] bArr = new int [bSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
bArr[i] = Integer.parseInt(st.nextToken());
}
int lt = 0;
int rt = 0;
ArrayList<Integer> list = new ArrayList<>();
while(rt < aSize && lt < bSize) {
if(aArr[rt] > bArr[lt]) {
list.add(bArr[lt]);
lt++;
}
else if(aArr[rt] < bArr[lt]) {
list.add(aArr[rt]);
rt++;
}
else {
lt++;
rt++;
}
}
while(rt < aSize) {
list.add(aArr[rt]);
rt++;
}
while(lt < bSize) {
list.add(bArr[lt]);
lt++;
}
System.out.println(list);
}
}
내가 생각한 풀이 해설
배열을 리스트에 담아서 출력하는 방법을 생각했다.
하지만 시간 초과가 나왔다. 다른 방식으로 투포인터 알고리즘으로 풀었는데도 시간 초과가 나왔다.(?)
계속 바꿔도 시간초과가 나왔는데 그 이유는 마지막에 정답을 출력할 때System.out.print를 사용하면 시간 초과가 나는 것이었다.
이것 때문에 시간을 많이 썼다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < list.size(); i++) {
bw.write(list.get(i) + " ");
}
br.close();
bw.close();
}
}
백준 21921번 블로그
문제점
for문에서 max를 구할 때 크기만큼 달라지는 합해주는 값이 달라지는 것과 count에서 어려움을 느꼈습니다.
for문 안에서 while과 if로 처리해주는 것에 대한 이해가 필요할 것 같습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek21921 {
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 m = Integer.parseInt(st.nextToken());
int [] arr = new int [n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int end = 0;
int sum = 0;
int max = 0;
int count = 1;
for(int i = 0;i < n; i++){
while((end - i < m) && end < n){
sum += arr[end];
end++;
}
if(max == sum){
count++;
}
else if(max < sum){
max = sum;
count = 1;
}
sum -= arr[i];
}
if(max == 0){
System.out.println("SAD");
return;
}
System.out.println(max);
System.out.println(count);
}
}
백준 3273번 두 수의 합
내가 생각한 풀이
어제 풀었던 투포인터 알고리즘을 사용해서 풀면 쉽게 풀리는 문제였다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek3273 {
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());
}
int m = Integer.parseInt(br.readLine());
int i = 0;
int j = n - 1;
int cnt = 0;
Arrays.sort(arr);
while(i < j) {
if(arr[i] + arr[j] == m) {
cnt++;
i++;
j--;
}
else if(arr[i] + arr[j] < m) {
i++;
}
else {
j--;
}
}
System.out.println(cnt);
}
}
백준 14706번 구간 합 최대
문제점
위에 문제는 아직 해결을 하지 못했다. 고민을 많이 해봐야 될 것 같다. 또한 코드를 참고하려고 해도 아직까지 블로그에 올리신 분이 없습니다.
백준 2167번 2차원 배열의 합
내가 생각한 풀이
이와 비슷한 문제를 푼 적이 있어서 오래 걸리지는 않았다. 처음에 이 문제를 접했을 때 구간에서 다음 구간까지 더해주는 것에서 방법을 떠올리기 힘들었다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2167 {
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 m = Integer.parseInt(st.nextToken());
int [][] arr = new int [n + 1][m + 1];
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int k = Integer.parseInt(br.readLine());
int sum;
for(int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
sum = 0;
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for(int j = x1; j <= x2; j++) {
for(int t = y1; t <= y2; t++) {
sum += arr[j][t];
}
}
System.out.println(sum);
}
}
}
오늘의 회고
오늘은 시간 초과 문제로 시간을 많이 소비했습니다. 시간 초과가 났을 때 알고리즘 문제가 아니라 출력해주는 부분에도 시간초과가 날 수 있다는 것을 배웠습니다. 또한 아직도 투포인터에서 이해하지 못한 부분이 있습니다. 자료를 계속 찾아서 공부하고 이해하려고 노력해야 될 것 같습니다. 또한 오늘 해결하지 못한 문제는 내일 이어서 고민해보고 내일은 책에 연습문제 4문제를 풀겠습니다.
