[백준] 1449. 수리공 항승

 

 

🗂️   문제 

1449. 수리공 항승

---

---

📌   Point

Two Pointers

테이프 시작 지점과 끝 지점을 이용해서 투 포인터로 풀이한다.

 

 

https://youngone-kang.tistory.com/30

[Algorithm] Two Pointers (투 포인터)

---

📄   코드

n, l = map(int,input().split())
pipes = list(map(int,input().split()))
pipes.sort()

# 테이프 시작 위치
start = pipes[0]-0.5
# 테이프가 끝나는 위치
end = start + l
# 처음 지점에서 테이프를 사용하기 때문에 정답값은 1개 이상이 됨.
ans = 1

for i in range(0, n):
    # 물 새는 곳이 테이프 내에 있는 경우
    if start < pipes[i] < end:
        continue
    # 테이프가 벗어난 위치에 물이 새는 경우
    else:
        ans += 1
        start = pipes[i] - 0.5
        end = start + l

print(ans)

---

✍🏻   풀이

시간 복잡도 : O(N)

 

1. pipe에 물 새는 위치를 오름차순으로 정렬 (문제에서 순서대로 주어지지 않기 때문에 정렬 필요)
2. 테이프의 시작 지점과 끝 지점 범위를 활용해서 물 새는 위치가 이 범위 내에 있는지 확인
3. 2에서 범위 내에 있는 경우에는 continue
4. 2에서 범위 내에 없는 경우
   • 테이프 수를 +1 하고 테이프 시작, 끝 지점을 재설정한다.