프로그래머스 - 이중우선순위큐

 

프로그래머스

 

이번 문제는 우선순위큐의 문제로 Queue의 사용법과 간단한 string 활용법을 묻는 질문이다.

 

Queue는 선입선출의 형식으로 Pop 와 Peak등을 통해서 순서를 유지하며 조정하는 경우 List 보다 가벼운 계산 속도를 보여주기에 특정상황에서 쓰인다.

이번 문제는 중간중간 들어오는 값을 순서에 맞춰서 배열해주면 되는 방식으로

단순히 for문이나 List를 쓰게된다면 중복해서 확인해야하는 이중 for문 구조로 밖에 풀리지 않아서 Queue를 활용해야했다.

 

 

 

 

---

 

 

 

아래는 실제 풀이이다.

public int[] solution(string[] operations)
{
    int[] answer = new int[] { };
    Queue<int> heaps = new Queue<int>(); // 내림차순 정렬

    for (int i = 0; i < operations.Length; i++)
    {
        switch (operations[i])
        {
            case "D 1":
                if(heaps.Count > 0)
                    heaps.Dequeue();
                break;
            case "D -1":
                if(heaps.Count > 0)
                {
                    Queue<int> temps = new Queue<int>();
                    while (heaps.Count > 1)
                        temps.Enqueue(heaps.Dequeue());
                    heaps.Dequeue();
                    heaps = temps;
                }
                break;
            default: // "I 숫자"
                int num = int.Parse(operations[i].Split(' ')[1]);
                Queue<int> temp = new Queue<int>();

                if (heaps.Count == 0)
                    heaps.Enqueue(num);
                else if (heaps.Peek() <= num)
                { 
                    temp.Clear();

                    temp.Enqueue(num);
                    while (heaps.Count > 0)
                        temp.Enqueue(heaps.Dequeue());  
                    heaps = temp;
                }
                else
                {
                    temp.Clear();

                    while (heaps.Count > 0 && heaps.Peek() >= num)
                        temp.Enqueue(heaps.Dequeue());

                    temp.Enqueue(num);

                    while (heaps.Count > 0)
                        temp.Enqueue(heaps.Dequeue());

                    heaps = temp;
                }

                break;
        }
    }
    if (heaps.Count == 0) return new int[] { 0, 0 };
    if (heaps.Count == 1) return new int[] { heaps.Peek(), heaps.Peek() };
    return new int[] { heaps.Peek(), heaps.Last() };
}

For문을 돌리며 적절한 타이밍에 while로 전체를 돌며 선입선출로 한번 다 빼줫다가 넣어주는 방식을 사용하였으나.

이러한 구조는 만약 n의 크기가 커지면 시간 초과가 뜰 가능성이 높은 구조라고 생각한다.

 

 

 

만약 문제가 Queue의 이해능력을 묻는 문제가 아니였다면 Dictionary 구조로 접근해서
dict.Keys.First();
dict.Keys.Last();

로 문제를 풀면 깔끔하고 시간 복잡도도 적게 나올것 같다.

 

 

 

---

 

최근 공채시즌의 시작과 함께 과제와 면접을 많이 진행하면서 코테공부를 소홀하게 한것 같다.

다시 개인 공부와 함께 코테 공부도 화이팅 하자.