URL : https://www.acmicpc.net/problem/1655
문제
- 백준이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
- 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
출력
- 한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
문제풀이
- 1) 결국 heap을 사용하게 됨
- heap도 최대힙, 최소힙을 구현해야함.
- 힙은 결국 루트가 되는 맨앞의 원소를 pop하기 떄문임
- 중앙값을 찾기위해 left heap은 최대힙으로, right heap은 최소힙으로 설정
- python은 최소힙만 지원하므로, 최대힙으로 바꾸기 위해 num에 -값을 주어 최대힙으로 변경함
- 숫자에 음수를 취하면 최대,최소가 바뀌는 성질을 이용
- left heap과 right heap에 매번 번갈아가면서 num을 넣음
- 각각 heap에 원소가 1개이상씩 있으면, left heap의 최대값과 right heap의 최소값을 비교하여 left heap의 최대값이 더 크면 각 원소를 바꾸어줌
- letf heap = [7, 2, 1], right heap = [3, 8, 9] 일 경우, letf heap의 7과 right heap의 3이 바뀌어야 중앙값이 3으로 되기 떄문
- 이후 left heap의 맨 앞의 원소를 음수를 취해주고 (push할때 음수를 취했기 때문에) print하면 끝
- 2) arr를 입력받아 중앙값을 계산하는 함수를 만들어서 실행 -> 사실 이렇게 하면 풀릴줄 알고 문제를 풀었으나, 시간 초과 걸림
- 3) 중앙값 계산함수에 sort가 시간이 오래걸리는것같아 bisect를 찾아, insort를 사용하였으나, 마찬가지로 시간 초과
- 4) 중앙값 함수를 제거하고, insort는 자동으로 정렬이 되니까, 해당 함수를 사용함 시간초과
- 5) insort를 사용해서 중앙값 기준 letf arr과 right arr를 생성하여 left arr의 제일 뒤를 리턴해주는 코드 작성, letf의 맨뒤 원소와 right의 맨앞 원소를 비교하는 형식도 시간초과
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
32
# 1) heap을 사용하여 품
import sys
import heapq
N = int(input())
# N = int(sys.stdin.readline().strip())
# 최대힙
letf_heap = []
# 최소힙
right_heap = []
for _ in range(N):
n = int(input())
# n = int(sys.stdin.readline().strip())
if len(letf_heap) == len(right_heap):
# 최대힙을 위해 n에 -를 줌
heapq.heappush(letf_heap, -n)
else:
heapq.heappush(right_heap, n)
if right_heap and -letf_heap[0] > right_heap[0]:
max_v = heapq.heappop(letf_heap)
min_v = heapq.heappop(right_heap)
heapq.heappush(right_heap, -max_v)
heapq.heappush(letf_heap, -min_v)
print(-letf_heap[0])
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
32
33
34
35
36
37
38
39
40
41
7
1
1
5
1
2
2
10
2
-99
2
7
2
5
5
1
2
3
4
5
6
7
8
7
1
5
2
10
-99
7
5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 시간 초과
# 2) arr를 입력받아 중앙값을 계산하는 함수를 만들어서 실행 -> 사실 이렇게 하면 풀릴줄 알고 문제를 풀었으나, 시간 초과 걸림
import sys
def median(arr):
arr.sort()
if len(arr) %2 == 0:
print(arr[:int(len(arr) /2)][-1])
else:
print(arr[int(len(arr) //2)])
N = int(input())
arr = []
for i in range(N):
# n = int(input())
n = sys.stdin.readline().strip()
arr.append(n)
median(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 시간 초과
# 3) 중앙값 계산함수에 sort가 시간이 오래걸리는것같아 bisect를 찾아, insort를 사용하였으나, 마찬가지로 시간 초과
import sys
import bisect
def median(arr):
if len(arr) %2 == 0:
print(arr[:int(len(arr) /2)][-1])
else:
print(arr[int(len(arr) //2)])
N = int(sys.stdin.readline().strip())
arr = []
for i in range(N):
# n = int(input())
n = sys.stdin.readline().strip()
bisect.insort(arr, n)
median(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 시간 초과
# 4) 중앙값 함수를 제거하고, insort는 자동으로 정렬이 되기까, 해당 함수를 사용함 시간초과
import sys
import bisect
# input = sys.stdin.readline
n = int(input().rstrip())
x = []
answers = []
for _ in range(n):
bisect.insort(x, int(input().rstrip()))
if(len(x) % 2 == 0):
answers.append(x[int(len(x)/2)-1])
else:
answers.append(x[int(len(x)/2)])
for a in answers:
print(a)
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
32
33
34
# 시간 초과
# 5) insort를 사용해서 중앙값 기준 letf arr과 right arr를 생성하여 left arr의 제일 뒤를 리턴해주는 코드 작성, letf의 맨뒤 원소와 right의 맨앞 원소를 비교하는 형식
import sys
import bisect
N = int(input())
left_arr = []
right_arr = []
n = int(input())
# n = sys.stdin.readline().strip()
bisect.insort(left_arr, n)
print(left_arr[-1])
for _ in range(N - 1):
n = int(input())
# n = sys.stdin.readline().strip()
if len(left_arr) == len(right_arr):
bisect.insort(left_arr, n)
else:
bisect.insort(right_arr, n)
if left_arr[-1] > right_arr[0]:
max_v = left_arr.pop(-1)
min_v = right_arr.pop(0)
bisect.insort(left_arr, min_v)
bisect.insort(right_arr, max_v)
print(left_arr[-1])
else:
print(left_arr[-1])