Softeer level3 스마트 물류 Python

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=414 

Softeer

풀이 코드

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
PHString = input().strip()

def is_valid(nextIdx):
    return 0 <= nextIdx < N

cntP = 0
V = [0 for _ in range(N)]
for idx in range(N):
    if PHString[idx] == "P":
        is_find = False
        for d in range(K, 0, -1):
            nextIdx = idx - d
            if is_valid(nextIdx) and PHString[nextIdx] == "H" and V[nextIdx] == 0:
                V[nextIdx] = 1
                cntP += 1
                is_find = True
                break
        if is_find == False:
            for d in range(1, K+1):
                nextIdx = idx + d
                if is_valid(nextIdx) and PHString[nextIdx] == "H" and V[nextIdx] == 0:
                    V[nextIdx] = 1
                    cntP += 1
                    break
print(cntP)

풀이 방법

1. 로봇(P)의 팔이 닿을 수 있는 가장 먼 곳이면서 왼쪽에 있는 부품(H)를 먼저 고릅니다.

=> for d in range(K, 0, -1)

=> 왜냐하면 for문을 통해서 맨 왼쪽에 있는 로봇 부터 부품을 고를 예정이기 때문에

2. 부품을 골랐으면 중복으로 고르지 못하게 방문배열 체크 V[nextIdx] = 1

3. 로봇도 카운트 해주고 이제 다음 로봇으로 가야 하기 때문에 break

잠깐!

여기서 그만두면 로봇이 왼쪽만 찾다가 부품이 없을 경우 끝나버립니다.

왼쪽에서 부품을 찾았으면 is_find = true

하지만 못 찾으면 그대로 is_find = false

4. 그러므로 오른쪽에 부품이 있는지 찾아야 합니다.

대신 왼쪽은 먼 곳 부터 고르는 것과 다르게 가장 가까운 곳부터 고릅니다.

=> for d in range(1, K+1)

=> 왜냐하면 어차피 오른쪽 방향으로 진행중이기 때문에 오른쪽에서 멀 경우 왼쪽에서는 가까울 수가 있음.

5. 결과적으로 로봇의 개수를 출력하면 끝