오늘은 프로그래머스에서 완전탐색 문제 중 마지막 문제인 카펫 문제 풀이를 해보겠습니다. 오늘 문제로 완전탐색 관련 문제가 끝난다니 아쉬우실수도 있지만, 우리가 풀 문제들은 다양하고 많으니 함께 계속 공부했으면 좋겠습니다.
프로그래머스 > 완전탐색 > 카펫 문제 풀이
◈ 문제 정보
문제명: 카펫
문제 난이도: Level 2
문제 푼 사람수: 23752명
사용 가능 언어: 11개 (JavaScript 사용)
◈ 문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
이 문제는 테두리에 칠해져 있는 갈색의 수, 내부에 칠해져 있는 노란색의 수를 통해 카펫의 가로, 세로 길이를 구하는 문제입니다.
갈색 격자의 수와 노란색 격자의 수를 통해 카펫의 가로, 세로 길이를 구하기
Inputs
brown: 격자 문양의 카펫 테두리에 칠해져있는 갈색 격자의 수
yellow: 격자 문양의 카펫 내부에 칠해져있는 노란색 격자의 수
Output: 카펫의 가로, 세로 길이
◈ 제한 사항
⊙ 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. ⊙ 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. ⊙ 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
8 ≤ 갈색 격자의 수(brown) ≤ 5,000
1 ≤ 노란색 격자의 수(yellow) ≤ 2,000,000
카펫의 가로 길이 ≥ 카펫의 세로 길이
◈ 입출력 예
brown
yellow
return
10
2
[4,3]
8
1
[3,3]
24
24
[8,6]
이번 문제도 입출력 예에 대한 설명이 없어 제가 해보겠습니다.
예제 #1
문제에서 나온 예와 같습니다.
예제 #2
위 그림과 같은 카펫이므로 가로 길이는 3, 세로 길이도 3입니다.
예제 #3
위 그림과 같은 카펫이므로, 가로 길이는 8, 세로 길이는 6입니다. 이 때, 가로 길이가 세로 길이보다 같거나 크기 때문에 위와 같습니다.
◈ 알고리즘 만들기
1. 갈색 격자의 수(brown)을 통해 가로 + 세로의 길이를 구한다. ≫ (brown + 4) / 2 2. 갈색 격자의 수(brown)을 통해 최소 가로의 길이를 구한다. (정사각형일 경우가 가장 가로가 짧다. ≫ 가로+세로 / 2) 3. 갈색 격자의 수(brown)을 통해 최대 가로의 길이를 구한다. (세로 길이는 최소 3이다. ≫ 최대 가로 길이는 (가로+세로 - 3) 4. 최대 가로 길이부터 최소 가로 길이까지의 카펫에 대해서 노란색 격자의 수(yellow)와 일치 여부를 확인한다. 5. 일치할 경우 카펫의 가로, 세로 길이를 반환한다.
알고리즘의 효율성을 높이기 위해 완전탐색을 위한 범위를 최대 가로 길이 ~ 최소 가로 길이까지로 줄여 그 사이를 반복하여 확인하도록 하였습니다. 이 때, 완전탐색이라도 모든 경우의 수를 검사하는 것이 아니라 최소한으로 경우의 수를 줄여 검사하도록 하는 것이 더 좋은 알고리즘입니다.
◈ 코드 구현
function solution(brown, yellow) {
var answer = [];
// 1. 갈색 격자의 수(brown)을 통해 가로 + 세로의 길이를 구한다. ≫ (brown + 4) / 2
let sumWidthAndHeight = (brown + 4) / 2;
// 2. 갈색 격자의 수(brown)을 통해 최소 가로의 길이를 구한다.
// (정사각형일 경우가 가장 가로가 짧다. ≫ 가로+세로 / 2)
let minWidth = sumWidthAndHeight / 2;
// 3. 갈색 격자의 수(brown)을 통해 최대 가로의 길이를 구한다.
// (세로 길이는 최소 3이다. ≫ 최대 가로 길이는 (가로+세로 - 3)
let maxWidth = sumWidthAndHeight - 3;
// 4. 최대 가로 길이부터 최소 가로 길이까지의 카펫에 대해서 노란색 격자의 수(yellow)와 일치 여부를 확인한다.
for(let width = maxWidth; width >= minWidth; width--) {
let height = sumWidthAndHeight - width;
let innerCount = (width - 2) * (height - 2);
// 5. 일치할 경우 카펫의 가로, 세로 길이를 반환한다.
if(yellow == innerCount) {
answer = [width, height];
break;
}
}
return answer;
}
◈ 채점 결과
오늘의 채점 결과는 정확성 테스트 케이스만 13개 있었으며, 모두 엄청 빠른 시간에 통과하였습니다.
오늘도 프로그래머스에서 완전 탐색 문제 중 카펫 문제 풀이를 해보았습니다. 이것으로 프로그래머스에서 완전 탐색 문제 풀이가 마무리되었습니다. 그럼 다음 문제 풀이로 찾아오겠습니다.
댓글