위메이드 코테 후기

잘하지도 못하는 재귀 구현이 필요한 문제에 시간 투자하느라 정작 풀 수 있었던 3번 문제를 풀지 못함..

 

n x n 크기 좌석을 첫 손님이 0,0 부터 앉고나서 k번째까지 각 앉아 있는 손님의 좌표들이 최대가 되는 거리가 되도록 앉을 때 k번째 앉는 좌표를 구하는 문제였슴...

 

지금은 풀었는데 불과 30분전에는 풀지못함.. ㅅㅂ...

 

아까워서 여기라도 올림..

import copy


def kprint(arr):
    for a in arr:
        print(a)


def caculdis(coordis, n):
    newcoordis = copy.deepcopy(coordis)
    arr = [[(n * n) + 1] * n for _ in range(n)]
    for coord in newcoordis:
        x, y = coord
        for i in range(n):
            for j in range(n):
                distance = abs(x - i) + abs(y - j)
                if arr[i][j] > distance:
                    arr[i][j] = distance

    maxVal = -1
    for i in range(n):
        for j in range(n):
            if arr[i][j] > maxVal:
                maxVal = arr[i][j]

    maxcoords = []
    for i in range(n):
        for j in range(n):
            if arr[i][j] == maxVal:
                maxcoords.append([i, j])

    maxcoords.sort(key=lambda x: x[1])
    coordis.append(maxcoords[0])
    return coordis


def solution(n, k):
    newarr = [[(n * n) + 1] * n for _ in range(n)]

    cnt = 0
    coordis = [[0, 0]]
    while cnt < k - 1:
        cnt += 1
        res = caculdis(coordis, n)
        coordis = res

    cnt = 1
    for c in coordis:
        x, y = c
        newarr[x][y] = cnt
        cnt += 1

    x, y = coordis[-1]
    return x + 1, y + 1


print(solution(5, 12))  # [4, 4]

# 5, 16 [1, 2]