[프로그래머스 코딩테스트 고득점 Kit] - 완전 탐색

프로그래머스 코딩테스트 고득점 Kit - 완전 탐색

모의고사 - level1

문제

1번, 2번, 3번 수포자가 찍는 방식에서 일정 주기를 가지고 반복되는데, 이 주기를 찾아서 배열에 저장한다. 이 후, answers를 순회하며 정답과 1대 1비교를 통하여 각각의 수포자가 맞힌 문제의 개수를 계산하여 비교한다.

#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<vector<int>> v(3);
    v[0].assign({1,2,3,4,5});
    v[1].assign({2,1,2,3,2,4,2,5});
    v[2].assign({3,3,1,1,2,2,4,4,5,5});

    int scores[3] = {0, };
    for(int i=0; i<3; i++){
        int score = 0;
        for(int j=0; j<answers.size(); j++){
            int size = v[i].size();
            if(answers[j] == v[i][j % size])
                score++;
        }
        scores[i] = score;
    }

    int maxIdx = 0;
    for(int i=1; i<3; i++){
        if(scores[i] > scores[maxIdx])
            maxIdx = i;
    }
    for(int i=0; i<3; i++){
        if(scores[i] == scores[maxIdx])
            answer.push_back(i+1);
    }
    return answer;
}

소수 찾기 - level2

문제

해당 문자열에 존재하는 문자를 선택하여 줄 세우기를 한다고 가정하였을 때, 줄 세우기를 한 문자들을 int로 변환한 후 소수 판별을 통해 해를 구해도 문제가 없는 N의 범위를 가진다.

주어진 문자열의 모든 순열을 구한 다음 ($O(N!)$), $K(1\leq K \leq N)$개의 문자를 앞에서 선택한다.

next_permutation함수는 기본적으로 해당 배열이 내림차순이 될 때 까지, true를 반환한다는 것을 이용하여 구현한다면 아래와 같다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int solution(string numbers) {
    int answer = 0;
    // 만들 수 있는 모든 조합들을 저장
    map<int, bool> mp;
    vector<int> v;

    auto isPrime = [](int k)->bool{
        if(k <= 1) return false;
        if(k == 2) return true;
        for(int i=2; i*i<=k; i++){
            if(k % i == 0)
                return false;
        }
        return true;
    };

    for(int i=0; i<numbers.size(); i++)
        v.push_back(i);
    do{
        for(int sz = 1 ; sz <= numbers.size(); sz++){
            string temp = "";
            for(int i=0; i<sz; i++)
                temp.push_back(numbers[v[i]]);
            if(temp != "" && !mp[stoi(temp)] && isPrime(stoi(temp))){
                mp[stoi(temp)] = true;
                answer++;
            }
        }
    }while(next_permutation(v.begin(), v.end()));

    return answer;
}

카펫 - level2

문제

여러 개의 연립 부정 방정식을 푸는 문제이다.

$n : 세로 길이$, $ m : 가로 길이$ 라고 가정하자$(n \leq m)$

1. $brown + yellow = nm$
2. $yellow = (n-2)(m-2)$

부정방정식의 형태가 디오판토스 방정식의 꼴로 표현되지 않으므로, Brute force 방식을 생각해볼 수 있다.

완전탐색으로 해를 시간 제한 내에 풀 수 있는지 확인하기 위해 입력 값의 제한 사항을 살펴보자.

주어진 제한 사항은 다음과 같다.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

앞에서 $yellow = (n-2)(m-2)$라는 것을 풀어보면

$nm -2(n+m) + 4 \leq 2,000,000$인 것을 알 수 있다.

또한, $(brown + yellow)\leq 2,005,000$인 것을 풀어보면

$nm \leq 2,005,000$인 것을 알 수 있다.

위 2식을 연립해주면 $n + m \leq 5000-4$ 인 것을 알 수 있다.

세로길이 $n$에 대해서 $2 \leq i \leq 2500$ 의 범위에서 n이 존재한다는 것을 알 수 있다.(이 후에 나올 가로 길이 j는 i보다 크거나 같은 것이 자명하므로)

가로길이 $m$에 대해서 $i \leq j \leq k$ and $i+j \leq 5000$의 범위에서m이 존재한다는 것을 알 수 있다.

완전탐색에 필요한 시간 복잡도는 $O(NM)$이므로 시간 복잡도 내에 문제를 해결할 수 있다는 것을 보일 수 있다.

#include <string>
#include <vector>

using namespace std;
typedef long long ll;
vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    bool isKeepGoing = true;
    for(ll i=2; i<=2500 && isKeepGoing; i++){
        for(ll j=i; i+j <= 5000; j++){
            if(brown + yellow == i*j && (ll)yellow == (i-2) * (j-2)){
                answer.push_back(j);
                answer.push_back(i);
                isKeepGoing = false;
            }
        }
    }
    return answer;
}