프로그래머스 - 완전탐색 : 모의고사 ,소수 찾기,숫자 야구

모의고사

이건 그냥 하면된다. ㅋㅋ

 

소수찾기

음 이게 좀 문젠데, 소수를 조합하는거랑 소수인지 확인하는 두가지 과정이 필요해 보인다.

 

음 이런 문제에서 항상 궁금했었다. 갯수 별로 잘라서 그걸 순열로 해야되는건가?!?!?

만들고 그게 소수인지 아닌지 확인하고, 중복인건 배열로 체크해서 제외하도록?

 

순열 알고리즘 구현을 찾았다. https://gorakgarak.tistory.com/522

순열(Permutation) 알고리즘

 

그리고 1월 안에는 풀어볼 문제들도... https://www.acmicpc.net/workbook/view/593

문제집: 완전검색-순열조합 (cwchoi00)

 

구현은 했는데 틀렸다. 그 이유는 string이 call by value라는 것... 

#include <string>
#include <vector>

using namespace std;

int visit[9999999] = { 0 };
int cnt = 0;

void swap(string str, int in1, int in2) {
	char tmp = str[in1];
	str[in1] = str[in2];
	str[in2] = tmp;
}

int stringToInt(string str,int size) {
	int exp = 1;
	int ans = 0;
	for (int i = size - 1; i >= 0; i--) {
		ans += (str[i] - '0')*exp;
		exp *= 10;
	}
	return ans;
}

bool isPrime(int x) {
	
	for (int i = 2; i < x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

void perm(string nums, int depth, int n, int k) {
	if (depth == k) {
		//to do 
		int prime = stringToInt(nums, k);
		
		if (prime > 1 && isPrime(prime) == true && visit[prime] == 0) {
			visit[prime] = 1;
			cnt++;
		}

		return;
	}
	for (int i = depth; i < n; i++) {
		swap(nums, i, depth);
		perm(nums, depth + 1, n, k);
		swap(nums, i, depth);
	}

}

int solution(string numbers) {
	int answer = 0;

	for (int i = 0; i < numbers.size(); i++) {
		perm(numbers, 0, numbers.size(), i);
	}

	answer = cnt;

	return answer;
}

void main() {
	solution("17");
}

http://www.cplusplus.com/forum/beginner/14042/이걸로 해결했다! 

how to pass reference of a string - C++ Forum

void swap(string* str, int in1, int in2) {
	char tmp = (*str)[in1];
	(*str)[in1] = (*str)[in2];
	(*str)[in2] = tmp;
}

 

삼성 야구공 문제에도 사용할 수 있을거 같다.!! 

음 근데 나중에 다시 풀때는 next_perm 사용하는 것도 다시 봐야할 것같다.

 

 

숫자 야구

삼성 소프트웨어 문제랑 같은 문제 유형이다. 풀이도 똑같은 것인가?.... 왜 완전탐색이라고 생각하지 못했을까...... 뭔가 스트라이크 볼수에 따라서 내가 조건을 설정할 수 있을것이라 생각했다. 근데 막생 해보니까 일일이 조건을 설정하기에는 무수히 많았다.....

 

#include <string>
#include <vector>
#include<queue>

using namespace std;

int arr[10];
queue<vector<int>> q;
queue<vector<int>> q2;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}



void perm(int arr[], int n, int r, int depth) {
	if (r == depth) {
		vector<int> tmp;
		tmp.push_back(arr[0]);
		tmp.push_back(arr[1]);
		tmp.push_back(arr[2]);
		q.push(tmp);
		return;
	}

	for (int i = depth; i < n; i++) {
		swap(&arr[i], &arr[depth]);
		perm(arr, n, r, depth + 1);
		swap(&arr[i], &arr[depth]);
	}
}

void init() {
	for (int i = 1; i < 10; i++) {
		arr[i] = i;
	}
	perm(arr, 10, 3, 0);
}

struct SB {
	int strike=0;
	int ball=0;
};

SB compare(vector<int>a, vector<int>b) {
	SB tmp;
	for (int i = 0; i < 3; i++) {
		if (a[i] == b[i] ) {
			tmp.strike += 1;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i != j && a[i] == b[j]) {
				tmp.ball++;
			}
		}
	}
	return tmp;
}

