Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- GatherTown
- 시뮬레이션
- 다이나믹프로그래밍
- 다익스트라
- 게더타운시작
- 자바PS
- 백준
- 엘라스틱서치
- 우선순위큐
- spring
- 네트워크플로우
- PS
- java
- 알고리즘
- BFS
- 이젠 골드구현도 어렵네..
- 취득후기
- deque
- DFS
- QUICKSTARTGUIDE
- 구현
- YBMCOS
- 완전탐색
- 01BFS
- dp
- COSPROJAVA1급
- 세그먼트트리
- 백준코딩테스트
- COSPRO
- 재귀함수
Archives
- Today
- Total
공부공간
BOJ - 1655 ) 가운데를 말해요 본문
https://www.acmicpc.net/problem/1655
특정한 수열의 숫자가 차례대로 주어질때에, 그 중간의 값을 계속 출력하면 된다.
두 가지 자료구조가 있다고생각하면 편하다, 항상 루트노드에 큰값이 오게 정렬되는 Max Heap과 반대인
Min Heap이 있다고 가정하면 이 둘을 붙였을때 온전한 수열이 된다고 생각한다.
그러면 중간값은 각 루트의 있는 값을 비교해서 선택하면 된다.
우선순위큐가 이러한 구조로 정렬되어있기때문에 사용하면된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import org.omg.CosNaming.IstringHelper;
public class 가운데를말해요 {
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());
PriorityQueue<Integer> pqMax = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if(o1>o2) {
return 1;
} else if(o1<o2) {
return -1;
} else {
return 0;
}
}
});
PriorityQueue<Integer> pqMin = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if(o1<o2) {
return 1;
} else if(o1>o2) {
return -1;
} else {
return 0;
}
}
});
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;++i) {
st = new StringTokenizer(br.readLine());
int now = Integer.parseInt(st.nextToken());
INPUT(pqMax,pqMin,now);
Balance(pqMax,pqMin);
Query(pqMax,pqMin,now,sb);
sb.append("\n");
}
System.out.print(sb.toString());
}
private static void Balance(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin) {
int sizeMax = pqMax.size();
int sizeMin = pqMin.size();
if(sizeMax==0||sizeMin==0)return;
if(sizeMax>sizeMin) {
pqMin.add(pqMax.poll());
} else if(sizeMin>sizeMax) {
pqMax.add(pqMin.poll());
}
}
private static void Query(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin, int now, StringBuilder sb) {
if(pqMax.isEmpty()) {
sb.append(pqMin.peek());
return ;
} else {
if(((pqMin.size()+pqMax.size())&1) ==0) {
int left = pqMin.peek(); int right = pqMax.peek();
sb.append(left > right ? right : left);
} else {
if(pqMin.size()>pqMax.size()) {
sb.append(pqMin.peek());
} else {
sb.append(pqMax.peek());
}
}
}
}
private static void INPUT(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin, int now) {
if(pqMax.isEmpty() && pqMin.isEmpty()) {
pqMin.add(now);
return;
} else if(pqMax.isEmpty()) {
if(pqMin.peek() > now) {
int t = pqMin.poll();
pqMax.add(t);
pqMin.add(now);
} else {
pqMax.add(now);
}
} else {
if(pqMax.peek() < now) pqMax.add(now);
else pqMin.add(now);
}
}
}
'알고리즘 > 구현,시뮬' 카테고리의 다른 글
BOJ - 11728 ) 배열 합치기 (0) | 2021.07.29 |
---|---|
프로그래머스 ) 음양더하기 (0) | 2021.07.19 |
BOJ - 2170 ) 선 긋기 (0) | 2021.06.02 |
BOJ - 11003 ) 최솟값 찾기 (0) | 2021.03.10 |
BOJ - 18870 ) 좌표압축 (0) | 2020.11.24 |
Comments