lv3 ) 숫자게임

https://school.programmers.co.kr/learn/courses/30/lessons/12987

프로그래머스

 

 

 

 

이중 loop 쓰면 O(n^2) 시간초과이기에, vector의 특징을 살려 풀었다. 

중요한 점은 

A: 1, 3, 4, 5, 6, 8

B:  2, 3, 4, 5, 6, 7

일때 동일한 idx 끼리 비교하면 안된다.

 

내풀이방법으론 마지막인덱스부터 시작해서 첫 인덱스 까지 가는 것인데 

B가 A보다 큰 값이 나올때 counting

그렇지 않을 경우 A를 pop 한다.

 

#include <string>
#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    //while 문
    //대상 B 인덱스 갯수까지
    int idx = B.size() - 1;
    while(!A.empty() && idx >= 0){
        if(A.back() < B[idx]){
            answer++;
            idx--;
        }
        A.pop_back();
    }
    return answer;
}

 

보아하니 for문에서 idx만 달리 줘도 되겠다.