[프로그래머스] 로또의 최고 순위와 최저 순위

programmers.co.kr/learn/courses/30/lessons/77484?language=cpp

코딩테스트 연습 - 로또의 최고 순위와 최저 순위

---

 

-풀이-

1. 먼저 당첨 번호들을 저장해둘 map 또는 bool check[46] 을 만들어 준다.

2. 당첨 번호를 1번에 만들어둔 배열, 혹은 map에 저장해둔다.

ex) 당첨번호가 1,2,3,4,5,6이면, check[1]=check[2]=check[3]=check[4]=check[5]=check[6]= true 가 되도록

3. lottos를 돌면서, 먼저 0인지 확인하고 0이면 zero_cnt++; 를 해준다. 0이 아니라면, 당첨번호중 해당 번호가 있는지 확인 후 , 당첨번호라면 cnt++; 를 해준다.

4. 최고 순위는 지워진 0이 모두 당첨번호일 경우이고, 최저 순위는 지워진 0이 모두 당첨번호가 아닐경우이므로, 당첨번호의 개수가 cnt+zero_cnt인 경우의 순위와, cnt인 경우의 순위를 구한 뒤, answer에 push_back해주면된다.

 

-시간복잡도-

당첨번호를 저장하는 로직 O(1)

당첨번호인지 확인하는 로직 O(1)

당첨갯수를 순위로 변환하는 로직 O(1)

 

따라서 시간복잡도는 O(1)이 된다.

 

-코드-

C++

#include <string>
#include <vector>

using namespace std;

//순위변경 함수
int rating(int correct_cnt){
    switch(correct_cnt){
        case 6:
            return 1;
        case 5:
            return 2;
        case 4:
            return 3;
        case 3:
            return 4;
        case 2:
            return 5;
        default:
            return 6;
    }
}

vector<int> solution(vector<int> lottos, vector<int> win_nums) {
    vector<int> answer;
    bool check[46]={0};
    //당첨번호를 저장
    for(int i=0;i<win_nums.size();i++){
        int num=win_nums[i];
        check[num]=true;
    }
    int zero_cnt=0;
    int c_cnt=0;
    for(int i=0;i<lottos.size();i++){
        int num=lottos[i];
        if(!num){
            zero_cnt++;
        }
        else{
            if(check[num]){
                c_cnt++;
            }
        }
    }
    answer.push_back(rating(c_cnt+zero_cnt));//최고순위 저장
    answer.push_back(rating(c_cnt));//최저순위 저장
    return answer;
}

 

Java

class Solution {
    public int getRank(int ccount){
        switch(ccount){
            case 6:
                return 1;
            case 5:
                return 2;
            case 4:
                return 3;
            case 3:
                return 4;
            case 2:
                return 5;
            default:
                return 6;
        }
    }
    
    public int[] solution(int[] lottos, int[] win_nums) {
        // int[] answer = {};
        boolean[] correct=new boolean[46];
        int z_cnt=0,cor=0;
        for(int c:win_nums){
            correct[c]=true;
        }
        for(int l:lottos){
            if(l==0) z_cnt++;
            else{
                if(correct[l]) cor++;
            }
        }
        int[] answer={getRank(cor+z_cnt),getRank(cor)};
        
        return answer;
    }
}