Posts 가운데를 말해요 [Python]
Post
Cancel

가운데를 말해요 [Python]

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])
This post is licensed under CC BY 4.0 by the author.

풍선 터뜨리기 [Python]

구글 colab과 vscode 연동하기

Comments powered by Disqus.