프로그래머스 | 덧칠하기 (파이썬)

 

 

오늘도 오랑이는 문제를 풉니다. 

 

덧칠하기 

 

 

풀이 과정

처음엔 입출력 예시만 고려한 채로 아래와 같은 코드로 풀었습니다.

section 의 최댓값과 최솟값의 차에 대해서 m과 들어맞는지 확인하고 결과물을 출력하는 방식이지요. 

def solution(n, m, section):
    answer = 0
    i = section[len(section)-1] - section[0] + 1
    if i//m == 0:
        answer = 1
    else:
        if i%m == 0:
            answer = i//m
        else:
            answer = i//m+1
    return answer

 

하지만 채점 결과 정확성이 반밖에 되지 않더군요. 예외케이스가 너무 많았습니다. 

 

예제 3번에 대해 만약 section 이 [1, 2, 4] 일 겨우 제 코드로는 그대로 4가 출력되지만 실제 결과물은 3이 되어야 합니다. 

이처럼 예제 3번을 약간 변형해서 예외케이스를 기준으로 다시 생각을 해봅니다. 

 

 

n = 4, m = 1, section = [1, 2, 4] → result = 3               n = 5, m = 2, section = [1, 2, 4, 5] → result = 2

 

이미 칠해진 구간을 기주으로 section 을 나눠서 봐야 하는데요.

section 의 각 값 사이의 차가 m 보다 클 경우, 즉 section의 값 사이에 이미 칠해진 구간이 m보다 클 경우 그걸 건너뛰고 다시 덧칠해야 하는 원리입니다. 

결국 section의 최댓값만과 최솟값의 차이만 보는 대신, 각각의 값 사이의 차에 대해 m보다 작으면 넘어가고 m보다 크거나 같으면 앞에 넘어간 부분에 대해 1을 카운트해주고 그 뒤에 값들에 대해 다시 차를 계산해야 합니다. 이때 조건에서 덧칠이 필요한 부분 section의 길이는 무조건 1보다 크다는 명시가 있었기에 answer = 1 를 디폴트로 시작해야 합니다. 

 

최종 코드

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

 

다른 방식의 풀이도 살펴봤습니다.

def solution(n, m, section):
    answer = 0
    start = section[0]
    for i in section:
        if start <= i:
            start = i + m  # 어차피 안 칠해진 부분 section 첫번째부터 시작하는 거기 때문에 m 만큼 더하기
            answer += 1
    return answer

 

그리디 유형의 알고리즘을 푸는 방법인 거 같은데 어떤 것인지 좀 더 찾아봐야 할 것 같습니다. 

 

 

오랑우탄이 영어를 하고 오랑이가 코드마스터가 되는 그날까지~

 

 

 

프로그래머스