void getRidof(vector<int> baseball, int strike, int ball) {
	SB result;

	while (!q.empty()) {
		vector<int> frontVec = q.front();
		result = compare(baseball, frontVec);
		if (result.strike != strike || result.ball != ball) {
			;
		}
		else {
			q2.push(frontVec);
		}
		q.pop();
	}

	while(!q2.empty()){
		q.push(q2.front());
		q2.pop();
	}

}

vector<int> getVec(int x) {
	vector<int> tmp;
	string str = to_string(x);
	tmp.push_back(str[0]-'0');
	tmp.push_back(str[1]-'0');
	tmp.push_back(str[2]-'0');

	return tmp;
}

int solution(vector<vector<int>> baseball) {
	int answer = 0;

	init();

	for (int i = 0; i < baseball.size(); i++) {
		getRidof(getVec(baseball[i][0]),baseball[i][1],baseball[i][2]);
	}
	answer = q.size();

	return answer;
}

void main() {

	vector<int>tmp;
	vector<vector<int>>sum;

	tmp.push_back(123);
	tmp.push_back(1);
	tmp.push_back(1);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(356);
	tmp.push_back(1);
	tmp.push_back(0);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(327);
	tmp.push_back(2);
	tmp.push_back(0);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(489);
	tmp.push_back(0);
	tmp.push_back(1);
	sum.push_back(tmp);
	tmp.clear();

	solution(sum);
}

그런데 예제는 맞는데 테케는 50점이다..... 1-9라는 것도 수정했는데 왜 여전히 이렇지? 아 init을 잘 못 수정해서 0이 포함됬었다. 다시 고쳤다.

 

#include <string>
#include <vector>
#include<queue>

using namespace std;

int arr[10];
queue<vector<int>> q;
queue<vector<int>> q2;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}



void perm(int arr[], int n, int r, int depth) {
	if (r == depth) {
		vector<int> tmp;
		tmp.push_back(arr[0]);
		tmp.push_back(arr[1]);
		tmp.push_back(arr[2]);
		q.push(tmp);
		return;
	}

	for (int i = depth; i < n; i++) {
		swap(&arr[i], &arr[depth]);
		perm(arr, n, r, depth + 1);
		swap(&arr[i], &arr[depth]);
	}
}

void init() {
	for (int i = 1; i < 10; i++) {
		arr[i-1] = i;
	}
	perm(arr, 9, 3, 0);
}

struct SB {
	int strike=0;
	int ball=0;
};

SB compare(vector<int>a, vector<int>b) {
	SB tmp;
	for (int i = 0; i < 3; i++) {
		if (a[i] == b[i] ) {
			tmp.strike += 1;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i != j && a[i] == b[j]) {
				tmp.ball++;
			}
		}
	}
	return tmp;
}

void getRidof(vector<int> baseball, int strike, int ball) {
	SB result;

	while (!q.empty()) {
		vector<int> frontVec = q.front();
		result = compare(baseball, frontVec);
		if (result.strike != strike || result.ball != ball) {
			;
		}
		else {
			q2.push(frontVec);
		}
		q.pop();
	}

	while(!q2.empty()){
		q.push(q2.front());
		q2.pop();
	}

}

vector<int> getVec(int x) {
	vector<int> tmp;
	string str = to_string(x);
	tmp.push_back(str[0]-'0');
	tmp.push_back(str[1]-'0');
	tmp.push_back(str[2]-'0');

	return tmp;
}

int solution(vector<vector<int>> baseball) {
	int answer = 0;

	init();

	for (int i = 0; i < baseball.size(); i++) {
		getRidof(getVec(baseball[i][0]),baseball[i][1],baseball[i][2]);
	}
	answer = q.size();

	return answer;
}

void main() {

	vector<int>tmp;
	vector<vector<int>>sum;

	tmp.push_back(123);
	tmp.push_back(1);
	tmp.push_back(1);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(356);
	tmp.push_back(1);
	tmp.push_back(0);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(327);
	tmp.push_back(2);
	tmp.push_back(0);
	sum.push_back(tmp);
	tmp.clear();

	tmp.push_back(489);
	tmp.push_back(0);
	tmp.push_back(1);
	sum.push_back(tmp);
	tmp.clear();

	solution(sum);
}