[프로그래머스] 덧칠하기 (파이썬)

🗓️ 문제 설명

• 어느 학교에 페인트가 칠해긴 길이가 n미터인 벽이 있는데, 페인트가 벗겨져 벽에 페인트를 덧칠하기로 했습니다. 
• 전체 벽을 새로 칠하는 대신, 일부 지역만 칠하고자 합니다.
• 이를 위해 벽은 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 
• 벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
  • 롤러가 벽을 벗어나면 안 됩니다.
  • 구역의 일부분만 포함되도록 칠하면 안 됩니다.
• 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼면 이를 벽을 한 번 칠했다고 정의합니다.
• 한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만, 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다.
• 정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 반환하세요.
• 제한 사항
  • 1  ≤ m ≤ n ≤ 100000
  • 1 ≤ section의 길이 ≤ n
    • 1 ≤ section의 원소 ≤ n
    • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호
    • section에서 같은 원소가 두 번 이상 나타나지 않음
    • section의 원소는 오름차순으로 정렬
• 입출력 예시

n	m	section	result
8	4	[2, 3, 6]	2
5	4	[1, 3]	1
4	1	[1, 2, 3, 4]	4

 

💻 코드

최종 코드

 

코드 풀이

 

 

다른 사람 풀이

풀이 1번

1. 2번줄 : answer에 1을 더한 값으로 시작
2. 3번줄 : prev에 section의 첫 값을 저장
3. 4번줄 : section에서 값을 하나씩 꺼내는 반복문 시행
4. 5~7번줄 : sec에서 prev를 뺀 값이 m과 같거나 크다면 prev를 sec으로 변경하고 1을 더함

sec에서 prev를 뺀 값은 한번에 칠할 수 있는 범위이기 때문에 이 범위가 m보다 같거나 크다면 1회 페인트칠을 한 것으로 볼 수 있기 때문에 다음 범위를 확인하기 위해 prev를 sec로 변경하고 answer에 1을 더합니다.

 

⚙️ 시행착오

1차 시도

• 테스트 결과 : 시간초과(50%)

 

2차 시도

• 테스트 결과 : 시간초과(8%)