인프런 커뮤니티 질문&답변

from copy import deepcopy

def init_sort_checker(checkers):
    tmp_list = []
    sorted_sum_list = []
    for idx, chk in enumerate(checkers):
        for i, tgt in enumerate(checkers):
            if idx == i: #본인으로 가는 값은 제외
                continue
            x_val = abs(chk[0] - tgt[0])
            y_val = abs(chk[1] - tgt[1])
            # price, [src, tgt] 순 정렬
            tmp_list.append([x_val + y_val, [idx, i]])
        tmp_list.sort(key=lambda x: x[0]) # price 값 적은 순서대로 정렬
        sorted_sum_list.append(deepcopy(tmp_list))
        tmp_list = []

    return sorted_sum_list


def sort_sum_target(sorted_sum_list, k):
    lowest_price = 1000000*k
    target_idx = -1
    for idx, line in enumerate(sorted_sum_list):
        cnt = 0
        line_price = 0
        for price in line:
            if cnt >= k-1:
                break
            line_price = line_price + price[0]
            cnt += 1
        if line_price < lowest_price:
            lowest_price = line_price
            target_idx = idx
    return target_idx


def k_tgt_process(k, sorted_tgt, sorted_sum_list):
    tgt_line = sorted_sum_list[sorted_tgt]
    tgt_loc = []
    for i in range(k-1):
        tgt_loc.append(tgt_line[i][1])

    return tgt_loc


def k_sorting_process(tgt_loc, checkers):
    tgt_list = []
    for tgt in tgt_loc:
        tgt_list.append(tgt[0])
        tgt_list.append(tgt[1])
    tgt_list = list(set(tgt_list))

    x_list = []
    y_list = []
    tgt_checkers = []
    for tgt in tgt_list:
        x_list.append(checkers[tgt][0])
        y_list.append(checkers[tgt][1])
        tgt_checkers.append(checkers[tgt])
    x_list.sort()
    y_list.sort()

    if len(x_list)%2 == 0: #짝수
        x_chk_point = [int(len(x_list)/2-1),int(len(x_list)/2)]
    else: # 홀수
        x_chk_point = [int(len(x_list)/2)]

    if len(y_list)%2 == 0: #짝수
        y_chk_point = [int(len(y_list)/2-1),int(len(y_list)/2)]
    else: # 홀수
        y_chk_point = [int(len(y_list)/2)]

    #모아볼 위치의 case 집합
    chk_point_list = []
    for x_chk in x_chk_point:
        for y_chk in y_chk_point:
            chk_point_list.append([x_chk,y_chk])

    # 각 checker 위치에서 좌표로 이동하는데 드는 값 계산

    ttl_price_list = []
    for chk in chk_point_list:
        x_tgt = chk[0]
        y_tgt = chk[1]
        price_list = []
        for checker in tgt_checkers:
            x = checker[0]
            y = checker[1]

            if x_list[x_tgt] > x:
                x_price = x_list[x_tgt] - x
            else:
                x_price = x - x_list[x_tgt]

            if y_list[y_tgt] > y:
                y_price = y_list[y_tgt] - y
            else:
                y_price = y - y_list[y_tgt]

            price = x_price + y_price
            price_list.append(price)
        price_list.sort()
        ttl_price_list.append(price_list)

    return ttl_price_list


def TestCases(N):
    checkers = [list(map(int,input().split())) for _ in range(N)]
    sorted_sum_list = init_sort_checker(checkers)
    output_str = '0'

    for k in range(2, N+1):
        min_price = 2000000
        sorted_tgt = sort_sum_target(sorted_sum_list, k)
        tgt_loc = k_tgt_process(k, sorted_tgt, sorted_sum_list)
        ttl_price_list = k_sorting_process(tgt_loc, checkers)

        for n_list in ttl_price_list:
            tmp = 0
            for idx in range(k):
                tmp = tmp + n_list[idx]
            if tmp < min_price:
                min_price = tmp

        output_str = output_str + ' ' + str(min_price)
        tmp_str = list(map(int,output_str.split()))
    # print(output_str)
    print(*tmp_str)
N = int(input())

TestCases(N)

다음과 같이 코드 작성해봤는데, sample input에 대한 답은 다 도출되지만문제 제출하면 답이 틀리다 나오네요..반례나 코드상의 오류를 도와주실 수 있을까요?

[사용해본 input/output]

4
1 1
2 1
4 1
13 1
0 1 3 14

4
13 13
16 14
15 18
15 30
0 4 8 24

5
3 2
6 9
3 16
14 6
17 14
0 10 17 31 47

5
3 2
6 9
6 13
13 6
17 14
0 4 14 24 40


4
15 14
15 16
14 15
16 15
0 2 3 4

2
4 7
4 7
0 0

4
1 101
2 101
200 101
201 101
0 1 199 398