Programmers - 완전탐색
주어진 찍는 방식을 배열에 저장하고 answer와 비교하여 맞춘 갯수의 배열을 만들어 가장 큰 값을 찾은 뒤 같은 배열을 찾으면 된다.
vector<int> solution(vector<int> answers) {
vector<int> answer;
vector<vector<int>> supos = {
{1, 2, 3, 4, 5},
{2, 1, 2, 3, 2, 4, 2, 5},
{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}};
vector<int> supo_check(3, 0);
for (int i = 0; i < answers.size(); i++) {
for (int j = 0; j < supos.size(); j++) {
if (supos[j][i % supos[j].size()] == answers[i])
supo_check[j]++;
}
}
auto m = max_element(supo_check.begin(), supo_check.end());
for (int i = 0; i < supo_check.size(); i++)
if (m[0] == supo_check[i])
answer.push_back(i + 1);
return answer;
}
각기 다른 길이와 중복되지 않는 숫자를 만들기 위해 재귀함수를 이용하여 순회한다. 백트레킹?을 이용하여 전체를 순회할 수 있는것 같다.
아리스토테네스의 체를 이용하여 소수의 계산을 위한 반복문의 순회를 줄이도록 한다.
입력된 숫자를 전체 순회하는 방법의 아이디어를 생각해내고 이를 직접 코드로 작성하는데 시간이 많이 걸렸으며 중복확인을 위해 unordered_map을 빠르게 적용하지 못했다.
모든 숫자를 순회(완전탐색)하여 주어진 3개의 숫자와 비교하여 나온 스트라이크와 볼의 개수를 비교하여 가능한 숫자의 갯수를 출력하였다.
모든 숫자는 9P3 으로 504개 밖에 되지않아 생각보다 오래걸리지 않는다. 따라서 완전탐색하는데 시간이 부족하지 않다.
카펫의 갈색 부분은 brown은 width * 2 + height * 2 - 4이고 red는 (width - 2) * (height - 2)이다.
이 문제가 완전탐색이라는 주제에 있어서 풀 수 있었지만 문제만 주어졌을 때는 완전탐색으로 풀었을지는 모르겠다.
brown이 8 ~ 5000 이하의 자연수임을 보고 width의 최대 상한을 대략적으로 2500이라 가정하고 최대 계산횟수는 6250000 1000ms안에 끝낼수 있을것 같았다.
(brown이 5000일때 width의 최댓값은 height가 최솟값 3이라고 생각하면 2499 이다)
문제를 읽고 어떤 방식으로 접근하여 풀어야 겠다는 생각이 잘 나지 않는데 많은 문제를 풀어 익숙해지도록 할 수 밖에 없는 것 같다.
댓글남기기