[Google Kick Start] 2021 구글 킥스타트 Round G Staying Hydrated 풀이

 

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b3a1c

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

단순히 brute-force 방식으로 풀면 시간 초과 에러가 난다. 이 문제에서 핵심은 search를 어떻게 효율적으로 할 것인가이다. 이를 위해선 최적의 x, y 좌표가 어디에 위치할 것인지에 대해 생각해봐야 한다.

x의 최적 위치만을 찾는다고 생각해보자. 만약 x1이라는 특정 지점을 기준으로 좌측에 가구가 a개 우측에 가구가 b개 있다고 해보자. 만약 a>b라면 각 가구로부터 거리가 최소가 되기 위한 x의 좌표는 당연히 x1을 기준으로 조금 더 좌측에 치우친 방향에 존재할 것이다.

이러한 생각을 가지고 x와 y의 좌표를 모두 구하면 된다. 두 개를 한꺼번에 구하려 하지 말고 따로 나누어 구한다고 생각해야 한다. 최종 시간 복잡도는 O(nlogn)이 나오게 된다.(정렬하는 부분 때문에)

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b3a1c

T = int(input())
for t in range(T):
    k = int(input())
    x, y = {}, {}
    for i in range(k):
        x1, y1, x2, y2 = list(map(int, input().split()))
        if x1 in x:
            x[x1] += 1
        else:
            x[x1] = 1
        if x2 in x:
            x[x2] += 1
        else:
            x[x2] = 1
        if y1 in y:
            y[y1] += 1
        else:
            y[y1] = 1
        if y2 in y:
            y[y2] += 1
        else:
            y[y2] = 1

    x = sorted(x.items())    
    y = sorted(y.items())
    
    ans_x, ans_y = 0, 0

    count = -1 * k
    for i in range(len(x)):
        count += x[i][1]
        if count >= 0:
            ans_x = x[i][0]
            break
    count = -1 * k
    for i in range(len(y)):
        count += y[i][1]
        if count >= 0:
            ans_y = y[i][0]
            break

    print(f"Case #{t+1}: "+str(ans_x)+' '+str(ans_y))