이번 문제는 프로그래머스의 레벨 3 캠핑 문제이다.
문제를 차근차근 한번 읽어보도록 하자.
2개의 쐐기를 골라 텐트를 설치하려고 한다.
최대 5000개의 쐐기 좌표가 주어진다.
또한 각 좌표는 최대 2^31 - 1까지 값이 주어진다.
텐트의 넓이는 0이 될 수 없으며, 텐트 중간에 쐐기가 들어갈 수 없다.
총 몇 개의 텐트를 만들 수 있을까!
조건 분석
먼저 각 좌표가 2^31 - 1의 크기를 가질 수 있음을 생각해보자.
뭔가 좌표 별 배열을 만들어서 푸는 것은 불가능함을 알 수 있다.
예를 들어 동적 계획법 같은 풀이가 불가능하다는 말이다.
그럼 완전 탐색으로, 모든 쐐기를 선택하는 경우를 체크한다면?
2쌍의 쐐기 쌍을 선택하는 행동만 O(N^2)의 시간을 사용하게 된다.
매 쌍마다 가운데에 쐐기가 없는지 검사도 해야하므로 시간이 더 걸린다.
쐐기 유무의 검사 또한 선형으로 진행되므로, O(N^3)이 걸릴 수도 있다.
즉, 완전 탐색으로는 최악의 경우 O(5000^3)의 시간이 소요된다.
그럼 어떤 방식으로 효율적으로 풀 수 있을까?
정렬
우선 나는 반드시 정렬이 필요하다고 생각했다.
항상 어떤 값을 탐색하거나 할 때엔 정렬된 상태로 탐색하는 것이 빠르다.
우리는 좌표들을 비교하는 연산을 해야 하기 때문에, 정렬을 해야만 한다.
정렬로 우리는 탐색 순서를 조절해 시간을 줄일 수 있다.
또한 정렬은 범위를 제한할 수 있는 효과를 준다.
예를 들어 정렬된 상태로, 1번 쐐기와 4번 쐐기를 선택했다면?
두 쐐기 사이의 쐐기들만 검사하면 될 것이다.
왜 그럴까?
우선 그냥 정렬을 하면 x좌표를 기준으로 정렬이 될 것이다.
만약 어떤 쐐기가 두 쐐기 사이에 있을 가능성이 있으려면?
당연히 x좌표가 사이에 있어야 하므로, 그런 결론이 도출되는 것이다.
우선 아래와 같이 구현하고 제출해보았다.
int solution(int n, vector<vector<int>> data) {
int answer = 0;
sort(data.begin(), data.end());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (data[i][0] == data[j][0] || data[i][1] == data[j][1])
continue;
// 좌표가 같으면 직사각형의 넓이가 0이 돼버린다.
bool exist_pile = true;
for (int inner = i + 1; inner < j; inner++) {
// 어차피 정렬을 했으니, 선택한 i + 1 번째 쐐기와
// 다음으로 선택된 j 번째 쐐기 내에서만 확인하면 된다.
int inner_x = data[inner][0];
int inner_y = data[inner][1];
if ((data[i][0] < inner_x && inner_x < data[j][0]) &&
(min(data[i][1], data[j][1]) < inner_y && inner_y < max(data[i][1], data[j][1]))) {
// X좌표는 정렬되어 있어 x1 < 쐐기_x < x2 로 사용해도 된다.
// 하지만 Y좌표는 정렬되어 있지 않다.
// 따라서 Y좌표는 min, max 함수를 통해 가공이 필요하다
exist_pile = false;
break;
}
}
if (exist_pile)
answer++;
}
}
return answer;
}하지만 시간 초과가 발생했다.
시간이 10초 이상 소요되는 것인데, 시간을 더 줄일 수 있을까?
내장 함수의 시간복잡도
결국 다른 사람들의 풀이를 참고하며 해답을 얻었다.
문제는 내장함수인 min(), max() 함수였다.
내가 생각하기엔 매개변수가 2개인 min(), max() 함수의 시간복잡도는
분명히 단순 대소비교로 O(1)만에 끝난다고 생각하는데,
해당 함수를 빼고 3항 연산자를 통해서 변수를 만들어 주었다.
곧바로 시간초과 없이 문제를 풀 수 있었다.
내장 함수의 시간 복잡도에 대해서 좀 더 알아볼 필요가 있을 것 같다.
이번 문제를 풀며 깨달은 점은 일단 부딪혀 보자는 것이다.
아 이거 시간초과 날거 같은데~ 하더라도 일단은 구현해보자.
그 방법이 맞으면 좋고, 안되면 과감하게 버리면 되는 일이다.