[C++로 풀이] 숫자 게임⭐⭐⭐

📌 숫자 게임

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int index = 0; 
    for(int i = 0; i < B.size(); ++i){
        if (B[i] > A[index]){
            answer++;
            index++;
        }
    }
            
    return answer;
}

🔥 시간 복잡도 차원에서

이 문제는 절대 \(O(N^2)\) 이 되어선 안된다. A와 B의 길이가 100,000이기 때문이다. 그래서 A 와 B 의 모든 원소를 서로서로 비교하면서 승점을 계산해선 안된다.

🔥 설명

1. A와 B를 오름 차순 정렬한다.
2. B 를 순회하면서
   • index에 “가장 최근에 B가 이겼던 A의 원소의 인덱스”를 저장한다.
   • B[i]가 A[index] 보다 크면 승점을 올린다.

굳이 B 의 원소마다 A 를 순회할 필요가 없다. 둘 다 오름차순 시켜놓고 이길 수 있는 후보들 중에 선택하고 소모시켜나가면 된다. 그 후보에서 가장 작은 원소가 A[index] 이기 떄문에 이거랑만 B원소를 비교하면된다. 결론적으로 O(N) 시간 복잡도으로 구현 충분함!!

B 👉 3 6 9 10 11 16 18
A 👉 1 2 2 11 13 15 20

정렬 후 위와 같은 모습이 되었다면

• index = 0
  • B[0] = 3 > A[0] = 1 👉 승점 = 1
    • 3 은 1,2,2 를 상대로 이길 수 있다. (여기서 1을 이기는데 3이 사용 되었으므로 이제 A[1]과 비교해야 됨)
• index = 1
  • B[1] = 6 > A[1] = 2 👉 승점 = 2
    • 6 은 2,2 를 상대로 이길 수 있다. (여기서 2을 이기는데 6이 사용 되었으므로 이제 A[2]과 비교해야 됨)
• index = 2
  • B[2] = 9 > A[2] = 2 👉 승점 = 3
    • 9 은 2 를 상대로 이길 수 있다. (여기서 2을 이기는데 9가 사용 되었으므로 이제 A[3]과 비교해야 됨)
• index = 3
  • B[3] = 10 < A[3] = 11
    • 10 은 11 를 상대로 이길 수 없다. (10은 1,2,2 를 이길 수 있지만 1,2,2 를 3,6,9 가 모두 사용해서 10이 이길 수 있는게 없음!)
  • B[4] = 11 == A[3] = 11
    • 11 은 11 를 상대로 이길 수 없다. (11은 1,2,2 를 이길 수 있지만 1,2,2 를 3,6,9 가 모두 사용해서 11이 이길 수 있는게 없음!)
  • B[5] = 16 > A[3] = 11 👉 승점 = 4
    • 16 은 11 를 상대로 이길 수 있다. (여기서 11을 이기는데 16이 사용 되었으므로 이제 A[4]과 비교해야 됨)
• index = 4
  • B[6] = 18 > A[4] = 13 👉 승점 = 5
    • 18 은 13 를 상대로 이길 수 있다. (B 순회 완료!)

따라서 위의 예시 같은 경우엔 B 가 A 를 최대 5 번 이길 수 있다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기