[프로그래머스] 숫자 게임

숫자 게임(https://programmers.co.kr/learn/courses/30/lessons/12987)

---

1. 이해하기

• 숫자가 큰 쪽이 승리하게 된다.
• A팀의 출전 순서가 정해져 있을 때, B팀의 최대 승점.
• 큐를 이용하여 구한다.

---

2. 구현하기

• 이 문제를 푸는 아이디어는 다음과 같다.

  • B에 있는 가장 작은 수부터 A의 가장 작은 수와 비교를 한다.
  • 만약 B의 수가 A의 수보다 크면 answer++를 하고 두 수를 큐에서 지운다.
  • 만약 B의 수가 A의 수보다 작다면 B의 수만 큐에서 지운다.

• Python

  from collections import deque
  
  def solution(A, B):
      answer = 0
      A.sort()
      B.sort()
      aQ = deque()
      bQ = deque()
      for i in range(len(A)):
          aQ.append(A[i])
          bQ.append(B[i])
      while len(bQ) != 0:
          a,b = aQ.popleft(), bQ.popleft()
          if a < b:
              answer+=1
          else:
              aQ.appendleft(a)
      return answer

• C++

  #include <string>
  #include <vector>
  #include <algorithm>
  #include <queue>
  
  using namespace std;
  
  int solution(vector<int> A, vector<int> B) {
      int answer = 0;
  
      sort(A.begin(), A.end());
      sort(B.begin(), B.end());
      queue<int> aQ, bQ;
      for(int i = 0; i < A.size(); i++) {
          aQ.push(A[i]);
          bQ.push(B[i]);
      }
      while(!bQ.empty()) {
          if(bQ.front() > aQ.front()) {
              bQ.pop();
              aQ.pop();
              answer++;
          } else {
              bQ.pop();
          }
      }
  
      return answer;
  }

---

3. 배운점

• python에서 제공되는 기본 리스트로도 큐 구현이 가능하다. 하지만 리스트를 사용하면 collections의 deque를 이용해서 구하는 것보다 시간이 오래걸린다. 실제로 프로그래머스에서 구현을 해본 결과 효율성 테스트에서 40배가 차이가 났다.
• python에서 deque를 사용하려면 from collections import deque를 이용해서 사용할 수 있다.
• python에서 deque 사용법
  • pop(): deque의 오른쪽 원소를 가져오면서 지운다.
  • popleft(): 왼쪽 원소
  • append(): 오른쪽에 추가.
  • appendleft(): 왼쪽에 추가.
• python에서 deque는 empty()가 없다. 그 대신에 큐가 비어있으면 False가 되므로 이를 이용하자.