[소프티어 Lv3] 스마트 물류(구현)

[소프티어 Lv3] 스마트 물류

 

https://softeer.ai/practice/6279

Softeer - 현대자동차그룹 SW인재확보플랫폼

현대자동차그룹은 주요 물류센터에 각종 자동화 기기를 도입하며 ‘스마트 물류’를 실현하고 있다. 최근에는 자동차 반조립 부품(KD, Knock-Down) 물류기지인 KD센터에 포장 관련 자동화 로봇 개발과 구축을 완료했다. 기존 수작업으로 진행하던 일부 작업 라인을 자동화 기기로 전환해 생산성을 높이기 위한 시도다. 기다란 작업 라인에 로봇과 부품이 아래 그림과 같이 단위 간격으로 놓여 있다. 로봇들의 위치에서 거리가 K 이하인 부품만 잡을 수 있다. 왼쪽 오른쪽은 상관 없다.

위 그림에서 K = 1인 경우를 생각해보자. 이 경우 모든 로봇은 그의 위치 바로 옆에 인접한 부품만 집을 수 있다.

* 10번 위치에 있는 로봇은 바로 왼쪽 11번 위치에 있는 부품을 집을 수 있다. 이 경우 다음과 같이 최대 5개의 로봇이 부품을 집을 수 있다.
* 2번 위치에 있는 로봇은 1번 위치에 있는 부품을 집을 수 있다.
* 4번 위치에 있는 로봇은 5번 위치에 있는 부품을 집을 수 있다.
* 6번 위치에 있는 로봇은 7번 위치에 있는 부품을 집을 수 있다.
* 9번 위치에 있는 로봇은 8번 위치에 있는 부품을 집을 수 있다.
* 10번 위치에 있는 로봇은 11번 위치에 있는 부품을 집을 수 있다.
* 12번 위치에 있는 로봇은 집을 수 있는 부품이 없다.

만약 K = 2라고 한다면 다음과 같이 6개 로봇 모두가 부품을 집을 수 있다.

* 2번 위치에 있는 로봇은 1번 위치에 있는 부품을 집을 수 있다.
* 4번 위치에 있는 로봇은 3번 위치에 있는 부품을 집을 수 있다.
* 6번 위치에 있는 로봇은 5번 위치에 있는 부품을 집을 수 있다.
* 9번 위치에 있는 로봇은 7번 위치에 있는 부품을 집을 수 있다.
* 10번 위치에 있는 로봇은 8번 위치에 있는 부품을 집을 수 있다.
* 12번 위치에 있는 로봇은 11번 위치에 있는 부품을 집을 수 있다.

라인의 길이 N, 부품을 집을 수 있는 거리 K, 그리고 로봇과 부품의 위치가 주어졌을 때 부품을 집을 수 있는 로봇의 최대 수를 구하는 프로그램을 작성하라.

제약조건

1 ≤ N ≤ 20,000

1 ≤ K ≤ 10

입력형식

입력의 첫 줄에는 두 정수 N과 K가 나온다.

다음 줄에는 로봇과 부품의 위치가 문자 P(로봇)와 H(부품)로 이루어지는 길이 N인 문자열로 주어진다.

출력형식

입력에 대해서 부품을 집을 수 있는 최대 로봇 수(정수)를 나타낸다.

입력예제1

20 1 HHPHPPHHPPHPPPHPHPHP

출력예제1

8

입력예제2

20 2 HHHHHPPPPPHPHPHPHHHP

출력예제2

7

---

[내 풀이] - 실패

※ 소요시간 : 27 분 + 반례 생각하는데 거의 50분 

※ 풀이 전략

- deque에 k만큼의 이전 값들을 담아놓은 후, 현재 값이 P라면 deque에서 H를 찾고, 현재 값이 H라면 deque에서 P를 찾는다. 하지만 이렇게 풀면 공개 케이스는 통과하지만 히든 케이스는 통과하지 못한다.

- 반례 생각하는데 오래걸렸다. 원래 알고리즘 대로라면, 가장 첫 로봇 부터 값이 결정 되어야 한다. 그런데 만약 내가 풀이한대로 하면, dq에 값이 다 차기 전에는, i번째에 값이 결정되어야 했던 것들이 i보다 큰 위치에서 값이 결정되어 버린다. 이렇게 되면 값이 결정되는 순서가 뒤바뀌는 경우가 생길 수 있다. 기본적으로 로봇으로부터 가장 먼 왼쪽의 물품을 가져와야 알고리즘이 정상적으로 돌아가는데, i번째에 결정되어야 했던 것들이 보류 된 채 이후의 값들이 결정되는 사이에 순서가 바뀌어버리는 것이다. 

from collections import deque
# 입력
n, k = map(int, input().split())
data = list(input())

idxdq = deque()
typedq = deque()
check = [0]*n
cnt = 0
for i,x in enumerate(data):
  if x=='P':
    if 'H' in typedq and check[idxdq[typedq.index('H')]]==0:
      check[idxdq[typedq.index('H')]] = 1
      check[i] = 1
      cnt += 1
  if x=='H':
    if 'P' in typedq and check[idxdq[typedq.index('P')]]==0:
      check[idxdq[typedq.index('P')]] = 1
      check[i] = 1
      cnt += 1
  if len(idxdq) == k:
    idxdq.popleft()
    typedq.popleft()
  idxdq.append(i)
  typedq.append(x)
print(cnt+1)

 

※ 생각 정리 

- k가 작기 때문에 크게 효율을 따질 것 없이, 단순하게 위치 주변으로 있는지 없는지 체크하는 게 나았을 듯 하다.

- 이렇게 효율을 따지고 복잡하게 생각하다보면 놓치는 게 생겨버린다. 

---

[다른 사람의 풀이]

※ 풀이 전략

- 로봇 위치에서 k만큼의 반경에서 부품을 찾고, 찾은 부품은 'H'에서 다른 값으로 변경 처리를 해주고 cnt 를 1 증가시킨다.

import sys

n, k = map(int, sys.stdin.readline().split())
# 로봇 = P, 부픔 = H
r = list(str(sys.stdin.readline()))
cnt = 0
# 반복문을 통해 로봇을 찾는다.
for i in range(n):
    if r[i] == "P":
        # 로봇의 위치에서 바로 옆에 인접한 거리가 K이하인 부품을 찾는다.
        for j in range(i-k,i+k+1):
            # 부품을 집는 거리는 라인의 길이를 넘지않게 한다.
            if j < 0 or j > n:
                continue
            # 집은 부품은 다른 이름으로 바꿔 구분한다.
            elif r[j] == "H":
                # 부품을 집는 순간 카운트 해준다.
                cnt += 1
                r[j] = "A"
                break

print(cnt)

 

※ 중요 포인트

- check를 따로 만들 필요 없이 찾는 값이 아닌 다른 값으로 값을 채워주면 다음 검색 루프에서는 그 값이 검색되지 않는다.