[파이썬 코딩테스트] 5.덧칠하기 - 프로그래머스

링크

내 풀이1(X)

  • 동작은 정상적으로 하는데 실행시간이 길다고 실패함
  • 배열의 모든 요소를 돌아야 해서 느린 것으로 보임
def solution(n, m, section):
    answer = 0

    arr = list('O' if i+1 in section else 'X' for i in range(n))

    idx = 0
    while(idx < len(arr)):
        if (arr[idx] == 'O'):
            answer += 1
            idx += m
        else:
            idx += 1

    return answer

내 풀이2(O)

  • 칠하기 시작할 구역의 번호(section[0]) + 롤러의 길이(m) 보다 큰 구역들만 남기는 식으로 반복
  • 롤러의 길이(m)이 1인 경우 section의 배열 길이 자체가 최소횟수
def solution(n, m, section):
    answer = 0

    if (m == 1):
        answer = len(section)
    else:
        while(len(section) > 0):
            num = section[0] + m
            section = [i for i in section if i >= num]
            answer += 1

    return answer

다른 풀이

  • 칠하기 시작할 구역의 번호(prev) + 롤러의 길이(m) 보다 큰 첫 번빼 구역을 찾아 그 횟수를 합산하는 방식
def solution(n, m, section):
    answer = 1
    prev = section[0]
    for sec in section:
        if sec - prev >= m:
            prev = sec
            answer += 1

    return answer

검증용 코드

ns = [8, 5, 4]
ms = [4, 4, 1]
sections = [[2, 3, 6], [1, 3], [1, 2, 3, 4]]
results = [2, 1, 4]

for idx in range(len(results)):
    print(idx, '성공' if solution(ns[idx], ms[idx], sections[idx]) == results[idx] else "실패")

links

social