[Lv2.] 덧칠하기

👉 사용 언어 : PYTHON3

덧칠하기

✅ Solution

import math

def solution(n, m, section):
    cnt = 0
    for i in range(len(section)):
        if section[-i] - section[-i-1] > m:
            cnt += 1
    return math.ceil((section[-1] - section[0] +1) / m) - cnt

: 실패 케이스 발생 (54점)

: 문제 예시에 끼워맞추는 풀이이기 때문에 잘못된 접근..!

def solution(n, m, section):
    cnt = 0
    i = 1
    length = len(section)
    while i <= length:
        j = i+1
        if i < length:
            while j <= length and section[-i] - section[-j] +1 <= m:
                j += 1
            cnt += 1
            i = j
        else:
            cnt += 1
            i += 1
    return cnt

 

👉 문제 설명 및 제한 사항

• 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙인 상황
• 벽에 페인트를 칠하는 롤러의 길이는 m미터
• 롤러로 벽에 페인트를 한 번칠하는 규칙
  • 롤러가 벽에서 벗어나면 안 된다.
  • 구역의 일부분만 포함되도록 칠하면 안 된다.
• 한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야함❗️
• 롤러로 페인트칠을 하는 횟수를 최소화
• 매개변수 : 정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section
  • 1 ≤ m ≤ n ≤ 100,000
  • 1 ≤ section의 길이 ≤ n
  • 1 ≤ section의 원소 ≤ n
  • section에서 같은 원소가 두 번 이상 나타나지 않는다.
  • section의 원소는 오름차순으로 정렬되어 있다.
• 리턴값 : 롤러로 페인트칠해야 하는 최소 횟수

👉 아이디어

• section의 길이만큼 반복문을 돌린다. (= idx1)
• 인덱스에 -를 붙여 맨 끝부터 비교할 것이기 때문에 idx1이 section 길이 이상이면 indexError가 발생한다.
• idx1 +1 값부터 section 길이까지 내부 반복문을 돌린다. (= idx2)
  • 그 둘의 차이(= section[-idx1]과 section[-idx2]) 가 m보다 커질때까지 반복문을 돌린다.
  • 빠져나오면 카운트변수 +1을 한 후, idx1을 idx2로 업데이트해준다. (원래 idx1 ~ idx2-1까지 칠했으므로❗️)
• idx1이 section 길이 이상이 되면, 칠할 구역이 1개 남은 것이기 때문에 카운트변수 +1을 한 후 idx1도 +1을 한다.
  • idx1에 +1을 하는 이유는 while문을 끝내기 위해❗️
• 카운트 변수를 리턴한다.

✅ 다른 사람 풀이 참고

def solution(n, m, section):
    answer = 1
    prev = section[0]
    for sec in section:
        if sec - prev >= m:
            prev = sec
            answer += 1

    return answer

 

👉 깨달은 것 / 알게된 것

• 두 개의 값의 차이가 m 이상이 될때까지 계속 비교하는건 동일
• 위의 방법은 맨 앞 원소부터 차례대로 비교하였다!
• m 이상이 되면 현재까지 칠한 구역을 업데이트하여 prev를 sec으로 바꿔주는 방법도 동일
• 훨씬 더 간결한 코드가 될 수 있었다....💦