이 포스팅에서는 Google Kickstart 2019 Round D 의 2번 문제인 ‘Latest Guests’의 풀이와 코드를 제공합니다.
본 풀이는 공식적인 풀이와 완벽히 일치하지 않을 수 있으며, 온라인 Submission을 통과하였습니다.
공식 풀이 및 자세한 사항은 공식 페이지를 참조하세요.
문제 링크 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061/0000000000161427
카테고리 : Binary Search, Hash
난이도 : 중간
N개의 지점이 원을 이루며 존재한다. 마치 시계와 같이 1에서 N까지 시계 방향으로 존재하는 것이다.
G명의 게스트는 시작점으로부터 매 초마다 시계방향 또는 반시계 방향으로 움직인다.
게스트들은 총 M초 동안 움직이게된다.
N개의 지점 각각에 대해 가장 마지막으로 그 지점을 거쳐간 게스트는 1점을 받게된다.
만약 두 명 이상의 게스트가 동시에 그 지점을 마지막으로 거쳐갔다면, 모두 1점씩을 받게된다.
각각의 케이스마다 모든 게스트들의 점수를 출력하여라.
첫 째 줄에는 테스트 케이스의 수 T가 주어진다.
두 번째 줄에는 N, G, M이 주어진다.
그 다음 N개의 줄에는 각 게스트의 시작 위치와 이동방향인 x, y가 주어진다.
1 5 3 2 5 C 2 A 1 A
결과 – 2 2 1
위 케이스는 5개의 지점에서 3명의 게스트가 2초동안 움직이는 경우다.
1번 게스트는 5 -> 1 -> 2
2번 게스트는 2 -> 1 -> 5
3번 게스트는 1 -> 5 -> 4 다.
1번 지점은 1초의 시점에 (1, 2)번 게스트가 동시에 지나간다.
2번 지점은 2초의 시점에 1번 게스트가 지나간다.
4번 지점은 2초의 시점에 3번 게스트가 지나간다.
5번 지점은 3초의 시점에 2번 게스트가 지나간다.
Simple Solution O(N^2)
가장 간단한 방법은 직접 문제의 조건을 시뮬레이션 하는 것이다.
각 초마다 각 게스트들을 주어진 방향으로 이동시킨다. 각 지점은 최근 방문자에 대한 기록을 가지고 있다.
이동한 게스트는 이 기록들을 지우고 자신을 새롭게 기록한다. 물론 같은 시간에 진입한 게스트는 지우면 안된다.
이를 위해서 tmp 같은 배열이나 dictionary를 만들어놓고, 매 iteration마다 원본에 덮어씌우면 된다.
이 방법은 Small에서는 가능할 수도 있으나, Large에서 TLE에 걸리게된다.
Binary Search O(N log N)
이 방법을 위해 전처리가 필요하다. 우선 M >= N인 경우에, 게스트들이 여러 바퀴를 도는 것은 고려할 필요가 없다.
이 경우 R = M % N만큼 게스트들을 우선 이동시키고, 모든 게스트들이 딱 한 바퀴를 돈다는 가정하에서 문제를 해결할 수 있다.
물론 M < N인 경우도 그대로 처리할 수 있다.
모든 지점을 기준으로, 자신을 마지막으로 거쳐간 게스트를 찾아내는 것이 목표다.
이 게스트를 찾아낸 다음에 1점을 더해주면 된다. 이 과정도 좀 간단히 할 필요가 있다.
처음에 한 지점에서 N명의 게스트가 같은 방향으로 출발하는 경우를 생각해보자.
이 경우 각 게스트마다 1점씩 주게되면, N초를 움직인다고 할 때 O(N^2)의 시간이 걸린다.
이 방법 대신에 같은 지점에서 같은 방향으로 움직이는 게스트를 하나의 그룹으로 바라볼 수 있다.
시계 방향과 반시계 방향에 대해 딕셔너리를 만들어서, 시작점을 키로 게스트를 관리할 수 있다.
시계 방향으로 움직이는 게스트가 [1, 3,6]의 위치에서 시작하고, N은 6이며 M은 3인 상황을 살펴보자.
지점 2에 대해서 가장 마지막으로 도달하는 게스트를 찾는 문제를 고려해보자.
모든 게스트들은 한 바퀴 이상을 돌 수 없기 때문에, 한 바퀴 전의 상태를 가상의 배열로 구성할 수 있다.
즉, 모든 게스트 위치들에 대해 한 바퀴를 돌기 위한 거리 N을 빼서 [-5, -3, 0]을 만들 수 있다.
이것을 이어붙이면 [-5, -3, 0, 1, 3, 6]의 값을 얻는다. 이것들 모두를 게스트로 간주해도 된다.
이 게스트들은 2 이후에 존재할 수는 없다. 3초 동안만 움직이므로 2 – 3인 -1보다 이전에 있을 수도 없다.
따라서 -1 <= x <= 2인 원소 중에서 가장 작은 값을 구하면 0을 정답으로 얻게 된다.
이 값이 1보다 작기 때문에 N을 더하면 원래 게스트 위치인 6을 얻게 된다.
반시계 방향은 이동이 반대이므로, 게스트가 [1, 3, 6]의 위치에서 시작한다면 [1, 3, 6, 7, 9, 12]를 얻는다.
각 지점에 대해 시계방향과 반시계 방향의 후보를 구해서 그 중에서 지점보다 더 먼 것을 찾아서 선택한다.
만약 두 방향의 후보가 같은 거리를 가진다면 둘 다 선택되어야 한다.
Binary Search를 사용해서 검색을 수월하게 만들 수 있다. 사실 x <= 2 조건은 마지막에 검사하면 된다.
-1 <= x인 x 중에서 최소 값을 구하는 것만으로도 x <= 2 조건을 맞추기 위해 노력하는 것이기 때문이다.
최종적으로 구해진 값이 x <= 2인지만 체크하면 된다.
def printAnswer(tt, answer):
answer = " ".join([str(x) for x in answer])
print ("Case #" + str(tt) + ": " + answer)
def addGuest(idx, position, Clock):
if position not in Clock:
Clock[position] = []
Clock[position].append(idx)
def rotateGuest(origin, step, direction, N):
rotated = {}
for key_ in origin.keys():
if direction == "C":
newKey = (key_ + step) % N
else:
newKey = (key_ - step + N) % N
rotated[newKey] = origin[key_]
return rotated
def extendArr(guest, direction, N):
arr = [0] * len(guest)
for i in range(len(guest)):
if direction == "C":
arr[i] = guest[i] - N
else:
arr[i] = guest[i] + N
if direction == "C":
return arr + guest
else:
return guest + arr
def findClosestLower(guest, position, step):
if len(guest) == 0:
return None
target = position - step
l, r = 0, len(guest) - 1
ret, distance = None, None
while l <= r:
mid = (l + r) // 2
if guest[mid] >= target:
ret = mid
r = mid - 1
else:
l = mid + 1
if ret != None and guest[ret] <= position:
distance = position - guest[ret]
return [(guest[ret] + N) % N, distance]
return None
def findClosestBigger(guest, position, step):
if len(guest) == 0:
return None
target = position + step
l, r = 0, len(guest) - 1
ret, distance = None, None
while l <= r:
mid = (l + r) // 2
if guest[mid] <= target:
ret = mid
l = mid + 1
else:
r = mid - 1
if ret != None and guest[ret] >= position:
distance = guest[ret] - position
return [guest[ret] % N, distance]
return None
def getLatest(a, b):
if a != None and b != None:
if a[1] > b[1]:
b = None
elif a[1] < b[1]:
a = None
return a, b
def addCount(spotCount, a):
if a == None:
return
if a[0] not in spotCount:
spotCount[a[0]] = 0
spotCount[a[0]] += 1
def updateGuestCount(guestCount, spotCount, guestDict):
for key in spotCount.keys():
for guest in guestDict[key]:
guestCount[guest] += spotCount[key]
T = int(input())
for tt in range(1, T + 1):
N, G, M = [int(x) for x in raw_input().split()]
# Add Guest to Clock
guestDict, guestDict2 = {}, {}
for idx in range(G):
position, rotation = raw_input().strip().split()
if rotation == 'C':
addGuest(idx, int(position) - 1, guestDict)
else:
addGuest(idx, int(position) - 1, guestDict2)
# Rotate if M > N
if M > N:
R = M % N
M = N
guestDict, guestDict2 = rotateGuest(guestDict, R, "C", N), rotateGuest(guestDict2, R, "A", N)
# Flatten and extend for binary search
guest, guest2 = list(guestDict.keys()), list(guestDict2.keys())
guest.sort(), guest2.sort()
guest, guest2 = extendArr(guest, "C", N), extendArr(guest2, "A", N)
# Find closest one from each direction
spotCount, spotCount2 = {}, {}
for idx in range(N):
c1 = findClosestLower(guest, idx, M)
c2 = findClosestBigger(guest2, idx, M)
a1, a2 = getLatest(c1, c2)
addCount(spotCount, a1)
addCount(spotCount2, a2)
# update Guest's count
guestCount = [0] * G
updateGuestCount(guestCount, spotCount, guestDict)
updateGuestCount(guestCount, spotCount2, guestDict2)
printAnswer(tt, guestCount)
Competition Kickstart ‘X or What’
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.