BOJ_1655 가운데를 말해요

Yodi.Song·2020년 9월 16일

Problem Solving

목록 보기

10/19

문제: https://www.acmicpc.net/problem/1655

Wrong Access

문자를 읽을때마다 리스트에 넣고 sort를 하고 나서 가운데 있는 글자를 반환하는 코드를 짰다.
그랬더니 시간초과가 나왔다 Oops! 일단 짜보고 안되면 그때서야 최선의 방법을 생각하는 그런 못된 습관을 가지고 있어서 이번에도 오류가 나고 나서야 다시한번 내 코드를 살펴보았다.

# 업데이트 될때마다 가운데 숫자를 계산 그리고 출력
def cal_mid(num_list):
    n = len(num_list)

    num_list = sorted(num_list)
    # 숫자의 길이가 홀수
    if n % 2:
        return num_list[n//2]
    # 숫자의 길이가 짝수
    else: return min(num_list[n//2-1], num_list[n//2])


n = int(input())
num_list = []
mid_list = []
for i in range(n):
    num = int(input())
    num_list.append(num)
    mid_list.append(cal_mid(num_list))
    # print(f"{i}번째 {num_list}")

# print(f"최종: {mid_list}")

# 출력
for val in mid_list:
    print(val)

Right Access

위에 작성한 내 코드를 보니까 하나의 수를 삽입할때마다 다시 소팅을 해주는 방법을 사용했는데
처음에 삽입할때부터 적당한 위치에 삽입을 한 후, 이미 정렬된 리스트의 가운데 값을 뽑아보면 어떨까 하는 생각이 들었다. 그래서 적당한 위치에 삽입하는 방법들을 생각해보니 바이너리 서치가 생각이 났고
바이너리 서치를 하면서 new one이 들어갈 최적의 위치를 찾고 넣어주는 방법을 선책했다.

def cal_mid(n_list, start, end, num):

    if start == end: return start
    mid = (start + end) // 2
    if num <= n_list[mid]:
        return cal_mid(n_list, start, mid, num)
    else:
        return cal_mid(n_list, mid+1, end, num)

n = int(input())
num_list = []
mid_list = []

for i in range(n):
    now = int(input())
    idx = cal_mid(num_list, 0, i, now)

    if idx == i: num_list.append(now)
    else: num_list.insert(idx, now)

    n_len = len(num_list)

    # 숫자의 길이가 홀수
    if n_len % 2:
        mid_list.append(num_list[n_len // 2])
    # 숫자의 길이가 짝수
    else:
        mid_list.append(min(num_list[n_len // 2 - 1], num_list[n_len // 2]))

for mid in mid_list:
    print(mid)