[Javascript][Programmers] 카드 뭉치

 

문제

문제에는 다음과 같은 조건이 제시되어 있습니다.

• 카드 뭉치에서 카드를 순서대로 사용합니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

이러한 조건들을 고려해보면, 이 문제는 "선입선출(FIFO: First In, First Out)" 원칙을 따르고 있음을 알 수 있습니다. 이런 특성을 가장 잘 구현할 수 있는 자료구조는 큐(Queue)입니다. 

 

나의 풀이

• 시간복잡도: O(M) (cards의 길이: N, goal의 길이: M)

function solution(cards1, cards2, goal) {
    let index1 = 0;
    let index2 = 0;

    for (let goalIndex = 0; goalIndex < goal.length; goalIndex++) {
        if (index1 < cards1.length && goal[goalIndex] === cards1[index1]) {
            index1++;
        } else if (index2 < cards2.length && goal[goalIndex] === cards2[index2]) {
            index2++;
        } else {
            return "No";
        }
    }

    return "Yes";
}

 

다른 풀이

직접 큐를 구현하여 문제를 해결할 수도 있습니다.

• 시간복잡도: O(M)

class Queue {
  items = [];
  front = 0;
  rear = 0;

  // 생성자를 이용해 편하게 초기화
  constructor(array) {
    this.items = array;
    this.rear = array.length;
  }

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.items[this.front++];
  }

  first() {
    return this.items[this.front];
  }

  isEmpty() {
    return this.front === this.rear;
  }
}


function solution(cards1, cards2, goal) {
  // cards와 goal을 Queue로 변환
  cards1 = new Queue(cards1);
  cards2 = new Queue(cards2);
  goal = new Queue(goal);

  // ➊ goal의 문자열을 순차적으로 순회
  while (!goal.isEmpty()) {
    if (!cards1.isEmpty() && cards1.first() === goal.first()) { // ➋ card1의 front와 일치하는 경우
      cards1.pop();
      goal.pop();
    } else if (!cards2.isEmpty() && cards2.first() === goal.first()) { // ➌ card2의 front와 일치하는 경우
      cards2.pop();
      goal.pop();
    } else {
      break;
    }
  }

  return goal.isEmpty() ? "Yes" : "No"; // ➍ goal이 비었으면 “Yes” 아니면 “No”를 반환
}

---

Reference

코딩테스트 합격자되기: 자바스크립트 편