[BOJ] 14465번: 소가 길을 건너간 이유 5

https://www.acmicpc.net/problem/14465

 

문제

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

 

풀이

시간복잡도를 고려하지 않았을 때의 코드 ⤵️

Defect = []  #고장난 신호등을 저장
minNum = float('inf') #minNum의 초기값을 무한대로 설정

N, K, B = map(int, input().split())
for _ in range(B):
    Defect.append(int(input()))

for i in range(1, N - K + 2):
    num = 0
    for j in range(i, i + K):
        if j in Defect:
            num += 1
    minNum = min(minNum, num)

print(minNum)

 

시간을 위해 위 코드에 투포인터를 적용하면, i를 left pointer로, j를 right pointer로 생각할 수 있다.

Defect = []
minNum = 0
tempNum = 0

N, K, B = map(int, input().split())
for _ in range(B):
    Defect.append(int(input())) #고장난 신호등 입력받음

left, right = 1, K + 1 

#처음 1부터 K까지의 고장난 신호등 수
for i in range(1, K + 1):
    if i in Defect:
        minNum += 1
tempNum = minNum

while right < N + 1:
    if left in Defect and right not in Defect:
        tempNum -= 1
    elif left not in Defect and right in Defect:
        tempNum += 1
    minNum = min(minNum, tempNum)
    right += 1
    left += 1

print(minNum)

1부터 N까지 일자로 신호등의 놓여있다고 생각하면, 길이 K짜리 틀을 가장 왼쪽에서부터 한 칸씩 오른쪽으로 옮기며 그 안에 있는 고장난 신호등의 개수를 세는 것이라 생각할 수 있다.

이해를 돕기 위해 이미지를 만들어왔다 :)

길이 K의 틀을 한칸씩 오른쪽으로 옮기며 그 내부의 고장난 신호등의 개수를 세는 것이다.

이때, 위의 그림에 있는 화살표에 집중해보자. 왼쪽화살표를 left, 오른쪽 화살표를 right라고 하면 (투포인터 역할)

한 칸 오른쪽으로 이동했을 때, left, right의 신호등을 제외한 틀 안의 나머지 요소들은 그대로 유지된다는 것을 알 수 있다.

나머지는 유지되는 상황에서 left는 빠지고 right가 새로 들어오는 것이다.

 

따라서 

1. left가 고장, right가 정상인 경우: 기존 고장난 신호등 횟수 - 1 (고장난 신호등이 빠지고 정상 신호등이 들어옴)

2. left가 정상, right가 고장인 경우: 기존 고장난 신호등 횟수 + 1 (정상 신호등이 빠지고 고장 신호등이 들어옴)

이라고 생각할 수 있다.

 

tempNum이라는 변수에 위와 같은 변경사항을 저장한 후, minNum과 비교해서 더 작은 값을 저장했다.

그후 최종 minNum을 출력했다.

 

최대한 이해를 도울 수 있도록 그림까지 그리며 설명했는데... 이해에 도움이 되었을지는 모르겠다😮‍💨