[프로그래머스][PYTHON] Lv. 1 덧칠하기

문제 설명

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

프로그래머스

 

 

처음 시도한 풀이

## 틀린 풀이
def solution(n, m, section):
    answer = 0
    # 페인트가 칠해진 구역은 1로, 페인트가 벗겨진 구역은 0으로 지정
    wall = [1] * n
    for i in section:
        wall[i-1] = 0
    
    # wall 안에 0이 있으면 페인트질 반복
    while wall.count(0) > 0:
        # 롤러의 길이만큼 모두 1로 변경. 1은 페인트칠이 되었다는 의미
        tmp = wall.index(0)
        wall[tmp:tmp+m] = [1] * m
        answer += 1
        
    return answer

 

리스트의 인덱스를 이용하여 페인트가 칠해진 구역은 1로, 페인트가 벗겨진 구역은 0으로 지정하여 풀어보았다. 

wall 배열 안에 페인트가 안칠해진 구역(0)이 있으면, 페인트질을 반복하는 형식으로 풀어보았다. 

 

 

50개의 테스트 케이스 중 12, 17, 35번에서 시간초과가 발생하였다.

 

count를 통해 배열의 순회를 하는 것이 시간이 오래걸리기 때문에 시간초과가 발생했던 것이였다. 

(count 함수의 시간복잡도는 O(n)이다)

 

따라서, 배열을 이용하는 것이 아닌 다른 풀이를 생각해야했다. 

 

정답 풀이

## 맞은 풀이
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

 

다른 사람의 풀이를 참고한 코드이다ㅠ

사실 처음에 보고 좀 이해하기 어려웠다. 

 

n_painted는 페인트가 칠해진 구역의 끝을 나타낸다. 

section 안의 값들만을 순회하며, m만큼의 페인트 칠을 해주고, 

다음 section의 원소가 이미 칠해진 구역(n_painted)보다 클 때만 n_painted를 갱신하고, answer을 더한다. 

각 section의 원소가 n_painted보다 작거나 같으면, 이미 페인트가 칠해져있기 때문이다. 

 

-> 하나씩 써보며 풀이해보니 이해가 되었다! 

 

다른 사람 풀이

def solution(n, m, section):
    answer = 1 # 칠하는 횟수
    paint = section[0] # 덧칠 시작점
    for i in range(1, len(section)):
        if section[i] - paint >= m:
            answer += 1
            paint = section[i]
            
    return answer

 

위의 코드와 굉장히 유사한 풀이이다! 

이는 전체 section의 범위를 이용하는 것이 아닌, 덧칠을 해야하는 구간인 secion 요소들 간의 범위를 구한 코드이다. 

덧칠 시작점인 paint를 section[0]으로 정해놓고, for문을 통해 paint와 section[i] 간의 간격을 구한다. 

 

즉, 롤러의 길이 m=4이면 1, 2, 3, 4를 1번의 페인트칠로 칠할 수 있으므로, 

1번의 칠로 가능한 범위는 4-1=3이다. 즉, m-1 이다. 

따라서, m-1의 범위까지는 1번의 페인트칠로 가능하므로, m부터는 2번의 페인트칠이 필요하다. 

그러므로 section[i] - paint가 m 이상이면 answer+1을 해주어야 한다. 

 

이렇게되면 1번의 페인트칠을 완료했으므로, 다음 칠할 구간을 찾게 된다. 

다음 칠할 구간을 찾기 위해 section[i]를 paint 시작점으로 바꾸고, 다시 범위를 찾는 과정인 for문을 반복한다. 

 

느낀점

1단계 문제를 풀고있긴한데,, 알고리즘 강의를 먼저 듣는게 좋을 것 같다. 

생각보다 알고리즘 지식이 많이 떨어지는듯하다.

유튜브 나동빈님의 '이테코' 강의를 먼저 들으면서, 그 알고리즘에 맞는 문제들을 풀어보는 형식으로 해봐야겠다!