[코딩테스트] Programmers - 기능개발 (실패)

 

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

프로그래머스

 

 

풀이

"뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다" 

앞에 것이 먼저 빠지는 것이니 이 문제는 큐로 풀면 된다. 

 

 

코드1 - 오답

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] progresses, int[] speeds)
    {
        List<int> answer = new List<int>();

        Queue<int> queue = new Queue<int>();
        foreach (int progress in progresses)
            queue.Enqueue(progress);

        int length = 0;
        int count = 0;
        for (int i = 0; i < speeds.Length; i++)
        {
            int target = queue.Dequeue();
            int speed = speeds[i];

            bool isExist = (100 - target) % speed > 0 ? true : false;
            int addNum = 0;
            if (isExist)
            {
                addNum = 1;
            }
            if (i != 0 && (100 - target) / speed + addNum < length)
            {
                count++;
                continue;
            }
            else if(i != 0 && (100 - target) / speed + addNum >= length)
            {
                answer.Add(count);
                count = 0;
            }

            count++;
            length = (100 - target) / speed;
        }
        answer.Add(count);

        return answer.ToArray();
    }
}

 

테스트케이스 1, 2, 4, 5에서 실패가 나왔다. 

 

 

코드2 - 정답

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] progresses, int[] speeds)
    {
         List<int> answer = new List<int>();

         int n = progresses.Length;
         int[] days = new int[n];

         for (int i = 0; i<n; i++)
         {
             int remain = 100 - progresses[i];
             days[i] = (remain + speeds[i] - 1) / speeds[i];
         }

         int count = 1;
         int curReleaseDay = days[0];
         for (int i = 1; i< n; i++)
         {
             if (curReleaseDay >= days[i])
             {
                 count++;
             }
             else
             {
                 answer.Add(count);
                 curReleaseDay = days[i];
                 count = 1;
             }
         }

         answer.Add(count);

         return answer.ToArray();
    }
}

 

풀이 시간이 오래 걸려서 다른 사람 코드를 그대로 가져와서 일단 통과만 시켰다. 

이 문제는 기록해뒀다가 다음에 다시 풀어야 겠다. 

 

cf)

[프로그래머스 C#] 기능개발

 

 

복습1 풀이 (6/10)

[문제]
기능 개선 작업 진행 중이다. 
각 기능은 진도가 100% 일 때 서비스에 반영한다. 

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

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses,
각 작업의 개발 속도가 적힌 정수 배열 speeds 주어진다. 

각 배포마다 몇 개의 기능이 배포되는지 return 

[입력]
- 작업 진도 정수 배열 progresse
- 작업 개발 속도 정수 배열 speeds 

[출력]
- 각 배포마다 몇 개의 기능이 배포되는지 return 

[제한 사항]
- 0 <= 작업 개수(progressed, speeds 길이) <= 100 
- 0 <= 작업 진도 < 100 
- 0 <= 작업 속도 <= 100
- 배포는 하루에 한 번만 가능 
- 하루의 끝에 배포된다. 

 

[풀이]

progresses[i]의 소요 기간을 구한다.

progresses[i]의 소요 기간이 앞선 기간보다 작거나 같으면, 앞선 기간에 배포되어야 한다. 

그 기간에 배포되어야 하는 프로세스 개수를 카운팅한다. 

 

progresses[i]의 소요 기간이 앞선 기간보다 크면, 앞선 기간에 처리해야 할 프로세스들 개수를 배열에 저장하고, 카운팅 변수는 1로 만든다. 

 

위 과정을 작업 개수(progresses, speeds 길이)만큼 해주면 된다. 

 

소요 기간은 공식화 해봤다. 

• (100 - progresses[i]) / speeds[i]의 나머지가 있는 경우
  • 소요 기간 = (100 - progresses[i]) / speeds[i] + 1 
• (100 - progresses[i]) / speeds[i]의 나머지가 없는 경우
  • 소요 기간 = (100 - progresses[i]) / speeds[i] 

 

이 풀이의 시간 복잡도는 선형 시간(O(N))이다.

N은 작업 개수이고, 작업 개수는 최대 100이다. 1초 내로 충분히 풀린다. 이 풀이로 코드를 짜보자. 

 

 

코드 1 - 정답

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] progresses, int[] speeds) 
    {
        List<int> answer = new List<int>();
        int max = -1; 
        int count = 0; 
        for(int i = 0; i < progresses.Length; i++)
        {
            // progresses[i] 완료하는 소요 기간 
            int day = (100 - progresses[i]) % speeds[i] != 0 ? (100 - progresses[i]) / speeds[i] + 1 : (100 - progresses[i]) / speeds[i];
            
            if(i == 0)
            {
                count++;
                max = day;
            }
            else
            {
                if(day <= max)
                    count++;
                else
                {
                    answer.Add(count);
                    count = 1; 
                    max = day;
                }
            }
        }
        
        answer.Add(count);
        
        return answer.ToArray();
    }
}