[프로그래머스/python] 기능개발

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

문제 링크

---

프로그래머스

 

풀이과정

---

첫 번째코드(실패한 코드와 아이디어)

def solution(progresses, speeds):
    answer = []
    result = []
    # 각 pro의 값+각 speeds의 값>=100이 될 때 answer에 더한 횟수를 넣음(루프의 i)
    # answer만큼 루프돌면서 현재값>다음값이 될 때 현재값을 result에 넣음

    for i in range(len(progresses)):
        temp = progresses[i]
        for j in range(1, 101):
            temp += speeds[i]
            if temp >= 100:
                answer.append(j)
                break
    cnt=0
    #answer=[5,1,2,3]
    for i in range(len(answer)):
        cnt+=1
        if i==len(answer)-1:
            result.append(cnt)
            break
        if answer[i] < answer[i + 1]:
            result.append(cnt)
            cnt=0
    return result
#print(solution([93, 30, 55],[1,30,5]))
#print(solution([95, 90, 99, 99, 80, 99],[1,1,1,1,1,1]))
#print(solution([95,95,95,95],[4,3,2,1]))
# 2 2 3 5 -> 2 1 1

기본 테스트 케이스는 성공했는데 히든 테스트케이스를 다 실패해서 한참 헤맸는데 해결하고 나서 좀 허무했다. 

테케가 제대로 안 들어가길래 결국 IDE없이 푸는 것을 포기하고… 파이참 실행(이러면 안됨)

 

일단 아이디어는 이렇다.

기능의 진행 완료 상태를 담은 progresses 만큼 루프돌면서 speeds의 값을 한번씩 더해서 100이 될때까지 더한 뒤에 100이 되면 그 더한 횟수(작업 기간)를 answer 리스트에 넣는다.

그리고 answer만큼 루프돌면서 다음 값이 현재 값보다 더 크면 그때 현재값만큼 증가되었던 카운트수를 결과값 리스트에 넣어준 후, 카운트를 0으로 되돌린다.

근데 [5,1,2,3] 이 answer일 때처럼, answer[i]<answer[i+1] 이지만 answer[i-1]보다 작은 경우를 고려하지 않아서 테스트케이스에 전부 실패했다.

그래서 이를 고려하기 위해 temp에 먼저 answer[0] 값을 넣어준 후, 루프 돌면서 temp보다 큰 값이 나타나면 그때 카운트수를 결과값 리스트에 넣어주는 것으로 변경했다. 그리고 temp는 그 발견한 큰값으로 교체해주는 것이다.

참으로 간단한데 이걸 못 떠올려서… 삽질을 오래 하다니….

다시 푼 코드(성공한 코드)

def solution(progresses, speeds):
    answer = []
    result = []
    # 각 pro의 값+각 speeds의 값>=100이 될 때 answer에 더한 횟수를 넣음(루프의 i)
    # answer만큼 루프돌면서 현재값>다음값이 될 때 현재값을 result에 넣음

    for i in range(len(progresses)):
        temp = progresses[i]
        for j in range(1, 101):
            temp += speeds[i]
            if temp >= 100:
                answer.append(j)
                break
    cnt=0
    #answer=[5,1,2,3]
    temp = answer[0]
    for i in range(len(answer)):
        cnt+=1
        if i==len(answer)-1:
            result.append(cnt)
            break
        if temp<answer[i+1]:
            result.append(cnt)
            cnt=0
            temp=answer[i+1]
    return result

근데 다른 사람의 코드를 보면 굉장히 … 잘 풀었다.

일단 나는 answer리스트에 넣는 것부터 이중 반복문을 이용해서 횟수를 하나하나 세서 넣었다. 즉, 시간 복잡도가 O(N^2)이다.

그런데 O(N)으로 풀 수 있더라.

 

다른 사람의 코드

def solution(progresses, speeds):
    print(progresses)
    print(speeds)
    answer = []
    time = 0
    count = 0
    while len(progresses)> 0:
        if (progresses[0] + time*speeds[0]) >= 100:
            progresses.pop(0)
            speeds.pop(0)
            count += 1
        else:
            if count > 0:
                answer.append(count)
                count = 0
								time=0
            time += 1
    answer.append(count)
    return answer

다른 사람의 코드이다. (else문에 count=0과 time=0을 넣는 게 더 정확할 것 같아서 그 부분은 내가 추가함)

progresses의 리스트 원소들이 빌 때까지 반복하면서 개발진도가 100이 되지 않으면 time을 증가시킨다. 그러면 개발진도가 100이 되는 순간이 있을 거다… 그때 그 원소를 pop()해서 빼내준 후에 count 수를 증가시킨다.

그러면 그 다음번의 첫 번째 원소를 또 확인해주게 되는데… 그때, 이미 저장되어 있는 time만큼 또 곱하고 더해보면 개발진도가 100이 되는지 안되는지 알 수 있다. 100이 넘으면 걔도 기간 내에 개발할 수 있다는 거니까 카운트에 1을 증가시켜주고.

그러다보면 100이 안 넘는 순간이 올 것이다.

그때, answer리스트에 카운트를 넣어주고 time을 다시 0으로 초기화 시켜주면 된다.