문제
- 팀과제
1-1. 주문 상품 중 처리 대기 중인 상품을 주문 처리 할 때
-> 1, 2, 3 번 대기 번호가 있었는데
-> 2번을 주문 처리하고 1, 3번이 남은 상황에서
-> 3번을 누르면 눌리지 않고 2번을 눌러야 대기 번호 3번의 상품이 출력됨
시도
- 팀 과제
1-1. 대기 상품 출력이 문제인가?
-> 출력을 하기 위해서 입력된 input과 해당 상품의 orderNumber가 input과 동일한지 묻는 과정에서 input--가 문제일 거라는 생각이 들었다.
-> input--는 해줄 필요가 없긴 했으나 문제는 아니였음
1-2. 대기 상품을 넘겨주는 매개변수가 문제인가?
-> 출력하는 메서드에 매개변수로 해당하는 상품과 input을 넘겨준
-> input 자체는 넘겨줄 필요가 없었으나 해당 문제는 아니였음
1-3. 해당하는 상품을 찾는 것이 문제인가?
-> orderNumber를 출력해보니 해당하는 상품은 올바르게 찾고 있었음
- 백준 1655
2-1. 예제는 맞았는데 제출하니 시간 초과
-> Collections.sort의 시간복잡도가 NlogN이라고 하는데 for문까지 사용하게 되면 문제의 제한 시간을 넘기는 거 같다.
2-2. for문을 없애거나 정렬 방법을 다르게 하거나, 혹은 아예 다른 알고리즘을 사용해야할 듯
-> 보통 이런 경우는 아예 다른 알고리즘이 존재할 가능성이 높았다....
해결
- 팀 과제
1-1. if 문 : if (input >= 1 && input <= orders.size())
-> 여기에서 input <= orders.size() 이 조건이 문제였다.
-> input은 입력 번호이기 때문에 1, 2, 3의 상품에서 2가 사라져도 3을 누를 수 있지만
-> orders.size()는 하나가 사라지면 크기가 2가 되기 때문에 3번을 입력 받을 수 없었다.
-> 따라서 그 조건을 size()가 아니라 input <= orders.get(orders.size() - 1).getOrderNum() 으로 하여서 해당하는 마지막 주문 번호보다 입력 번호가 작게 수정
- 백준 1655
2-1. 결국 해결하지 못해서 구글링으로 검색하였다.
-> PriorityQueue를 이용해서 maxheap과 minheap을 만든다.
-> 두 개의 사이즈가 같으면 maxHep에, 다르면 minHeap에 숫자를 집어넣는다.
-> 만약 두 heap이 모두 null이 아니고, minHeap의 맨 앞 값이 maxHeap의 맨 앞값보다 작으면 가장 먼저 보관한 값을 서로 바꾼다.
=> 최대 큐의 루트 값은 항상 중앙 값을 나타낸다.
알게 된 점
- 팀 과제
1-1. 팀으로 진행되는 과제이다보니 남이 짠 코드를 수정하는 것이 어렵고, 내가 짰어도 뭔가 코드가 길고 복잡해져서 문제되는 곳을 찾기가 힘들다.
-> 한번 짤 때 제대로 짜는 습관을 들이는 것이 중요
-> sout으로 출력해서 알아보는 것보다 디버깅으로 알아보는 방식이 나중에는 더 좋을 듯
- 백준 1655
2-1. 아직 Heap, PriorityQueue와 관련된 부분은 아는 것이 적어서 더 공부해서 정리해놓아야겠다.
-> 거의 모른다고 할 수 있기 때문에 TIL 말고 별도로 페이지를 만들어서 정리를 해야 할 듯
오늘 푼 문제
백준 1655 (가운데를 말해요) - Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// (o1, o2) -> o2 - o1 => 역순으로 저장한다는 뜻이다.
// Comparator.reverseOrder()와 같음
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
int test_case = Integer.parseInt(br.readLine());
for (int i = 0; i < test_case; i++) {
int num = Integer.parseInt(br.readLine());
// 서로의 사이즈가 같으면 maxHeap에 add, 다르면 minHeap에 add
if (minHeap.size() == maxHeap.size()) maxHeap.add(num);
else minHeap.add(num);
// 서로 switch
if(!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.peek() < maxHeap.peek()) {
int temp = minHeap.poll();
minHeap.add(maxHeap.poll());
maxHeap.add(temp);
}
bw.write(maxHeap.peek() + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
