[Programmers][Python] 덧칠하기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

 

처음 작성한 코드

• 일정 구간을 한 번에 칠하는 것을 이용하여 몇 번째 벽까지 칠해져 있는지 체크하는 알고리즘으로 작성하였다.
• 처음벽부터 어디까지 색이 칠해져있는지 기록하는 변수 n_painted와 칠할 횟수의 변수 answer를 초기화시킨다.
• 각 section의 번호가 n_painted보다 값이 같거나 작으면 이미 페인트가 칠해져 있고, 반대의 경우에는 칠해져 있지 않다는 의미이므로 다음 알고리즘을 실행한다.
  • s번의 벽을 기준으로 한번 칠을 하게 되면, s + m - 1 번째 벽까지 칠이 되므로 n_painted를 그 값으로 갱신시켜 준다.
  • 칠 한 번이 끝났으므로 answer에도 1을 더해주게 된다.
• 반환되는 answer의 값은 총 칠한 횟수가 된다. 

def solution(n, m, section):
    n_painted, answer = 0, 0
    for s in section:
        if s > n_painted:
            n_painted = s + m - 1
            answer += 1
    return answer

# 입출력 예시
print(solution(8, 4, [2, 3, 6]))
print(solution(5, 4, [1, 3]))
print(solution(4, 1, [1, 2, 3, 4]))

생각보다 쉬운 문제였고, lv0에 어울리는 문제라 생각된다.

문제를 풀면서 탐욕법에 대한 설명이 있었는데, 문제에 부합되는 설명인지 잘 모르겠어서 관련 알고리즘에 대해 좀 공부를 해야 할 것 같다.

 

다른 코드

사소한 차이는 있으나 크게 다른 코드, 혹은 더 좋은 코드를 발견하지 못했다.