⚙️ 알고리즘 분류 : 투포인터
🔠 언어 : c++
🤫 힌트.
map을 잘 활용하자.
✏️ 풀이.
투포인터 알고리즘만 알면 풀 수 있는 문제다.
카카오 인턴 문제에 대한 해설이 카카오 테크 블로그에 올려져있어서 이를 참고했다.
(아래 링크의 3번 문제다.)
https://tech.kakao.com/2020/07/01/2020-internship-test/
투포인터는
연속된 구간합을 구할 때자주 사용된다.
특히 배열의 크기가 클 경우,O(n)의 시간복잡도로 효율적이게 만들 수 있다.
준비물 : start, end (보통 left, right라고 이름 짓는데, 그건 본인 기호!)
➡️ 구간의 index를 나타내는 값이다. start는 첫 index, end는 마지막 index.
➡️ while 문을 사용하는데, 조건은 보통 start<=end && end<배열의 크기 이렇게 설정한다.
문제 풀이 단계
(1) start=0, end=0. [start, end]가 구간이다.
(2-1) if 구간의 원소들이 조건을 만족하지 못하면
➡️ end 값을 늘린다.
➡️ end index가 가리키는 값을 구간합에 포함시킨다.
(2-2) if 구간의 원소들이 조건을 만족하면
➡️ start 값을 늘린다.
➡️ start index가 가리키는 값을 구간합에서 뺀다.
➡️ 정답 값을 업데이트 한다.
⚠️ 헤맨 부분.
1) segmentation fault
segmentation fault로 한 시간을 날린 것 같다.
map에서 erase 하는 코드를 주석처리 했을 때 에러가 발생해서,
'도대체 어떻게 out of index가 발생하지...?'라는 생각을 했다.
결국 erase에서 발생한 게 아니라, end 값에서 발생한 거였다.
erase를 하지 않으면 map에서 지워지지 않아서, 늘 map에는 모든 종류 개수만큼 들어있게 된다.
그 때문에 end 값이 증가할 일이 없어서 에러가 발생하지 않은 거였다.
그리고 이 문제 풀면서 안 건데,
m["A"]++ ➡️ m["A"]-- ➡️ cout<<m.size();
를 하게 되면 1이 나온다. key의 value가 0이라도 아예 삭제하지 않으면 그대로 남는다.
2) 정답을 업데이트 해봅시다.
정답이 업데이트 되는 조건은 아래와 같다.
- map에 모든 종류의 보석이 있어야 한다.
- 기존 정답보다 구간이 짧아야 한다.
- 기존 정답과 구간이 같다면, start 값이 더 작아야 한다.
이렇게 간단한 걸... 정리를 못해서 헤매고 있었다.. 우잉ㅠㅠ
👩🏻💻 코드.
#include <string>
#include <vector>
#include <map>
#define MX 999999999
using namespace std;
map<string, int> m;
vector<int> solution(vector<string> gems) {
vector<int> answer(2,0);
// 보석 종류의 개수를 구한다.
for(int i=0; i<gems.size(); i++) m[gems[i]]=1;
int kind=m.size();
m.clear();
// 여기서부터 map의 의미는 <보석 이름, 보석 개수>.
// start는 답으로 선택할 구간의 왼쪽, end는 오른쪽이다.
int start=0, end=0, mn_len=gems.size();
m[gems[0]]++;
while(start<=end && end<gems.size()){
int sz=m.size();
if(sz<kind) {
// ⚠️ segmentation fault 주범
// while문 조건은 end가 gems의 최대 index를 넘으면 안 되는 거였다.
// 그래서 end가 (gems.size()-1) 일 때,
// 여기에 1을 더하면 out of index가 발생하는 거였다.
if(end+1==gems.size()) break;
m[gems[++end]]++;
continue;
}
if(sz==kind){
// 얘도 날 너무 힘들게 했다ㅠ
// 모든 종류를 포함한다고 다 답이 될 순 없다.
// 문제에서 주어진 대로, 구간 길이가 같은 경우엔 start가 작은 것이 우선이기에
// 구간 길이가 더 짧은 경우에만 업데이트 시켜줘야 한다.
if(end-start<mn_len) {
mn_len=end-start;
answer[0]=start+1, answer[1]=end+1;
}
if(m[gems[start]]>1) {
m[gems[start++]]--;
}
// 만약 하나 남은 보석을 빼야한다면,
// 정확한 map의 크기를 위해서 해당 보석을 지워야 한다.
else if(m[gems[start]]==1){
m.erase(gems[start++]);
}
}
}
return answer;
}😎 후기.
전에 한 번 풀었을 땐 블로그의 답지를 봤는데 무슨 소리인지 이해를 못했다.
이번에 풀 땐 블로그를 보지 않고, 카카오 공식 블로그에 있는 풀이만 보고 풀어봤다.
훨씬 더 직관적으로 문제를 풀 수 있었다.
풀면서 segmentation fault가 계속 나서 괴로운 문제였다ㅠㅠ
vector의 원소를 삭제하는 코드를 지워보니 잘 되어서 처음엔 삭제할 때 index를 잘못 건드렸나 싶었는데,
그게 아니었다... 예상과는 다른 곳에서 문제가 나와 당황했었다.
늘 유심히 살펴보자.
풀고 나서 보니, 투포인터를 잘 이해할 수 있는 문제라고 생각한다.
얘는 꼭 풀어보자!
