본 문제는 정말 마음에 안들게 푼 문제이다. 해결 후에 분명 더 좋은 방법이 있을거라고 생각은 드는데 쉽게 생각이 떠오르질 않아서 기분이 좋지 않았다. 그리고 다른 사람의 풀이를 보는데 ‘왜 이렇게 생각하지 못했지’, ‘이번 문제는 정말 못 풀었다’하는 생각이 들었다. 그래서 풀고나서 다른 사람의 코드를 참고해 다시 한 번 더 풀어서, 처음에 생각했던 알고리즘과 다른 사람의 코드를 참고해서 다시 내 나름대로 푼 알고리즘 두 가지가 있다.
1. 문제
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한조건
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
2. 알고리즘! 생각해보자
초반에 해결한 코드
- 빨간색 격자의 수를 기준으로 1이상 2,000,000 이하 개로 만든 카펫에 대해서 다음을 반복한다.
- 카펫이 정사각형일 때와 그렇지 않을 때를 구분하여, 정사각형일 때에는 (한 변의 빨간 격자 수 + 2) 값을 가로, 세로 값으로 반환한다.
(정사각형인지 확인하는 방법은 i를 한 변의 빨간 격자 수라고 했을 때 \(i^2\) 의 제곱이red와 같은지 확인하고,
(\((i+2)^2 - red 격자 수\)) 값이brown과 같은지 확인해서 둘 다 같으면 정사각형이다) - 정사각형이 아닐 때에는 세로의 길이를 1씩 줄어가면서 맞는 길이를 찾는다.
(코드 상에서sqrt_num이 세로의 빨간 격자 수이다) - 맞는 길이를 찾으면 마찬가지로 (가로의 빨간 격자 수 + 2), (세로의 빨간 격자 수 + 2) 값을 반환한다.
다른 사람의 코드를 참고해 수정한 코드
brown/2 + 2를 해 가로와 세로의 길이를 합한 값이 되는 len 변수를 생성한다.- 세로 길이
h를 3부터 시작하고, 가로 길이w를 (len - 3)부터 시작해서 세로×가로 값이 전체 격자 수와 동일해질 때 까지 계속해서 세로는 증가시키고 가로는 감소시킨다.
(brown은 8이상의 값이라고 했으므로 세로의 길이는 3부터 시작할 수 있다) - 반복 문에서 벗어나면, 해당 가로, 세로 길이 값을 반환한다.
(반복 문에서 벗어나면 해당 카펫의 격자 수와 동일한 가로, 세로 길이를 구했다는 뜻이므로)
3. 해결코드
[C++]
초반에 해결한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<int> solution(int brown, int red) {
for (int i = 1; i <= sqrt(2000000); i++) {
int pow_num = pow(i, 2);
if (pow_num == red) {
if (brown == (pow((i + 2),2) - red)) return {i+2, i+2};
} else if (pow_num >= red) {
int sqrt_num = i - 1;
while(1) {
while(red % sqrt_num != 0) sqrt_num--;
if (brown == ((sqrt_num + 2) * ((red/sqrt_num) + 2) - red))
return {(red/sqrt_num) + 2, sqrt_num + 2};
else sqrt_num--;
}
}
}
}
다른 사람의 코드를 참고해 수정한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int red) {
int len = brown/2 + 2;
int w = len - 3;
int h = 3;
while(w*h != brown+red) { h++; w--; }
return {w, h};
}
4. 해결능력UP, 깊이 생각해보기
- 벡터를 선언하지 않고 바로 사용할 수 있다는… 신세계 (파이썬 같다)
- 초반에 너무 복잡하게 풀었고 정말 좋지 않은 코드 방법으로 풀었다 → 자칫 잘못하면 무한 루트에 빠지는 불상사가..
5. 참고해서 문제해결 ٩( ᐛ )و
- [C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근) https://blockdmask.tistory.com/307
- 어떤 수의 제곱을 구할 때는
pow()함수 사용
- 어떤 수의 제곱을 구할 때는
- [C++] std :: vector 초기화하기
https://riptutorial.com/ko/cplusplus/example/1676/std----vector-%EC%B4%88%EA%B8%B0%ED%99%94%ED%95%98%EA%B8%B0- vector를 초기화 할 때
vector v{n1, n2, ...};식으로 바로 어떤 값을 할당하며 초기화 가능 - 특정 변수에 vector를 할당할 필요없이 그냥 사용할 때에는
{n1, n2, ...}식으로 바로 사용 가능
- vector를 초기화 할 때
1
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges