[Google Kick Start] 2021 구글 킥스타트 Round F Trash Bins 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435bae/0000000000887c32

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

자신의 집 앞에 쓰레기통이 없는 경우 간단하게 두 가지 경우만 존재한다. 좌측 방향의 가장 가까운 쓰레기통을 선택하거나 우측 방향의 가장 가까운 쓰레기통을 선택하거나. 여기에 착안해서 L이라는 배열엔 무조건 좌측만을 선택해 거리를 계산한 값을 넣고, R이라는 배열엔 무조건 우측만을 선택해 거리를 계산한 값을 넣는다.

경계 조건을 신경써주어야 하는데 만약 00100으로 input이 주어지는 경우 L 배열을 채울 때 0, 1번째 인덱스 집들은 갱신하지 않고 최댓값 500,001로 그대로 둔다. R 역시 마찬가지이다.

그리고 두 배열의 값을 모두 갱신한 뒤에 마지막으로 동일한 인덱스의 L, R 값을 비교해 더 작은 것을 정답 ans에 더해준다.

문제의 핵심은 그냥 하나씩 거쳐가면서 좌, 우측 중에 가장 가까운 거리를 계산하는 방식인 O(n^2)이 아니라, 한 방향씩 거치면서 O(n)의 시간복잡도를 갖도록 프로그램을 설계하는 것이다.

 

코드

---

T = int(input())
for t in range(T):
    n = int(input())
    arr = input()
    L, R = [500001 for _ in range(n)], [500001 for _ in range(n)]
    # select left only
    pos = -1
    for i in range(n):
        if arr[i]=='0' and pos==-1:
            continue
        if arr[i]=='1':
            L[i] = 0
            pos = i
        else:
            L[i] = i-pos
    # select right only
    pos = -1
    for i in range(n-1,-1,-1):
        if arr[i]=='0' and pos == -1:
            continue
        if arr[i]=='1':
            R[i] = 0
            pos = i
        else:
            R[i] = pos-i
    ans = 0
    for i in range(n):
        ans += min(L[i], R[i])
    
    print(f"Case #{t+1}: {ans}")