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

📌 문제

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

📌 풀이

풀이 1 - (11,20,24,26번 테스트 케이스 실패)

1. n갯수 만큼 1를 만든다.
2. section에 있는 숫자에서 -1을 뺀 인덱스의 값을 0으로 바꾼다.
3. while문을 돌려 0이 없을때까지 반복한다.
   3-1.가장 앞에 있는 0의 인덱스 값을 찾는다. 그리고 인덱스 값을 idx에 저장한다.
   3-2. idx:idx+m까지 1로 바꾼다 (덧칠했다는 뜻이다)
   3-3. 덧칠한 횟수를 담은 변수 answer에 1을 더한다.

def solution(n, m, section):
    answer = 0
    _list= [1 for _ in range(n)]
    for i in section:
        _list[i-1] = 0
        
    while True:
        if 0 not in _list:
            break
        idx=_list.index(0)
        _list[idx:idx+m] = [1] * m
        answer +=1
    return answer

풀이 2 - (성공)

(시간초과 오류는 항상 답답해요.. 이래서 효율성 어느정도 계산할 줄 알아야 하나바요... )
위의 코드에서 시간초과 난것은 제한사항을 보면 대략 가늠이 된다. n이 10만이고 section도 10이다. m이 1이면 _list를 10만번 재설정한다는 것이다. 이러한 재설정 방법을 사용하지 않고 코드를 짤 필요가 있다.

1. start를 -100001로 저장한다. (무조건 section의 첫번째 값을 덧칠하기 위해서)
2. section을 돌며 아래 과정을 반복한다.
   2-1. start+m 보다 section원소(s)가 더 큰지 비교한다.
   2-2. 더 크다면 s를 start에 저장하고 answer에도 +1을 한다.

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