문제
로직
연산 개수 입력받기
큐 선언(우선순위 큐를 아예 구현하려고 큐로 선언함ㅜ)
1. 반복문
- 숫자 입력 받기
- 숫자가 0이 아닐 때 -> 큐에 삽입
- 숫자가 0일 때 -> 큐가 비었을 때 -> 0출력
-> 큐가 안 비었을 때 -> 출력할 값을 변수에 저장 후 출력
sign함수
- 결과값 변수 선언 및 초기화
- 결과를 저장할 배열 선언 및 크기 설정
- 음수값 저장할 배열 선언 및 크기 설정
- 양수값 저장할 배열 선언 및 크기 설정
1. 반복문
- 큐 안의 값이 음수일 때 -> minus배열에 값 불러와 저장 -> 배열 오름차순 정렬
- 큐 안의 값이 양수일 때 -> plus배열에 값 불러와 저장 -> 배열 오름차순 정렬
2. 반복문
절댓값 크기를 비교하며 배열 값을 큐에 삽입
-> 이 로직을 세우는 것이 어려워서 마무리 못함
결과값 반환
My Code
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
Queue<Integer> cardQueue = new LinkedList<>();
int x;
for (int i = 0; i<N; i++) {
x = Integer.parseInt(bf.readLine());
if (x != 0){
cardQueue.add((x));
}
else{
if (cardQueue.isEmpty())
System.out.println(0);
else {
int num = sign(cardQueue);
System.out.println(num);
}
}
}
}
private static int sign(Queue<Integer> cQueue) {
int result = 0;
int[] numArray = new int[cQueue.size()];
int[] minus = new int[cQueue.size()];
int[] plus = new int[cQueue.size()];
for (int i = 0; i < cQueue.size(); i++) {
if(cQueue.peek() < 0){
minus[i] = cQueue.poll();
Arrays.sort(minus);
}
else{
plus[i] = cQueue.poll();
Arrays.sort(plus);
}
}
for (int i = 0; i < cQueue.size(); i++) {
if(Math.abs(minus[i]) <= Math.abs(plus[0]))
cQueue.add(minus[i]);
else {
cQueue.add(plus[0]);
while(Math.abs(minus[i]) <= Math.abs(plus[0]))
}
}
return result;
}
}
문제의 핵심 & 알게된 점
우선순위 큐로 선언한 후
절댓값에 따라 오름차순 정렬시키고 절댓값이 같은 경우 음수, 양수 판별 후 정렬시켜야한다.
우선순위 큐의 우선순위 정하는 기준을 위와 같이 구현하는 것이 문제의 핵심이었다.
그런 논리는 알고 있었지만 구현하기 어려웠다...
거의 8시간 동안 이틀에 걸쳐 이 문제만 생각했는데 쉽지 않았다...
return할 때 반환 값에 따라 오름차순, 내림차순 정렬이 가능하다는 것을 알게 되어 구현할 수 있었다.
return o1 - o2;일 때
o1 > o2 => 1
o1 == 02 => 0
o1 < o2 => -1
위와 같은 규칙으로 오름차순 정렬로 정의가 가능하다.
(내림차순은 반대로)
큐를 선언할 때 비교할 값 2개 변수(o1, o2)를 선언해서 비교하며 구현하는 방식도 처음 알게 됐다.
참고 Code
import java.io.*;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
PriorityQueue<Integer> cardQueue = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if(first_abs == second_abs) {
return (o1 > o2)? 1 : -1;
}
return first_abs - second_abs;
});
int x;
for (int i = 0; i<N; i++) {
x = Integer.parseInt(bf.readLine());
if (x != 0){
cardQueue.add((x));
}
else{
if (cardQueue.isEmpty())
System.out.println(0);
else {
System.out.println(cardQueue.poll());
}
}
}
}
}
참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA
'Java' 카테고리의 다른 글
[백준] 1427번 소트인사이드 - 내림차순 정렬 / 선택정렬 (1) | 2023.08.21 |
---|---|
[백준] 2750번 수 정렬하기 - 버블 정렬 구현 / BubbleSort / 오름차순 (0) | 2023.08.19 |
[백준] 2164번 카드2 - 큐(Queue)/선입선출/스택을 이용한 방법/ (0) | 2023.08.18 |
[백준] 1874번 스택 수열 - Stack / push() / pop() / 스택의 원리 (0) | 2023.08.16 |
[백준] 12891번 DNA 비밀번호 - 슬라이딩 윈도우 / switch / 함수 (0) | 2023.08.12 |