프로그래머스 - 완전탐색(모의고사, 소수찾기, 카펫)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12230

👀문제이해 및 풀이방법

완전탐색 문제 사실상 구현문제라고 봐도 무방하다.
2번 문제인 소수찾기 문제가 조금 까다로웠는데 조금 중복이 있더라도 permutation함수를 사용해서 풀었다.
숫자들의 목록으로 만들수있는 모든 숫자들을 다 체크하는게 쉬운일은 아니였다
prime_table의 경우 자주 쓰이므로 계속 리마인드 하는게좋을것 같다
3번문제인 카펫은 그냥 흘러가는데로 짜봤는데 엄청 짧게 잘 풀린것 같다

📝코드

1 모의고사

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

vector<int> solution(vector<int> answers) {
    int x=0,y=0,z=0;
    for(int i=0;i<answers.size();i++){
        if(answers[i]==(i)%5+1)
            x++;
        if(i%2==0 && answers[i]==2)
                y++;
        else if(i%2==1){
            int tmp= (i/2)%4;
            if(tmp==0&& answers[i]==1)
                y++;
            else if(tmp!=0 && answers[i]==tmp+2)
                y++;
        }
        int t =(i/2)%5;
        if(t==0 && answers[i]==3)
            z++;
        else if(t==1 && answers[i]==1)
            z++;
        else if(t==2 && answers[i]==2)
            z++;
        else if(t==3 ||t==4){
            if(answers[i]==t+1)
                z++;
        }
    }
    vector<int> answer;
    int sol=max(max(x,y),z);
    if(x==sol)
        answer.push_back(1);
    if(y==sol)
        answer.push_back(2);
    if(z==sol)
        answer.push_back(3);
    
    return answer;
}

2 소수 찾기

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class prime_num{
private:
    vector<bool> prime_table;
    string numbers;
    int size;
public:
    prime_num(string& n):numbers(n){
        size = (int)pow(10,numbers.size());
        prime_table.resize(size,true);
        prime_table[0]=false;
        prime_table[1]=false;
        for(int i=2;i<size;i++){
            if(prime_table[i]){
                for(int j=2;j<=(size-1)/i;j++)
                    prime_table[i*j]=false;
            }
        }
    }  
    int fins_sol(){
        int sol=0,tmp;
        for(int i=1;i<=numbers.size();i++){
            sort(numbers.begin(),numbers.end());
            do{
                tmp=stoi(numbers.substr(0,i));
                if(prime_table[tmp]){
                    prime_table[tmp]=false;
                    sol++;
                }
            }while(next_permutation(numbers.begin(),numbers.end()));
        }
        return sol;
    }
};
int solution(string numbers) {
    prime_num pn(numbers);
    return pn.fins_sol();
}

3 카팻

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    for(int i=3;i<brown/2;i++){
        if((brown-i*2)/2*(i-2)==yellow)
            return {(brown+yellow)/i,i};
    }
}