[프로그래머스] 덧칠하기 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

소스 코드

def solution(n, m, section):
    if len(section) == 1:
        return 1
    
    mini,maxi = section[0],section[-1] # 최소, 최대
    
    cover = mini + m - 1 # 지금까지 칠한 위치
    cnt = 1
    for i in range(len(section)):
        if cover >= section[i]: # 현재 위치가 이미 칠해진 경우
            continue
            
        cnt += 1 
        cover = section[i] + m - 1 # 새로 칠해지게 된 범위
        if cover > maxi: # 가장 큰 값을 넘어서면 스탑
            break
    
    return cnt

해설

• 그리디

그리디

문제 조건을 보면 m, n은 최대 100,000까지 입니다.

usechatgpt init success

그래서 처음엔 이분 탐색으로 풀어야 하는 건가 따져보았는데, 이분 탐색 대상이 딱히 없어 보였습니다.

현재 시점까지 칠해진 번호를 대상으로 놓기도 애매하고..

칠해진 개수를 대상으로 놓기도 애매하고..

 

다시 생각을 해보니 앞에서부터 칠할 수 있는 것들을 다 치우면 그것이 최선의 결과가 되겠더라구요.

같은 위치에 중첩해서 칠하는 상황만 피한다면, section 리스트에 들어있는 값들을 맨 앞에서부터 하나씩 치워나가면 되는 것이었습니다.

 

문제에서 준 예시를 살펴보겠습니다.

위 상황에서 페인트를 칠하는 순서는 사실 이렇게 될 필요는 없습니다.

오히려 2,3,4,5를 먼저 칠하고 3,4,5,6을 칠하는 것이 코드를 짜기는 더 쉽죠.

 

그럼 이런 건 어떨까요?

[1,2,3,4]를 먼저 칠하고 [3,4,5,6]을 칠하는 경우.

또 [1,2,3,4]를 먼저 칠하고 [5,6,7,8]을 칠하는 경우.

어떤 식으로 해도 상관이 없습니다.

 

사실 조건을 까다롭게 설정한다면 필요한 페인트질 횟수가 달라지겠지만,

기본적으로는 앞에서부터 칠하면 똑같습니다.

아니 오히려 그래야지만 최선의 결과를 얻기가 편하죠.

 

for문을 살펴봅시다.

for i in range(len(section)):
    if cover >= section[i]: # 현재 위치가 이미 칠해진 경우
        continue

    cnt += 1 
    cover = section[i] + m - 1 # 새로 칠해지게 된 범위
    if cover > maxi: # 가장 큰 값을 넘어서면 스탑
        break

우선 section 리스트의 맨 앞 원소를 기준으로 m을 더하여 칠해질 수 있는 최대 범위를 cover에 담았습니다.

위 예시에서 첫 cover는 2 + 4 - 1 = 5가 됩니다.

이는 [2,3,4,5]를 칠했다는 것을 의미하죠.

 

이미 2~5값을 칠했기 때문에, section에 포함된 값들 중에서 2~5내의 것들은 굳이 살펴볼 필요가 없습니다.

이미 칠해져있으니까 6부터 보면 되는 것이죠.

그럼 section 내의 2,3은 continue로 패스하고 6을 보게 되겠네요.

 

이때는 바로 카운트를 올려줍니다.

색칠되지 않은 영역을 만났기 때문에 바로 색칠을 해주고 그 결과를 cover에 새롭게 반영합니다.

이때 이 cover의 값이 section 리스트의 최댓값을 초과하면 계산을 멈춥니다.

위 예시에서는 6 + 4 - 1 = 9가 되어 [6,7,8,9]를 칠한 개념이 됩니다.

이는 이미 칠해야 할 범위나 주어진 조건을 벗어나는 것이죠.

 

실제로는 이렇게 칠할 수는 없지만 정확히 어디서부터 칠을 해야 베스트인지는 굳이 찾을 필요가 없습니다.

우리는 '최소 페인트질' 횟수만 구하면 되기 때문에 그냥 범위를 벗어나는지만 확인해서 카운트해주면 되겠죠.

 

주의할 것은 리스트는 인덱스로 접근해야 하는데 section 리스트는 원래 정수값을 담고 있기 때문에 이 값을 적절히 조정하는 것이 중요합니다.

cover의 값을 정할 때도 부등호 관계를 잘 생각하여 -1을 해주어야 합니다.

그렇지 않으면 4칸을 칠하려고 한 것이 5칸을 칠하게 되어 오류가 발생하기 때문입니다.