20240123_기능개발(프로그래머스)_큐 이용

오늘의 TIL은 어제 풀이하여 TIL로 작성했던 '기능개발'의 큐를 이용한 문제 풀이이다.

 

문제 링크

 

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

프로그래머스

 

문제의 내용을 설명하면(어제랑 같은 부분)

 

int[] progresses로 주어지는 배열에 현재 프로그램의 개발 진도가 주어지고

int[] speeds로 주어지는 배열에 인덱에 해당하는 프로그램의 개발 속도가 주어진다.

각 개발은 병렬로 이뤄지고, 배포는 앞의 기능이 배포될 때 함께 배포된다.

배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이뤄진다.

예를 들어서 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어진다.

 

이 경우에 각 배포마다 몇 개의 기능이 배포되는지를 return하시오.

 

 

하루에 배열 progresses에 있는 숫자들에 각 인덱스에 매칭되는 speeds의 숫자들이 더해지는 것인데,

이 때, 작업의 개발 진도가 100이상이 되면 배포를 하게된다.

단, 배포는 이전에 있는 작업이 배포되거나 배포된 상태에서만 배포할 수 있게된다.

예를 들어서 아래와 같이 progresses가 주어진 경우에

하루가 지나면 progresses는 {94, 60, 60}로

이틀이 지나면 {95, 90, 65}로, 3일이 지나면 {96, 120(개발 완료), 70}이 되지만,

첫 번째 기능이 개발이 안됬기 때문에 첫 번째 개발이 완료되는 순간 같이 배포되게 된다.

7일이 지나면 {100(개발 완료), 120(개발 완료), 90} 이 되므로

7일째에 2개를 배포하고 9일째에 마지막 기능이 완료되어 배포하게 된다.

int[] progresses = {93, 30, 55};
int[] speeds = {1, 30, 5};

 

 

이 문제의 분류에 스택/큐가 달려있지만,

정해진 시간 내에 아이디어가 떠오르지 않아서 어제는 큐를 사용하지 않고 리스트를 사용하여 풀이했는데

이 문제를 시간을 두고 큐로 문제를 풀이하기로 해서 추가로 TIL로 작성하게되었다.

 

우선 문제를 푸는 아이디어는 어제 풀이했던 부분과 같은데,

우선 배포까지 걸리는 소요 일수를 만들고

이후에 현재 가장 앞에 있는 기능이 배포 가능한 경우에

그 뒤에 있는 기능들이 배포 가능한지 확인하게 만들 것이다.

다만 이 과정에서 List를 사용했던 것 대신, Queue를 사용하고

그 결과들이 차이가 있는지 비교할 것이다.

 

전체 코드를 작성하면 아래와 같다.

static void Main(string[] args)
{
    int[] progresses = { 93, 30, 55 };
    int[] speeds = { 1, 30, 5 };

    int[] result = new int[] { };

    result = Develop(progresses, speeds);

    return result;
}

static public int[] Develop(int[] progresses, int[] speeds)
{
    Queue<int> queue = new Queue<int>();
    List<int> costTime = new List<int>();

    for (int i = 0; i < progresses.Length; i++)
    {
        int cnt = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
        queue.Enqueue(cnt);
    }

    while (queue.Count > 0)
    {
        int cnt = 1;
        int costDay = queue.Dequeue();

        while (queue.Count > 0 && queue.Peek() <= costDay)
        {
            cnt++;
            queue.Dequeue();
        }

        costTime.Add(cnt);
    }

    return costTime.ToArray();
}

 

어제와 달라지는 부분은 Comp였던 리스트가 Queue인 큐로 바뀐 부분인데,

List<int> Comp = new List<int>();

for (int i = 0; i < progresses.Length; i++)
{
    int days = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
    Comp.Add(days);
}


//

Queue<int> queue = new Queue<int>();

for (int i = 0; i < progresses.Length; i++)
{
    int cnt = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
    queue.Enqueue(cnt);
}

 

위와 같이 같은 방식으로 필요한 값을 구하지만

List의 경우에는 Add를 사용했던 부분은 Queue의 경우에는 Enqueue를 사용했고

 

int curDay = Comp[0];
Comp.RemoveAt(0);
int cost = 1;

while (Comp.Count > 0 && Comp[0] <= curDay)
{
    cost++;
    Comp.RemoveAt(0);
}

costTime.Add(cost);

//

int cnt = 1;
int costDay = queue.Dequeue();

while (queue.Count > 0 && queue.Peek() <= costDay)
{
    cnt++;
    queue.Dequeue();
}

costTime.Add(cnt);

 

while문의 안에서

 

리스트의 경우에는 우선 개발되어야되는 기능이 개발된 날을 curDay로 하여 지정해주고, 리스트에서 제거했는데,

Queue에서는 costDay를 사용하고 Dequeue()를 이용하여 바로 지정하면서 빼주었다.

 

while문의 while문의 조건은

리스트나 큐에 데이터가 남아있고, 리스트에서는 curDay와 남아있는 리스트의 첫 원소를 비교했지만,

큐에서는 현재 큐의 데이터를 Peek()을 이용하여 첫 원소를 확인했다.

 

while문의 while문 안에서는 같은 방식이지만,

리스트의 경우에는 가장 처음의 데이터를 제거하므로 RemoveAt(0)을 사용했지만

큐의 경우에는 Dequeue()를 사용한 차이가 있다.

 

 

전체적으로 리스트와 큐를 비교하면 코드의 내용은 비슷하지만 사용하는 함수가 차이가 있고,

데이터를 처리하는 부분에서 리스트의 경우에는 RemoveAt(0)으로 처음의 데이터를 삭제했지만,

