서론
오늘의 코딩 테스트 문제는 프로그래머스의 '카펫' 문제입니다. 한동안 프로그래머스 문제를 풀지 않아 감을 잃은 것 같아 연습 삼아 풀어보기로 했습니다.
문제 분석
문제의 핵심은 다음과 같습니다:
1.
테두리가 갈색, 내부가 노란색인 직사각형 카펫이 있습니다.
2.
갈색 격자의 수와 노란색 격자의 수가 주어집니다.
3.
카펫의 가로, 세로 크기를 구해야 합니다.
4.
가로 길이는 세로 길이와 같거나 깁니다.
제한 사항으로는, 갈색은 8~5,000, 노란색은 1~2,000,000 범위의 자연수입니다.
접근 방식
문제를 풀기 위해 다음과 같은 접근 방식을 사용했습니다:
1.
가로를 n, 세로를 m이라고 할 때, 노란색 격자의 수는 (n-2) * (m-2)입니다.
2.
갈색 격자의 수는 2n + 2(m-2)입니다.
3.
갈색 격자의 수로부터 n+m을 구할 수 있습니다.
4.
n+m 값을 이용해 가능한 n과 m의 조합을 완전탐색합니다.
브루트포스 방식으로 충분히 해결할 수 있을 것으로 판단했습니다.
코드 구현
코드는 다음과 같이 구현했습니다:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer(2, 0);
int nm = 0; // n + m을 의미
nm = (brown + 4)/2; // 테두리의 수로부터 n+m을 구함
for (int m=(nm/2); m>=3; m--) // 경우의 수 완전탐색
{
int n = nm-m;
if ((n-2) * (m-2) == yellow)
{
answer[0] = n;
answer[1] = m;
}
}
return answer;
}
C++
복사
핵심 로직은 다음과 같습니다:
1.
갈색 격자의 수로부터 n+m을 계산합니다.
2.
가능한 m값에 대해 반복문을 실행합니다.
3.
조건을 만족하는 n, m 조합을 찾으면 반환합니다.
문제 해결 및 최적화
코드를 구현한 후 테스트를 진행했습니다. 특별한 문제점은 발견되지 않았습니다.
최적화 관점에서 보면, 현재 구현은 O(n)의 시간 복잡도를 가집니다. 주어진 제한 사항 내에서는 충분히 효율적입니다.
회고
이번 문제를 통해 몇 가지 점을 깨달았습니다.
역시 코딩 테스트 문제는 주기적으로 풀어야 감을 유지할 수 있습니다. 프로그래머스 환경에 다시 익숙해질 필요가 있을 것 같습니다.
