알고리즘 문제 풀이(프로그래머스 - 두 큐 합 같게 만들기)

프로그래머스 LEVEL 2(두 큐 합 같게 만들기)

• 사용 언어 : javascript

• 해결 날짜 : 2022-08-19

• 해결 방법 :

  • O(1) 시간에 insert, remove 할 수 있도록 Queue()를 구현
  • q1 원소의 합 > q2 원소의 합이면 q2에서 pop()하여 q1에 push()
  • q1 원소의 합 < q2 원소의 합이면 q1에서 pop()하여 q2에 push()
  • 반복 횟수가 length * 4와 같아지면 전체를 다 돌고도 정답을 찾지 못한 것이므로 -1을 반환
• 회고 :
  • 처음에 시간 복잡도 생각하지 않고 2중 for문으로 해결하려 함
  • 최대 반복 횟수를 length * 2로 잘못 생각함

• 코드

  class Node {
              constructor(data) {
              this.data = data;
              this.next = null;
          }
      }
  
      class Queue {
          constructor() {
              this.front = null;
              this.rear = null;
              this.sum = 0;
          }
  
          isEmpty() {
              return this.front === null && this.rear === null;
          }
                  
          insert(data) {
              const newNode = new Node(data);
              if (this.isEmpty()) this.front = newNode;
              else this.rear.next = newNode;
              this.rear = newNode;
              this.sum += data;
          }
  
          remove() {
              if (this.isEmpty()) return;
              var front_data = this.front.data;
              this.sum -= front_data;
              this.front = this.front.next;
              if (!this.front) this.rear = null;
              return front_data;
          }
      }
  
      function solution(queue1, queue2) {
          var count = 0;
          const q1 = new Queue();
          const q2 = new Queue();
              
          for (var i = 0; i < queue1.length; i++) {
              q1.insert(queue1[i]);
              q2.insert(queue2[i]);
          }
              
          do {
              if (count >= queue1.length * 4) {
                  count = -1;
                  break;
              }
              if (q1.sum > q2.sum) {
                  q2.insert(q1.remove());
                  count++;
              } else if (q1.sum < q2.sum) {
                  q1.insert(q2.remove());
                  count++;
              } else {
                  break;
              }
          } while(true);
              
          return count;
      }
  
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges