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

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

프로그래머스

---

python

def solution(n, m, section):
    answer = 0       
    idx = 0
    while idx <= n:
        if idx in section:
            answer += 1
            idx += m
        else:
            idx += 1
    return answer

처음에 코드를 이렇게 짰더니 2개의 테케에서 시간초과가 났다.

---

그래서 아래 코드로 수정하였다.

def solution(n, m, section):
    answer = 0       
            
    cur = 1 # 현재 위치
    idx = 0
    while idx < len(section):
        if cur <= section[idx]:
            cur = section[idx]
            answer += 1
            cur += m
        idx += 1
    return answer

1번부터  n번째 섹션까지 순서대로 돌기로 한다.

현재 위치에서 페인트를 칠하지 않아도 된다면, 페인트를 칠해야하는 가장 가까운 영역으로 이동해서 페인트칠을 한다.

 

 

단순구현 문제인데 인덱싱하는게 너무 헷갈려서 약간 고생했다. ㅠㅠㅠ 나 바보...

---

 

다른 분들 풀이를 보니까, 리스트 자료형이 시간복잡도가 안 좋아서인지

deque나 set 등으로 문제를 푼 분들이 많았다.

 

내가 첫 번째로 제출했던 코드도 리스트 말고 set으로 풀면 시간초과가 나지 않았다.

def solution(n, m, section):
    section = set(section) ### 수정
    answer = 0       
    idx = 0
    while idx <= n:
        if idx in section:
            answer += 1
            idx += m
        else:
            idx += 1
    return answer

이렇게 두 번째 라인만 추가해주니 정답판정을 받을 수 있었다!