[백준 19941 / Python / 실버3] 햄버거 분배

문제

 

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.

can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다.

 

import sys

input = sys.stdin.readline

"""

N: 식탁의 길이

K: K 이하 거리 햄버거 먹기 가능

table: 사람과 햄버거의 위치

사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?

K가 최대 10이니 가능할거같다. K <= N이었으면 힘들었을듯.

햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.

왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다.

"""

def can_eat(idx, K):

    # 기준 (사람 또는 햄버거)

    point = table[idx]

    # idx 뒤로 K거리만큼 잘라낸다 (슬라이싱은 인덱스오류 안남)

    sliced_table = table[idx + 1: idx + K + 1]

    # 거리 내에 있는 햄버거/사람을 찾으면 방문 처리

    for i in range(len(sliced_table)):

        if point != sliced_table[i] and not visited[idx + 1 + i]:

            visited[idx + 1 + i] = True

            return True

           

    return False

           

N, K = map(int, input().split())

table = list(input().strip())

visited = [False] * N

result = 0

for i in range(N):

    # 아직 매칭되지 않은 사람/햄버거에 대해 진행

    if not visited[i]:

        visited[i] = True

        if can_eat(i, K):

            result += 1

print(result)

 

일단, 나는 사람(P)과 햄버거(H)를 매핑되는 관계로 간주하고 딱히 구분짓지 않았다.

그리고 visited 리스트를 사용해서 이미 매핑된 사람/햄버거는 방문처리하여 다시 탐색하지 않게 했다.

 

사람과 햄버거를 구분짓지 않으면, 왼쪽부터, 즉 0번 인덱스부터 차례로 기준점이 되는 것이 가능해진다.

그리고 각 기준점에서 K거리만큼의 범위만 확인하되, H라면 P를, P라면 H를 찾으면 된다. 요소는 H 또는 P 2개밖에 없기 때문에 != 연산을 사용하면 된다.

 

그리고 매핑될 때마다 result를 1씩 추가해 주면 정답을 도출할 수 있다.

 

시간 복잡도는 O(N)이고 정확히는 O(KN) 인데, K의 최대값이 몇이냐에 따라 복잡도가 많이 바뀐다.

이 문제에서 K는 최대 10이라, 정확히는 O(10N) 이라서 O(N)에 수렴하는데,

만약 K의 최대값이 N이었다면 O(N^2)이 되고 4억번 이상의 연산이 필요하여 문제 해결이 어려웠을 것이다.

 

한 번에 통과

한 번에 통과했다.

다른 사람들 제출 내역을 보니, 최근 제출 중에는 내 코드가 가장 빨랐다. 매우 기쁘다.