[프로그래머스 - level2] [완전탐색] 카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

brown 50, yellow 22 로 테스트해보시기 바랍니다.

기댓값은 [24,3] 입니다.

---

 

풀이 과정

<첫번째 풀이>

brown격자수 + yellow격자수 = 가로*세로

-> 감이 안와서 질문하기에서 문제 푸는 팁을 참고 : 1. yellow의 약수를 배열에 담아줍니다

yellow 타일 변 = 1 -> 카펫(brown)의 가로는 yellow격자가로+2, 카펫(brown)의 세로는 yellow격자세로+2

yellow의 약수 조합(yellow격자의 가로,세로)을 배열에 넣고 brown을 해당 조합의 가로+2, 해당 조합의 세로+2로 친 다음 계산한 brown의 가로*세로 == brown+yellow면 계산한 값이 가로,세로 answer

가로길이는 세로길이와 같거나 세로길이보다 길다는 조건 주의

 

약수 계산을 어떻게 하냐 -> 소인수분해: 반복문으로 2부터 소수를 늘려가면서 1이 될 때까지 나눈다. 한번 돌 때 나눈 수를 배열에 담는다. -> 배열에 담겨있는 인수들의 곱을 조합해 pair에 담는다(큰 수를 pair의 first로).

세로 길이가 1일수는 없으니까 1은 제외.

 

2 24 -> 2,12 / 4,6 / 8,6

2 12

2  6

3  3

소인수분해 할때 소인수를 못 찾아서 틀리는듯.. 소수 찾는 알고리즘을 찾아야겠다 -> 에라토스테네스의 체

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

vector<int> solution(int brown, int yellow) {
	vector<int> answer;
	vector<pair<int, int>> y_factorCombi; // 가로,세로
	vector<int> y_factors;
	int y_temp = yellow;
	int factor = 2;

	if (y_temp == 1) {
		y_factorCombi.emplace_back(make_pair(1, 1));
	}

	while (y_temp != 1) {
		y_temp /= factor;
		y_factors.emplace_back(factor);
		if (y_temp % 2 != 0) {
			if (y_temp % 3 == 0)
				factor = 3;
			if (y_temp % 5 == 0)
				factor = 5;
		}
		if(y_factors.size() <2 && y_temp == 1)
			 y_factors.emplace_back(1);
	}

	for (int i = 1; i < y_factors.size(); ++i) {
		int firstTmp = 1;
		int secondTmp = 1;
		//if(i == 0) 
			//firstTmp = y_factors[i];
		for (int j = 0; j < i; ++j) {
			firstTmp *= y_factors[j];
		}
		for (int k = i; k < y_factors.size(); ++k) {
			secondTmp *= y_factors[k];
		}
		if (secondTmp > firstTmp) {
			y_factorCombi.emplace_back(make_pair(secondTmp, firstTmp));
		}
		else {
			y_factorCombi.emplace_back(make_pair(firstTmp, secondTmp));
		}
	}

	for (auto combi : y_factorCombi) {
		if ((combi.first + 2) * (combi.second + 2) == brown + yellow)
		{
			answer.emplace_back(combi.first);
			answer.emplace_back(combi.second);
		}
	}

	/*for (auto it = y_factorCombi.begin(); it != y_factorCombi.end(); ++it) {
		if (((*it).first + 2) * ((*it).second + 2) == brown * yellow)
		{
			answer.emplace_back((*it).first);
			answer.emplace_back((*it).second);
		}
	}*/

	return answer;
}

 

<두번째 풀이> 

에스토레네스의 체를 사용하여 소수를 판별 한 다음 벡터에 넣어서 index를 하나씩 올려줘 소인수분해.

3,6,7,8,10 TC 실패.

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

using namespace std;

bool isZeroValue(int n) {
    if( n == 0)
        return true;
    else
        return false;
}


