Lv1_[로또의 최고 순위와 최저 순위, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

이번 문제의 풀어야 할 점은 "일치하는 숫자가 몇개"인지 입니다.
일치하는 숫자는 당연하게 최저 순위가 될 것입니다.
그러면 최고 순위는 (일치하는 숫자 + 낙서로 가려진 숫자의 개수)가 됩니다.

문제 해결방법은 찾았으니 얼마나 효율적으로 찾아낼 수 있느냐만 남아있다.

두 개의 벡터를 비교하는 방법 고민해보면
 1) 이중 반복문으로 비교
 2) 벡터 정렬 후 index를 가지고 비교 (Lv1. 숫자 짝꿍에서 사용했던 방식; https://workingdog.tistory.com/38)
 3) set을 활용해서 중복인 요소 찾아내기 (삽입 연산 insert)

위의 3가지 시간복잡도를 살펴보면
 1) O(n*n)  (이중 반복문)
 2) O(nlogn + n) (sort + 반복문)
 3) O(n) (불균형 트리 삽입)
으로 볼 수가 있는데 문제에서 주어진 벡터는 사이즈 6으로 작기 때문에 큰 시간차는 없을 것으로 판단됩니다.

그래도 효율적으로 구성하는게 후에 유지보수를 위해는 더 좋죠

1) vector<int> win_nums에는 로또 당첨 번호로 중복된 값이 존재하지 않기 때문에 우선적으로 set<int> s에 삽입해줌.
    (vector<int> lottos에는 중복 값 '0'이 존재할 수 있음)
2) 먼저 set에 삽입된 win_nums와 lottos를 비교하며 중복된 값과 '0'의 값의 개수를 추출하면 완료.

 

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
vector<int> solution(vector<int> lottos, vector<int> win_nums) {
    vector<int> answer;
 
    // 1) 일치하는 숫자 찾기
    // 2) 0의 개수 찾기
    // 3) (일치하는 개수 == 최저 순위), (최저 순의 + 0의 개수 = 최고 순위)
    int count_0 = 0;
    int count_etc = 0;
    vector<int> score = { 6, 6, 5, 4, 3, 2, 1 };
    set<int> s(win_nums.begin(), win_nums.end());
 
    for (auto item : lottos) {
        if(item == 0) {
            count_0++;
        } else {
            auto ret = s.insert(item);
            if(ret.second == false) {
                // 중복
                count_etc++;
            }
        }
    }
 
    answer.push_back(score[count_etc + count_0]);
    answer.push_back(score[count_etc]);
 
    return answer;
}

속도는 아주 좋다

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