[기능개발 | 프로그래머스 스쿨 | 스택/큐 Lv2] 반례 찾기

tony·2024년 2월 24일
algorithmprogrammersstack/queue
0

코딩테스트-알고리즘

목록 보기
8/10

문제

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
progresses speeds return
[93, 30, 55][1, 30, 5] [2, 1][95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1][1, 3, 2]
입출력 예 설명
입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

※ 공지 - 2020년 7월 14일 테스트케이스가 추가되었습니다.

pseudo code

  1. 남은일수와 speeds 를 통해 필요한작업기간리스트 를 구한다.

  2. 이전값 플래그 (혹은 스택) 사용하여 다음 필요기간이 이전 필요기간보다 작거나 같은 경우를 카운트한다.

  3. 다음 필요기간이 이전 필요기간보다 큰 경우라면 answer 리스트에 추가한다.

  4. 모든 필요한작업기간리스트를 구했다면 종료한다.

접근 방향 자체는 올바른 방향이었다. 다만 접근하는 과정에 있어서 주의해야할 점이 있었다는 게 문제다.

무엇이 문제였는지 알아보자.

접근 1)

def solution(progresses, speeds):
    answer = []

    # 1
    leftProgresses = [(100 - p) // speeds[idx] for idx, p in enumerate(progresses)]

    leftPStack = [leftProgresses[0]]
    daysToDeploy = 0
    for idx,pr in enumerate(leftProgresses):
        # 2
        if(pr <= leftPStack[-1]):
            daysToDeploy += 1
        # 3
        else:
            answer.append(daysToDeploy)
            daysToDeploy = 1
    answer.append(daysToDeploy)
    
    # 4
    return answer
  1. 남은일수와 speeds 를 통해 필요한작업기간리스트 를 구한다.
  2. 이전값 플래그 (혹은 스택) 사용하여 다음 필요기간이 이전 필요기간보다 작거나 같은 경우를 카운트한다.
  3. 다음 필요기간이 이전 필요기간보다 큰 경우라면 answer 리스트에 추가한다.
    다만, 이 때 카운트값을 1로 초기화해준다.
  4. 모든 필요한작업기간리스트를 구했다면 종료한다.

주어진 예제 이외 케이스들은 모조리 실패하는 것을 볼 수 있었다.

무엇이 문제였을까?

개선 1) 새로운 배포일을 스택에 추가해주기

그렇다.

새로운 배포일을 찾을 때, 새로운 배포일을 스택에 추가하지 않은 것이다.

즉, 다음 필요기간이 이전 필요기간보다 큰 경우, 다음 필요기간에 대해 업데이트를 해주어야한다.

나는 이것을 해주지 않은 것이다.

그렇다면 개선된 코드를 살펴보자.

def solution(progresses, speeds):
    answer = []

    # 1
    leftProgresses = [(100 - p) // speeds[idx] for idx, p in enumerate(progresses)]

    leftPStack = [leftProgresses[0]]
    daysToDeploy = 0
    for idx,pr in enumerate(leftProgresses):
        # 2
        if(pr <= leftPStack[-1]):
            daysToDeploy += 1
        # 3
        else:
            answer.append(daysToDeploy)
            leftPStack.append(pr) # 코드 추가 : 새로운 배포일을 스택에 추가
            daysToDeploy = 1
    answer.append(daysToDeploy)
    
    # 4
    return answer

모든 게 완벽한 것 같다.

이제 정답을 살펴보자.

테스트 케이스 11이 통과하지 못 하는 것을 볼 수 있다!

왤까??

개선 2) 정수가 아닌 올림수로 필요한 기간 계산하기

힌트는 프로그래머스 질문 에서 얻을 수 있었다.

입력값 〉 [99, 96, 94], [1, 3, 4]
기댓값 〉 [1, 2]
실행 결과 〉 실행한 결괏값 [3]이 기댓값 [1,2]과 다릅니다.

작업진도가 99,96,94 이면 남은 일수는 1,4,6이다.

이를 speeds 인 1,3,4 로 나누어 필요한작업기간을 추출해야한다.

이 때, 두 번째 작업진도가 이슈이다.

4 작업진도에 대해 3 speed 라면 필요한 작업기간은 2일이다.

왜냐하면 작업진도 4에 대해서 하루에 3정도를 일하고 다음 날에도 일을 해야한다.

