[C++로 풀이] 보석 쇼핑 (투포인터 알고리즘)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 보석 쇼핑
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이
🔥 1 차 풀이 ⏰(시간 초과)
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
// 보석 하나
struct Jewelry {
string name; // 보석의 이름 문자열
set<int> positions; // 이 보석이 위치한 인덱스들 모아둔 집합 (set이라 자동 정렬)
int size; // 이 보석은 gems 내에 몇개 있는지
};
bool compare(const Jewelry& a, const Jewelry& b) {
if (a.size == b.size)
return *(a.positions.begin()) < *(b.positions.begin()); // 같은 개수를 가진 보석이라면 인덱스가 더 앞에 있는(=더 왼쪽에 있는) 보석을 우선
return a.size < b.size; // 오름 차순 정렬. gems 내에서 적게 있는 보석일 수록 앞에 위치하게끔
}
vector<int> solution(vector<string> gems) {
vector<int> answer;
unordered_map<string, set<int>> kindOfJew; // [보석 이름, 해당 보석이 위치한 인덱스들 모아둔 집합]
vector<Jewelry> sortedJew; // 적은 빈도수를 가진 레어한 보석일 수록 앞에 위치하도록 정렬
for (int i = 0; i < gems.size(); ++i)
kindOfJew[gems[i]].insert(i);
for (auto& jew : kindOfJew){
int n = jew.second.size();
sortedJew.push_back({jew.first, jew.second, n});
}
sort(sortedJew.begin(), sortedJew.end(), compare);
for (int i = sortedJew.size(); i <= gems.size(); ++i) {
for (int j = 0; j < sortedJew.size(); ++j) {
for (auto& pos : sortedJew[j].positions) {
int firstStart = pos - i + 1 < 0 ? 0 : pos - i + 1;
int lastStart = pos + i - 1 >= gems.size() ? gems.size() - i : pos;
for (int k = firstStart; k <= lastStart; ++k) {
bool flag = true;
for (int m = 0; m < sortedJew.size(); ++m) {
if (find(gems.begin() + k, gems.begin() + k + i, sortedJew[m].name) == gems.begin() + k + i) {
flag = false;
break;
}
}
if (flag) {
answer.push_back(k + 1);
answer.push_back(k + i - 1 + 1);
return answer;
}
}
}
}
}
return answer;
}
구간은 보석의 종류를 최소 하나 이상씩 포함해야 한다. 그런 구간의 최소 길이를 구하는 문제.
5 중 for 문을 쓰니.. 당연히 시간초과가.. 7000ms 까지 가다니 ㅠㅠ.. 이 엄청나게 비효율적인 이 풀이를 나중에 다시 볼 미래의 나를 설명해보자면..😅 gems 구간의 길이가 가질 수 있는 최소값은 보석 종류의 개수가 될 것이다. 예를 들어 보석 종류가 4 가지인데 그 4 가지가 야무지게 딱 하나씩만 다 들어있는 구간이라면 그 구간의 길이는 4 가 될 것이다. 그리고 gems 구간의 길이가 가질 수 있는 최대값은 gems 배열의 전체 길이가 된다. 배열의 처음부터 끝까지를 전체를 구간으로 잡아야 모든 보석의 종류를 하나 이상 포함할 수 있는 경우가 되겠다. 아무튼 이 풀이는 최소 길이가 될 수 있는 보석의 종류 개수 (sortedJew.size()) 부터 gems 배열 전체의 길이까지 증가시키면서 처음으로 보석의 종류를 모두 포함하는 구간을 찾아내면 그것을 답으로 도출하는 풀이이다. 최소 길이부터 잡아 차례차례 따지므로 처음 발견한 그 구간은 무조건 보석의 종류를 모두 포함하는 최소 길이 구간이라는 것이 보장된다.
- 첫 번째 for문
- 구간이 가질 수 있는 최소 길이부터 최대 길이 사이의 모든 정수를 순차탐색
- 이런 크기를 가지는 for 문에서 여러 for 문을 사중으로 돌렸으니 당연히 시간초과가 날 수 밖에..
- 구간이 가질 수 있는 최소 길이부터 최대 길이 사이의 모든 정수를 순차탐색
- 두 번째 for문
- 보석의 종류마다.
- 세 번쨰 for문
- 해당 보석의 인덱스마다. 해당 보석의 인덱스를 포함하는 “구간들”을 이번 첫번째 for문의 길이로 설정하여 구해볼 것.
firstStart이 구간들 중 가장 앞설 수 있는 시작점lastStart이 구간들 중 가장 마지막에 있을 수 있는 시작점- 예를 들어 [1,2,3,4,5,6,7] 에서 6 이라는 보석을 구간에 꼭 포함하기로 하였고 현재 잡으려는 구간 길이가 3 이라면 [4,5,6] [5,6,7] 이 이번 구간 후보가 될 것이다. firstStart 는 4, lastStart 는 5.
- 해당 보석의 인덱스마다. 해당 보석의 인덱스를 포함하는 “구간들”을 이번 첫번째 for문의 길이로 설정하여 구해볼 것.
- 네 번째 for문
- 구간들 하나하나
- 다섯 번째 for문
- 해당 구간에 보석의 종류가 다 있는지를 검사. 다 있다면 종료.
- 여담으로 find 함수는 탐색하려는 데이터가 없다면 범위의 끝으로 넘긴 파라미터를 리턴한다. 그래서 리턴값이 gems.begin() + k + i 와 같다면 못 찾은 것으로 간주.
찾자마자 바로 빠져나온다하더라도 만약에 바로 못 찾고 최대 100,000 크기인 gems를 거의 끝까지 순회할 때 까지도 리턴 되지 못한다면? 당연히 O(N^5)에 도달할 것이다. 가장 작은 빈도수의 보석부터 구간을 잡고 진행하니 금방 리턴될 것이란 생각에 5 중 for문도 무리 없지 않을 까 하고 이런 풀이를 했는데 난 반성해야돼!!! 무대뽀로 금방 찾을 것을 기대하고 이런 풀이를 했다니.. 무조건 이렇게 입력 크기가 크다면 어떤 상황이든 안정적으로 반드시 O(N), 적어도 O(NlogN) 를 넘지 않도록 알고리즘을 짜야한다.
🔥 2 차 풀이 ❌
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
struct Jewelry {
string name;
set<int> positions;
int size;
};
bool compare(const Jewelry& a, const Jewelry& b) {
if (a.size == b.size)
return *(a.positions.begin()) < *(b.positions.begin());
return a.size < b.size;
}
vector<int> solution(vector<string> gems) {
vector<int> answer(2);
unordered_map<string, set<int>> kindOfJew;
vector<Jewelry> sortedJew;
for (int i = 0; i < gems.size(); ++i)
kindOfJew[gems[i]].insert(i);
for (auto& jew : kindOfJew) {
int n = jew.second.size();
sortedJew.push_back({ jew.first, jew.second, n });
}
sort(sortedJew.begin(), sortedJew.end(), compare);
Jewelry jew = sortedJew[0]; // 가장 빈도수가 작고 가장 왼쪽에 있는 보석 하나를 결정.
int minLength = 100000;
for (const int& pos : jew.positions) { // 가장 빈도수가 작고 가장 왼쪽에 있는 보석의 인덱스들. 이 보석이 각각 포함되는 구간들을 전부 검사 (인덱스 하나하나가 pos)
int start = pos;
int end = pos;
for (int i = 1; i < sortedJew.size(); ++i) { // 보석의 종류 하나하나마다 결정
// pos 의 왼쪽에서 이번 보석의 종류를 찾으면 그 위치를 left 에 기록. (구간의 시작)
// 못 찾으면 left = -1 인 상태로 빠져나올 것이다.
int left;
for (left = pos - 1; left >= 0; --left) {
if (sortedJew[i].name == gems[left])
break;
}
// pos 의 오른쪽에서 이번 보석의 종류를 찾으면 그 위치를 right 에 기록. (구간의 시작)
// 못 찾으면 right = gems.size() 인 상태로 빠져나올 것이다.
int right;
for (right = pos + 1; right < gems.size(); ++right) {
if (sortedJew[i].name == gems[right])
break;
}
// 왼쪽, 오른쪽에서 둘 다 찾았다면 pos 와 더 가까운 것을 채택
if (left >= 0 && right < gems.size()) {
if (pos - left > right - pos)
left = -1; // 오른쪽이 더 가깝다면 왼쪽은 못 찾은 것으로 처리
else
right = gems.size(); // 왼쪽이 더 가깝다면 오른쪽은 못 찾은 것으로 처리
}
if (left >= 0) // 왼쪽을 찾았다면
if (left < start) // 근데 왼쪽이 start 보다 더 왼쪽에 있다면 이제 새롭게 start 값을 left 로 수정
start = left;
if (right < gems.size()) // 오른쪽을 찾았다면
if (right > end) // 근데 오른쪽이 end 보다 더 오른쪽에 있다면 이제 새롭게 end 값을 right 로 수정
end = right;
}
// "이번 pos" 가 속한 구간들 중 모든 보석을 포함하는 가장 짧은 구간
if (minLength > end - start + 1) {
// answer 에 저장해두기
answer[0] = start + 1;
answer[1] = end + 1;
minLength = end - start + 1;
}
}
return answer;
}
결론적으로 처참하게 틀린 풀이이다. ㅎㅎㅎㅎㅎ
가장 빈도수가 작고 가장 왼쪽에 있는 보석 하나를 후보로 잡았다..(그 보석이 있는 위치들은 pos) 모든 보석의 종류들을 전부 포함하되 각각 최소의 개수로서 담는 구간을 찾아야하기 때문에 최대한 연산량을 줄이기 위하여 가장 빈도수가 적은 보석을 택하였다. 그 보석의 위치들 중 차례로 택하여 그 위치를 중심으로 모든 보석을 최소로 다 포함하는 [left, right] 구간을 잡는다.
3 중 for문으로 줄였고 딱 하나의 보석을 잡아서 그 보석의 위치들을 기준으로 구간을 잡는다는점에서 시간복잡도가 나쁘지 않지 않을까 하고 생각했지만.. 첫 번째풀이보단 시간적인면에서 더 낫지만 잘못된 판단이였다.
앞으로 고쳐야할 습관 📢 시간 효율성이 나름 이렇게 하면 괜찮아지지 않을까..? 대충..? 하고 생각하지 말기!!! 정말 정확하게, 확실하게 이 시간복잡도가 될 수 있겠구나 하는 풀이를 생각하자. 시간만 버린다. 이 문제는 입력 크기가 최대 100,000 이기에 O(N)으로 (혹은 O(NlogN)) 으로 풀어야 하는 문제라는 것을 염두해두고 이 시간복잡도를 확실하게 지킬 풀이로 접근했어야 했다.
🔥 3 차 풀이 ⭕ (투포인터 알고리즘 사용)
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer(2);
set<string> kind;
for (int i = 0; i < gems.size(); ++i)
kind.insert(gems[i]); // set은 중복을 제거하므로 최종적으로 kind.size() 는 보석의 종류 개수가 된다.
int minLen = 100000; // 구하는 구간
unordered_map<string, int> count; // while문 반복 내에서 매 반복마다 해당 구간의 보석 종류 개수를 이 unordered_map 으로 셀 것이다. (Key 정렬 필요 없으므로 map 보단 더 빠른 unordered_map 채택)
int i;
int start = 0;
int end = 0;
while (true) {
// end 포인터 업뎃 👉 보석의 모든 종류를 하나 이상씩 포함하는 곳까지
for (i = end; i < gems.size(); ++i) {
count[gems[i]]++;
if (count.size() == kind.size()) {
end = i;
break;
}
}
// end 포인터가 업뎃되지 못하고 빠져나와 gems 를 넘어섰다면 더 이상 업뎃할 구간 없으므로 종료
if (i == gems.size())
break;
// start 포인터 업뎃 👉 보석의 모든 종류를 다 포함하되 이 보석을 제외하면 모든 종류를 포함할 수 없다싶은 곳 까지
for (i = start; i < gems.size(); ++i) {
if (count[gems[i]] == 1) {
start = i;
break;
}
else count[gems[i]]--;
}
// 현재 완성된 구간의 길이가 minLen 현재까지 구한 구간 최소 길이보다 작으면 minLen 업데이트
if (end - start < minLen) {
answer[0] = start + 1;
answer[1] = end + 1;
minLen = end - start;
}
// 이제 새로운 구간을 다음 반복부터 잡아야한다.
// start, end 모두 1 씩 증가시킴 (start 와 end 의 다음 "후보" 시작점)
// gems[start] 는 제외해야하므로 count 에서 제거
count.erase(gems[start]);
start++;
end++;
}
return answer;
}
투포인터 알고리즘을 사용하여 O(N) 시간복잡도로 풀 수 있다.
투포인터 알고리즘 👉 어떤 특정 조건을 만족하는 🔥구간🔥을 구할 때 O(N) 으로 풀 수 있도록 도와주는 알고리즘
2 개의 포인터를 사용하여 구간의 길이를 가변적 적으로잡아가며 특정 조건을 만족하는 구간을 찾는다. 모든 연속 구간을 잡는다면 O(N^2)이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 풀 수 있다. 어떤 구간을 찾는 문제일 때 입력 크기가 아주 크다면 투 포인터 알고리즘 을 고려하여 풀자! 2 개의 포인터 中 right 포인터는 어떤 조건일 때 증감시키고, left 포인터는 어떤 조건일 때 증감시킬지 결정해야 한다.
- 모든 보석을 포함하되 최소로 포함하도록 구간의 start 와 end 를 확정짓는다.
- 현재의 start, end 가 가질 수 있는 값 내에서 찾는다.
- 현재 확정지은 구간이 현재까지 찾은 구간들 중 최소 길이가 될 수 있는지 검사한다.
- 다음 구간을 찾으러
start++,end++
보석의 종류 4 가지 👉 “RUBY”, “DIA”, “EMERALD”, “SAPPHIRE”
- 후보 "DIA", "RUBY", "RUBY", "DIA", "EMERALD", "SAPPHIRE", "DIA"
end결정 👉 모든 다이아를 포함하도록 "DIA", "RUBY", "RUBY", "DIA", "EMERALD", "SAPPHIRE", “DIA”start결정 👉 최소로 포함하도록 “DIA”, “RUBY”, "RUBY", "DIA", "EMERALD", "SAPPHIRE", “DIA”- 현재의 구간 길이 4.
minLen은 4 로 업데이트 (내가 end - start + 1 가 아닌 그냥 end - start 로 코딩했기 때문에 사실 3 이긴 하다)
- 후보 “DIA”, “RUBY”, “RUBY”, "DIA", "EMERALD", "SAPPHIRE", "DIA"
end결정 👉 gems 의 끝에 도달할 때까지 모든 다이아를 포함하지 못해 종료!
답은 4 가 된다.
https://ansohxxn.github.io/algorithm/twopointer/
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기