[프로그래머스] 기능개발: math.ceil 대체 수식

문제

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

프로그래머스

 

 

풀이1

def solution(progresses, speeds):
    answer = []
    days_left = [(100 - progresses[i] + speeds[i] -1) // speeds[i] for i in range(len(progresses))]
   
    day = days_left[0]
    cnt = 1
    
    for d in days_left[1:]: 
        if d <= day:
            cnt += 1
        else:
            answer.append(cnt)
            day = d
            cnt = 1
    
    answer.append(cnt)
    return answer

 

시간복잡도는 days_left 구할때 O(n), for문에서 O(n)

-> O(n)

zip을 이용해서 progresses랑 speeds를 한번에 돌면서 하고싶었는데

어떻게할지 모르겠음+문제 조건에서 리스트 길이가 100 이하래서

그냥 새로운 리스트 days_left를 따로 만들어서 풀었다

다른풀이1

from math import ceil

def solution(progresses, speeds):
    answer = []
    max_duration = ceil((100 - progresses[0]) / speeds[0])
    count = 0
    
    for progress, speed in zip(progresses, speeds):
        duration = ceil((100 - progress) / speed)
        # duration = -(-(100 - progress) // speed)
        if max_duration < duration:
            answer.append(count)
            count = 0
            max_duration = duration
        count += 1
    
    if count > 0:
        answer.append(count)
    
    return answer

 

처음에 풀려던 의도대로 해결한 풀이법

다른풀이2

def solution(progresses, speeds):
    Q = []
    for p, s in zip(progresses, speeds):
        days_left = (100 - p + s - 1) // s  # 남은 일수 계산 (올림 효과)
        if not Q or Q[-1][0] < days_left:
            Q.append([days_left, 1])  # 새로운 배포 그룹 시작
        else:
            Q[-1][1] += 1  # 같은 배포 그룹에 포함
    return [q[1] for q in Q]

 

zip() 이용한 풀이

2차원리스트 활용

비교: 이전 코드와의 차이점

1. 첫 번째 코드 (기존 코드):
   • 각 작업이 완료될 일수를 계산한 후, 다시 한 번 순회하여 배포 가능한 작업들을 그룹화합니다.
   • 시간 복잡도는 O(n)입니다.
2. 두 번째 코드 (새 코드):
   • zip을 이용해 한 번의 순회만으로 남은 일수 계산과 그룹화를 동시에 처리합니다.
   • 시간 복잡도는 O(n)입니다.

어떤 코드가 더 나은가?

• 가독성: 첫 번째 코드는 각 단계를 명확히 나눠서 처리합니다. 첫 번째 코드는 각 작업의 완료 일수를 먼저 계산하고, 그 이후에 배포 가능 여부를 판단하는 구조라서 이해하기 쉽습니다. 반면, 두 번째 코드는 한 번의 루프에서 모든 것을 처리하기 때문에 다소 복잡하게 느껴질 수 있습니다.
• 성능: 두 코드는 모두 시간 복잡도가 O(n)으로 동일하므로, 입력 크기 n에 따른 성능 차이는 크지 않습니다. 하지만 두 번째 코드는 그룹화를 계산하는 과정을 반복해서 처리하지 않고, 한 번의 루프에서 모든 것을 해결하므로 약간 더 효율적입니다.

결론

• 첫 번째 코드는 가독성이 좋고, 직관적으로 단계별로 문제를 해결하는 방식입니다.
• 두 번째 코드는 한 번의 루프에서 작업을 처리하므로, 효율성이 조금 더 뛰어납니다. 단, 가독성 측면에서 약간 불리할 수 있습니다.

따라서, 두 번째 코드가 미세하게 더 효율적일 수 있지만, 코드의 명확성과 유지보수성을 고려하면 프로젝트 상황에 따라 두 코드 중 선택할 수 있습니다.

 

math.ceil

원래 math.ceil()함수를 사용해서 풀었는데 챗지피티가 다른 방법을 알려주었다

# import math
# math.ceil((x - p) / s)

# 대신 아래 식으로 쓸 수 있다

(x - p + s - 1) // s

 

• 함수 호출 비용: math.ceil은 Python에서 함수를 호출하는 것이므로, 함수 호출에 대한 오버헤드가 발생합니다. 이 오버헤드는 특히 반복문 안에서 호출할 경우 성능에 영향을 미칠 수 있습니다.
• 산술 연산: 반면, (x - p + s - 1) // s는 단순한 산술 연산이므로, 계산이 더 빠르게 수행됩니다. 이 방식은 일반적으로 상수 시간 O(1)로 처리됩니다.

 

또 -((p - 100) // s)로 푸는 방법도 있었는데 가독성과 미미한 성능의 차이에서 모두(x-p+s-1)//s가 낫다고 한다.