[프로그래머스] 프로그래머스 Level1 로또의 최고 순위와 최저 순위 C++ (데브매칭 코딩테스트)

문제

https://programmers.co.kr/learn/courses/30/lessons/77484

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

백트래킹이란 것은 바로 알아차렸지만 코드도 좀 더러워지고 구현하는데 애를 좀 먹었던 문제이다. 

풀이

백트래킹 + 구현 문제이다.

'0'인 로또 칸에 대해 갯수를 세고 이를 바탕으로 이미 나온 번호를 제외한 0 ~ 45의 번호들에 대해 조합을 구해주면 된다.

조합을 구한 후에는 정답 로또와 조합을 통해 맞은 로또 번호를 비교해주어 각각의 최대/최소 케이스를 구해주었다. 여기서 끝이 아니고 최대/최소 케이스에 원래 맞았던 갯수(origin)을 더해준 값을 바탕으로 등수를 계산하여 정답을 구해주면 된다.

또한 받은 로또의 모든 칸이 0이면 조합을 돌렸을때 무조건 최고 순위는 1등이고 최저 순위는 6등이므로 바로 1등과 6등을 리턴하게 해주거나 받은 로또가 정답 로또와 일치하면 1등과 1등을 바로 리턴해주어 계산 시간을 아낄 수 있다.

코드

#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int m = 0;
int big = -1;
int small = 7;
int origin = 0;
int arr[46];
int all[46];
bool isused[46];
bool checkUsed[46];
bool correctUsed[46];

void func(int cnt, int idx)
{
    int correctCnt = 0;

    if (cnt == m)
    {
        for (int i = 0; i < m; i++)
        {
            if (!checkUsed[arr[i]] && correctUsed[arr[i]])
            {
                correctCnt++;
            }
        }
        big = max(big, correctCnt);
        small = min(small, correctCnt);
        return;
    }

    for (int i = idx; i < 45; i++)
    {
        isused[i] = true;
        arr[cnt] = all[i];
        func(cnt + 1, i + 1);
        isused[i] = false;
    }
}

vector<int> solution(vector<int> lottos, vector<int> win_nums) {

    vector<int> answer;

    memset(isused, false, sizeof(isused));

    for (int i = 0; i < lottos.size(); i++)
    {
        for (int j = 0; j < lottos.size(); j++)
        {
            if (lottos[i] == win_nums[j])
            {
                origin++;
            }
        }
    }

    if (origin == 6)
    {
        answer.push_back(1);
        answer.push_back(1);
        return answer;
    }

    for (int i = 0; i < win_nums.size(); i++)
    {
        correctUsed[win_nums[i]] = true;
    }

    for (int i = 0; i < lottos.size(); i++)
    {
        if (lottos[i] == 0)
        {
            m++;
        }
        else
        {
            isused[lottos[i]] = true;
            checkUsed[lottos[i]] = true;
        }
    }

    if (m == 6)
    {
        answer.push_back(1);
        answer.push_back(6);
        return answer;
    }

    for (int i = 0; i < 45; i++)
    {
        all[i] = i + 1;
    }

    func(0, 0);

    big += origin;
    small += origin;

    switch (big)
    {
    case 6:
        answer.push_back(1);
        break;
    case 5:
        answer.push_back(2);
        break;
    case 4:
        answer.push_back(3);
        break;
    case 3:
        answer.push_back(4);
        break;
    case 2:
        answer.push_back(5);
        break;
    default:
        answer.push_back(6);
        break;
    }

    switch (small)
    {
    case 6:
        answer.push_back(1);
        break;
    case 5:
        answer.push_back(2);
        break;
    case 4:
        answer.push_back(3);
        break;
    case 3:
        answer.push_back(4);
        break;
    case 2:
        answer.push_back(5);
        break;
    default:
        answer.push_back(6);
        break;
    }

    return answer;
}