https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
소스코드
풀이
★ 중간값을 찾기 위해 2개의 리스트를 만들어줍니다. 왼쪽, 오른쪽 리스트를 만들어주는데, 왼쪽 리스트는 최대힙으로, 오른쪽 리스트는 최소힙으로 만들어줍니다 !
★ 왼쪽 리스트를 최대힙으로 만드는 이유는 최소힙의 경우, 가장 작은 수부터 정렬되게 됩니다. 하지만 최대힙일 경우 가장 큰 수부터 정렬되기 때문에 왼쪽의 가장 큰수는 왼쪽의 나머지 수들보다 크고, 오른쪽의 수들보다 작은 중간값이 됩니다 다.
ex) input = 1,5,3,4
1 - left[-1],right = [] => 1출력
2 - left[-1], right[5] => 1출력
3 - left[-3,-1], right[5] => 3출력
4 - left[-3,-1], right[4,5] => 3출력
★ 한가지 더 고려해야 하는 조건이 존재하는데, 그동안 외친 수가 짝수인 경우, 중간값 2개 중 더 작은 수를 출력해야 합니다. 그렇기에 만약 최대힙의 첫번째 수가 최소힙의 첫번째 수보다 크다면 둘을 교환하여 위의 조건을 맞춰줍니다 !
ex) input = 1,5,3,2
1 - left[-1],right = [] => 1출력
2 - left[-1], right[5] => 1출력
3 - left[-3,-1], right[5] => 3출력
4 - left[-2,-1], right[3,5] => 2출력 (교환 발생)
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1590번: 캠프가는 영식 (Python) (0) | 2023.10.31 |
|---|---|
| [백준 알고리즘] 20551번: Sort 마스터 배지훈의 후계자 (Python) (1) | 2023.10.31 |
| [백준 알고리즘] 2231번: 분해합 (Python) (0) | 2023.10.26 |
| [백준 알고리즘] 14940번: 쉬운 최단거리 (Python, BFS) (0) | 2023.10.23 |
| [백준 알고리즘] 1253번: 좋다 (Python) (1) | 2023.10.23 |