문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력 1

4 2
1 2 100 101

예제 출력 1

2

예제 입력 2

4 3
1 2 3 4

예제 출력 2

2

예제 입력 3

3 1
3 2 1

예제 출력 3

3

나의 코드

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n")
  .map((r) => r.split(" ").map(Number));
const [N, L] = input[0];
input.shift();
const arr = input[0];

// 배열 오름차순 정렬 후 문제 풀이 시작
arr.sort((a, b) => a - b);
let count = 0;

while (arr.length) {
 // tapeEnd에 배열의 마지막 원소 저장
  const tapeEnd = arr[arr.length - 1];
  // tapeStart에 마지막 원소부터 테이프를 붙인다면 붙일 수 있는 가장 왼쪽의 원소 저장
  const tapeStart = tapeEnd - (L - 1);
  // tapeStart보다 크거나 같은 원소라면 이번 테이프로 막을 수 있으므로 pop();
  while (arr[arr.length - 1] >= tapeStart) {
    arr.pop();
  }
  // 테이프로 1번 붙인 후 count++
  count++;
}
console.log(count);

마지막 원소부터 시작하여 테이프를 붙인다고 생각하고 코드를 짰다.
한번에 테이프로 붙일 수 있는 최소값은 마지막 원소에서 L - 1만큼 왼쪽으로 떨어져있는 원소가 될 것이므로 이를 계산하여 tapeStart라는 변수에 저장했다. (이것을 고려하여 오름차순 정렬한 것)

그리고 이번 회차 때 테이프로 붙일 수 있는 원소 중 가장 작은 값은 tapeStart보다 크거나 같을 것이므로 이 범위에 해당하는 숫자는 모조리 pop하여 제거한다.
그리고 테이프 붙이기가 한번 끝나면 count++한다.

그리디가 약한 것 같아서 오랜만에 돌아왔다~~
그리디 좀 더 풀고 이코테에 있는 다익스트라 파이썬 코드 뜯어보기 시작하자 화이팅팅!!

---

미래에서 왔슴당~
오늘은 2023년 8월 8일.

오늘도 파이썬으로 이전에 풀었던 문제 복습!

from sys import stdin as s

s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n, l = map(int, s.readline().split())

spots = list(map(int, s.readline().split()))

answer = 0
spots.sort()

while spots:
    start = spots.pop()
    while spots and start - spots[-1] < l:
        spots.pop()
    answer += 1

print(answer)

테이프를 붙이기 시작하는 spot을 start로 지정한다.
현재 배열의 끝 원소와 start와의 거리가 문제에서 주어진 tape 길이보다 짧으면 (같을 때는 테이프로 못 붙임 주의) while문 진입한다. 진입하여 테이프로 붙인다고 생각하고 pop한다.
더 이상 끝 원소가 테이프로 붙일 수 있는 길이의 범위를 벗어나면 while문을 종료하고 answer를 1만큼 증가시킨다.

이전에 자바스크립트로 풀었을 때는 tapeStart와 tapeEnd 값을 미리 정했구나. 이것도 방법이겠군.

이번에 파이썬 코드를 풀면서 알게된 사실! 파이썬에서 리스트의 마지막 원소는 음수 인덱스로 접근 가능하다.
예를 들어 spots 리스트의 마지막 원소는 spots[-1]이다.
처음에 spots[len(spots) - 1]로 접근했었는데, 이렇게 길게 쓸 필요가 없었다는 사쉴!

여튼 좋은 복습이었다. 다음 문제 풀러~~ 갑니다~~ 짜이찌엔~