따라서 올림수로 계산이 되어야한다.

이에 따라 아래와 같이 코드를 변경했다.

import math
def solution(progresses, speeds):
    answer = []

    # 1
    leftProgresses = [math.ceil((100 - p) / speeds[idx]) for idx, p in enumerate(progresses)]
    # math 라이브러리를 통한 올림수 처리

    leftPStack = [leftProgresses[0]]
    daysToDeploy = 0
    for idx,pr in enumerate(leftProgresses):
        # 2
        if(pr <= leftPStack[-1]):
            daysToDeploy += 1
        # 3
        else:
            answer.append(daysToDeploy)
            leftPStack.append(pr)
            daysToDeploy = 1
    answer.append(daysToDeploy)
    
    # 4
    return answer

잘 통과되는 것을 볼 수 있었다.

다른 사람 풀이

아래는 나와 동일한 접근인데 따로 for문과 올림수를 쓰지 않고, 스택을 통한 비교로직 내에서 한 번에 처리하게끔 한 구현이다. C++ 코드이다.

#include <vector>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

100칸 짜리 리스트를 만들고 progrogress 와 speed를 통해 몇 일을 사용해야 배포를 할 수 있는지 카운트, 배포일 인덱스에 카운트를 삽입한다.

이후 filter를 사용한 stream 을 통해 카운트들에 대해 추출한다.

다만 이 접근법은 O(N^2) 이므로 효율보다는 기발하다고 말할 수 있겠다.

public int[] solution2(int[] progresses, int[] speeds) {
	int[] dayOfend = new int[100];
	int day = -1;

	for(int i = 0; i < progresses.length; i++) {
		while (progresses[i] + (day * speeds[i]) < 100) {
			day++;
		}
		dayOfend[day]++;
	}
	return Arrays.stream(dayOfend).filter(i -> i != 0).toArray();
}

Python 최고효율 코드는 납득이 되지 않는 풀이라서 참고용으로만 복붙해본다.(실제 시험장에서 이렇게 생각할 수 있을까?에 대해서 설득력이 떨어진다고 생각한다)

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

처음에 Q 배열은 빈 배열이므로 [-((p-100)//s),1]를 추가해준다. 이는 [개발하는데 걸리는 일수, 기능 갯수] 순서이다. 처음에는 당연히 기능의 개수는 1개일 수 밖에 없다.
이 작업이 끝나면 다음 p, s로 넘어가는데, 만약 이 p,s의 '개발하는데 걸리는 일수'가 Q 배열에 있는 가장 마지막의 배열의 '개발하는데 걸리는 일수' 보다 크다면, Q 배열에 단순히 이전 단계와 같이 추가해준다.
하지만 만약 이 p,s의 '개발하는데 걸리는 일수'가 Q 배열에 있는 가장 마지막의 배열의 '개발하는데 걸리는 일수' 보다 작다면, Q 배열에 있는 가장 마지막의 배열의 '기능 개수'에 1을 더해준다.
이것이 모두 끝나면 [q[1] for q in Q], 즉 '기능 개수'를 담은 배열을 출력해준다.

Python 에 대해 알게된 것

math 라이브러리를 통한 올림수(ceil)

import math

math.ceil(1.3) #2 
math.ceil(1.1) #2
math.ceil(1.7) #2

list comprehension 으로 for 문으로 list 정의

leftProgresses = []
for idx,p in progresses:
    leftProgresses.append((100 - p) // speeds[idx])

위 코드를 list comprehension 을 통해 한 줄로 변경할 수 있다.

leftProgresses = [math.ceil((100 - p) / speeds[idx]) for idx, p in enumerate(progresses)]

즉, list comprehension 을 사용하게 되면 다음과 같은 syntax 를 통해 활용될 수 있다. -- 이걸 쓰는 게 두 번째이다. ㅎㅎ

$변수명 = [ $i 에 대해 적용할비즈니스로직 for $i in $items ]
profile
tony
내 코드로 세상이 더 나은 방향으로 나아갈 수 있기를
이전 포스트

[같은 숫자는 싫어 | 프로그래머스 스쿨 | 스택/큐 Lv1] 두 가지 접근법

다음 포스트

4 steps to solve any dynamic programming

0개의 댓글