vector<int> solution(int brown, int yellow) {
	vector<int> answer;
	vector<pair<int, int>> y_factorCombi; // 가로,세로
	vector<int> y_factors;
	vector<int> primeNums(yellow+1);
	int y_temp = yellow;
	int factorIdx = 0;

	//if (y_temp == 1) {
		y_factorCombi.emplace_back(make_pair(y_temp, 1));
	//}
	// 입력받은 수 만큼 배열에 모두 초기화 해둔다

	for (int i = 2; i <= yellow; i++) {
		primeNums[i] = i;
	}

	for (int i = 2; i*i < yellow; i++) {
		if (primeNums[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다
			continue;
		for (int j = i + i; j <= yellow; j += i) { // i를 제외한 i의 배수들은 0으로 체크
			primeNums[j] = 0;
		}
	}
	primeNums.erase(remove_if(primeNums.begin(), primeNums.end(), isZeroValue),primeNums.end());

	while (y_temp != 1) {
		if (y_temp%primeNums[factorIdx] == 0) {
			y_temp /= primeNums[factorIdx];
			y_factors.emplace_back(primeNums[factorIdx]);
		}
		else
			++factorIdx;
		
		if (y_factors.size() < 2 && y_temp == 1)
			y_factors.emplace_back(1);
	}

	for (int i = 1; i < y_factors.size(); ++i) {
		int firstTmp = 1;
		int secondTmp = 1;
		//if(i == 0) 
			//firstTmp = y_factors[i];
		for (int j = 0; j < i; ++j) {
			firstTmp *= y_factors[j];
		}
		for (int k = i; k < y_factors.size(); ++k) {
			secondTmp *= y_factors[k];
		}
		if (secondTmp > firstTmp) {
			y_factorCombi.emplace_back(make_pair(secondTmp, firstTmp));
		}
		else {
			y_factorCombi.emplace_back(make_pair(firstTmp, secondTmp));
		}
	}


	for (auto combi : y_factorCombi) {
		if ((combi.first + 2) * (combi.second + 2) == brown + yellow)
		{
			answer.emplace_back(combi.first + 2);
			answer.emplace_back(combi.second + 2);
            break;
		}
	}
    //cout << answer[0] << ',' << answer[1];

	return answer;
}

-> 반례를 도저히 못 찾겠어서 다른 풀이를 참고했는데 세로길이는 무조건 3 이상 이라는 조건(중간에 yellow가 무조건 있어야 하기 때문에) 으로 임의의 세로를 반복문에서 점점 더해가고,

'brown+yellow = 가로*세로' =>  '가로 = brown+yellow / 세로' 식을 이용해 가로를 구한 다음

반복문에서 '(가로-2)*(세로-2) = yellow' 가 되는지 검사한 뒤 return 하면 되는 것 

 

-> 이 식은 원래 생각했던 brown을 yellow가로+2로 생각했던 방정식을 역으로 한 것인데 더 생각해보지 않아서 문제를 엄청 복잡하게 푼 것 같다. 이대로 풀면 간단한 문제였다.. 간단하게 풀기 위해서 조금만 더 생각해보는 것이 좋겠다

 

 

코드 

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

using namespace std;


vector<int> solution(int brown, int yellow) {
	vector<int> answer;
    int tiles = brown + yellow;
    for(int h=3;;++h) { // 세로는 3이상
        int w = tiles / h;
        if((w-2)*(h-2) == yellow)
        {
            answer.emplace_back(w);
            answer.emplace_back(h);
            break;
        }
    }
    
	return answer;
}

 

 

 

 

알게된 것

- iterator를 사용하는 반복문에서 pair가 들은 container의 iterator를 참조했을 때 값의 first, second인자에 접근하려면 (*it).first , (*it).second 이런식으로 써야 오류가 안나고 사용이 가능하다.

for (auto it = y_factorCombi.begin(); it != y_factorCombi.end(); ++it)
{
  if ((*it.first + 2) * (*it.second + 2) == brown * yellow) // 이렇게 쓰면 오류!
{
  answer.emplace_back(*it.first); // 이렇게 쓰면 오류!
  answer.emplace_back(*it.second); // 이렇게 쓰면 오류!
}
}

---

 

for (auto it = y_factorCombi.begin(); it != y_factorCombi.end(); ++it)
{
 if (((*it).first + 2) * ((*it).second + 2) == brown * yellow) // 이렇게 써야 오류 안난다!
{
 answer.emplace_back((*it).first); // 이렇게 써야 오류 안난다!
 answer.emplace_back((*it).second); // 이렇게 써야 오류 안난다!
}
}

- 범위기반 for문은 데이터를 변수에 저장해주기 때문에 iterator가 아니라서 참조를 쓸 필요가 없다. 이거 실수했음

매 반복문이 돌때마다 int elem : arr 을 통해서 하는 일은 아래와 같습니다.
elem = arr[0];
elem = arr[1];
이런식으로 배열의 요소들이 elem 이라는 변수에 복사됩니다.

---

- 범위기반 for문에 대해서 더 자세하게 알아보려고 검색한 결과 나온 글에서 발췌. 알아둬야 한다.

그래서 배열의 요소를 내부에서 바꾸려고 elem = 1; 시도를 해도. 복사된 값 이기 때문에 arr[0] 의 값이 바뀌거나 하지않습니다.

그래서 range based for문 내부에서는 배열의 요소를 변경할수 없습니다.

범위기반 for문에 대해서 더 자세하게 알아보려고 검색한 결과 이 글을 발견했다. 읽어보면 좋을 것 같다.

https://blockdmask.tistory.com/319

[C++] range based for, 범위기반 for 반복문에 대해서.

 

- 프로그래머스 컴파일러에서 signal: floating point exception (core dumped)

이 오류는 변수를 0으로 나눌 때 생기는 오류라고 한다.

 

- 에라토스테네스의 체 : 소수를 구하는 알고리즘

https://donggoolosori.github.io/2020/10/16/eratos/

[Algorithm] 에라토스테네스의 체 - C++ - DGOS | 동꿀오소리