큐의 경우에는 Dequeue()를 사용한 것이 큰 차이인데,

리스트의 RemoveAt(0)의 경우에는 첫 데이터를 삭제하고 각 데이터들의 인덱스를 하나씩 줄이는 과정이 필요한데,

Dequeue()의 경우에는 각 데이터들의 인덱스의 이동이 없는 것이 차이점이다.

다시 말해서, 큐의 경우에는 각 데이터들의 인덱스가 없고 이 데이터들의 연결구조만이 존재하기 때문에

첫 데이터가 사라지더라도 나머지 데이터들의 연결구조에 영향을 주는 부분은 두 번째 데이터만이므로

데이터를 삭제하는 부분에서의 처리 데이터의 양이 차이가 나는 것이 둘의 차이점이다.

 

 

마지막으로 리스트와 큐의 결과를 비교하면 아래와 같은데

좌측이 리스트, 우측이 큐를 사용한 테스트의 결과

 

예상한 결과는 리스트 부분이 RemoveAt(0)의 함수로 인하여 좀 더 시간이 오래 걸릴 것으로 예상되었으나

오히려 리스트가 빠르고 큐가 오래 걸리는 것을 확인할 수 있었다.

 

이를 확인해보니 이 문제의 제한 조건이

작업의 개수(progresses, speeds의 배열의 길이)가 100개 이하인 경우로,

데이터의 양이 적기 때문에 Queue의 성능의 이점이 두드러지지 않을 수 있다고 확인하였다.

 

다만 데이터의 양이 많아지는 경우에는 이 둘의 성능차이가 크게 나타날 수 있다고 확인하였는데,

수작업으로 데이터의 양을 늘려도 유의미한 차이를 확인하지는 못했다.

 

이 부분에 대해서는 내일 튜터님께 질문한 후에 정리하여 추가할 예정이다.

 

 

## 20240125  이 둘의 성능의 차이에 대한 내용 추가

List에서 RemoveAt(0)이 원래 시간을 많이 사용하는 부분은 맞지만,

100개의 데이터를 처리하기 때문에 이는 속도에 영향을 미치지 않을 수준이다.

(속도에 영향을 주려면 데이터의 양이 훨씬 많아야 한다. 10만 이상의 데이터라면 유의미한 차이가 나올 수 있다)

 

Queue는 C#에서 순환배열로 구현되어 있다.(Linked List가 아님)

 

0.2ms는 테스트 결과에서 차이가 나는 것처럼 보이지만,

실제로는 매우 작은 차이이므로 둘의 차이는 거의 없다고 봐도 무방하다.

이 차이가 나는 부분을 유추해보면,

Queue에서 내부에 구현된 부분(Enqueue, Dequeue)이 List보다 좀 더 복잡한데,

 

Enqueue와 Dequeue의 경우에는 아래와 같이

public void Enqueue(T item) {
    if (_size == _array.Length) {
        int newcapacity = (int)((long)_array.Length * (long)_GrowFactor / 100);
        if (newcapacity < _array.Length + _MinimumGrow) {
            newcapacity = _array.Length + _MinimumGrow;
        }
        SetCapacity(newcapacity);
    }

    _array[_tail] = item;
    _tail = (_tail + 1) % _array.Length;
    _size++;
    _version++;
}


public T Dequeue() {
    if (_size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

    T removed = _array[_head];
    _array[_head] = default(T);
    _head = (_head + 1) % _array.Length;
    _size--;
    _version++;
    return removed;
}

 

Queue에 데이터를 추가하고 빼는 과정에서 head, tail, size가 변수로 작동하게 되는데,

 

 

List의 경우(ArrayList)에는 아래와 같이

public override int Add(Object obj) {
    int i = _list.Add(obj);
    _version++;
    return i;
}

public virtual void RemoveAt(int index) {
    if (index < 0 || index >= _size) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
    Contract.Ensures(Count >= 0);
    //Contract.Ensures(Count == Contract.OldValue(Count) - 1);
    Contract.EndContractBlock();

    _size--;
    if (index < _size) {
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    _items[_size] = null;
    _version++;
}

 

데이터를 추가하는 과정에서는 변수가 특별히 없지만

RemoveAt에서 Array.Copy를 사용하게 되므로 이 부분에서 성능에 영향을 줄 수 있다.

 

 

즉, 이 데이터들로 유추하면, Queue의 경우 Enqueue와 Dequeue 부분이 기본적으로 사용하는 변수가 많기 때문에

데이터의 양과 관계 없이 기본적으로 사용하게되는 시간이 존재하지만,

List(ArrayList)인 경우에는 기본적으로 사용하는 변수가 적어서 기본적으로 사용하게되는 시간이 적지만,

RemoveAt 함수에서 Array.Copy가 작동하므로, 데이터의 양이 많아지만 사용하는 시간이 많아진다

라고 유추할 수 있다.

 

따라서 이 문제에서 List가 더 빨랐던 이유는

Queue의 초기화에서 생기는 소요시간이 어느정도 있기 때문에

데이터가 적은 이번 문제에서는 이 소요시간이 데이터를 처리하는 시간보다 길게 잡혔기 때문이라고 할 수 있다.

또, 데이터의 양이 많아지면 List의 RemoveAt() 함수가 Array.Copy를 많이 해야되므로

Queue가 List보다 훨씬 빠르게 작동할 것을 예상할 수 있다.

 

아래는 튜터님의 도움으로 Queue와 ArrayList를 비교하는데 사용했던 닷넷 문서이다.

 

Queue

Reference Source

 

ArrayList

Reference Source