투 포인터 (Two Pointers Algorithm) (feat. 프로그래머스 - 보석 쇼핑)

어떤 알고리즘인지 모르고 있었지만 이번 기회에 문제를 풀면서 알게 된 알고리즘.

아직은 어떤 타이밍에 이 알고리즘을 써야 하는지 모르지만, 연습하다보면 알게 될것이라 믿는다.....ㅠㅠ

 

방법은 다음과 같다.

1. 두개의 포인터가 있다. 본인은 front, end로 정한다.

2. 두 포인터중 하나라도 배열의 크기를 넘어가게 되면 그대로 끝!

3-1. 두 포인터의 범위에서 모자라면 end로 범위를 늘려준다.

3-2. 두 포인터의 범위에서 넘치게 되면 front로 범위를 줄여준다.

 

생각보다 간단한 알고리즘. 그런데 시간복잡도는 O(N)밖에 안된다. 원래대로 하려면 for문을 두개 쓰는 등 해야하는데!!!  빠르자너.....!!!

 

예시를 들어보자. (초기 : front = 0, end = 0, answer = 9)

front	↓
arr[i]	1	2	3	4	2	6	1	3	2
end	↑

합이 9인 구간을 모조리 찾아보자. 우선 초기에는 합이 1이다. (sum = 1)

sum이 answer보다 한참 모자라므로 end로 범위를 늘려준다.

front	↓
arr[i]	1	2	3	4	2	6	1	3	2
end		↑

여기서는 sum = 3이다. 

역시 한참 모자라므로 end 범위를 늘려준다. (빠른 설명을 위해 arr[3]까지 늘려줘보자!!!)

front	↓
arr[i]	1	2	3	4	2	6	1	3	2
end				↑

여기서는 sum = 10이다.

이런...!! 넘었잖아....!!!!

front로 구간을 줄여주자!!!!

front		↓
arr[i]	1	2	3	4	2	6	1	3	2
end				↑

front를 줄여주고 보니 구간합이 9가 되었다.

answer의 값을 찾았다!! 좋아좋아..... 우선 첫번째 구간 (1, 3)이 구해졌다. 계속 해보자!!

front		↓
arr[i]	1	2	3	4	2	6	1	3	2
end					↑

구간합이 10이 되면서 answer = 8보다 커졌다. 다시 줄여주자.

front			↓
arr[i]	1	2	3	4	2	6	1	3	2
end					↑

오..... 또 찾았다... 두번째 구간 (2, 4)!!! 계속 계속!!!

front			↓
arr[i]	1	2	3	4	2	6	1	3	2
end						↑

다시 커졌다. 구간합이 15씩이나 되다니....

역시 빠른 진행을 위해 지금까지 했던 방법으로 찾아보면!

front					↓
arr[i]	1	2	3	4	2	6	1	3	2
end							↑

세번쨰 구간 발견!!!! (4, 6) 구간!!!

이 이후에도 더 있나 찾아보자!!!! (는 없다..ㅎㅎㅎㅎ)

 

......

 

front							↓
arr[i]	1	2	3	4	2	6	1	3	2
end									↑

마지막은 이렇게 된다. 여기서 구간합은 6인데 end를 늘려주게 되면 배열을 넘어가게 되므로 종료!!!!!!

 

결과는 (1, 3), (2, 4), (4, 6) 세 구간이 됬다.

 

이를 이용해서 다음 문제를 풀었다.

<문제>
programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

오우... 망할 어피치....

내가 코딩을 잘 못했을때 처음 마주쳤는데 이런...어피치... 나를 힘들게 해.....

그리고 두번째 어피치와의 설욕전에서는 문제는 풀었지만 효율성에서 꽝이었다..

오늘! 어피치와의 설욕전 마지막 이었다. 하하하하하하하하하하하하

 

<코드>

#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    map<string, int> m;
    set<string> s;
    for(int i = 0; i < gems.size(); i++) {
    	s.insert(gems[i]);
	}
	
	int num_of_gems = s.size();
    int fnt = 0, end = 0, cnt = 0;
    int min_fnt = 0, min_end = 0, min_length = gems.size() + 1;
    
    while(end != gems.size()) {
    	if(cnt != num_of_gems) {
    		if(!m[gems[end]]) {
    			m[gems[end]] = 1;
    			cnt++;
    			end++;
			}
			else {
				m[gems[end]]++;
				end++;
			}
		}
		else {
			if(min_length > end - fnt + 1) {
				min_length = end - fnt + 1;
				min_end = end;
				min_fnt = fnt;
			}
			
			if(m[gems[fnt]] == 1) {
				cnt--;
				m[gems[fnt]] = 0;
                fnt++;
			}
			
			else {
				m[gems[fnt]]--;
				fnt++;
			}
		}
	}
    
	if(min_fnt == 0 && min_end == 0) {
	    min_end = gems.size();
	}
	
    answer.push_back(min_fnt+1);
    answer.push_back(min_end);
    return answer;
}

흠.... 뭐가 이렇게 길지.....

 

방법은 다음과 같았다.

1. set을 사용해서 보석의 종류가 몇가지 되는지 빠르게 확인했다.

2. map을 사용해서 구간 안에 보석이 몇개 있는지 저장해뒀다.

3. 투포인터를 사용해서 구간 내에 보석이 몇 종류가 있는지 계속 확인했다.

 

이런..!!! 그런데 어피치가 나의 발목을 잡았다. (그냥 쇼핑 안하면 안되니.......??? ㅠㅠㅠㅠㅠ)

 

gems = ["A", "A", "C"];

이 경우..... 왜 틀렸지.... 싶었다.

생각해보니까..... end가 2일때 cnt가 보석의 갯수 만큼 되지만 while문을 빠져나가버린다!!!!!

그래서!!!!!! while문 안에 있는 else문을 가지 않는다!!!!!

따라서 while 밖에 나와서도 똑같이 처리해주도록 했다.

 

#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    map<string, int> m;
    set<string> s;
    
    for(int i = 0; i < gems.size(); i++) {
    	s.insert(gems[i]);
	}
	
	int num_of_gems = s.size();
    int fnt = 0, end = 0, cnt = 0;
    int min_fnt = 0, min_end = 0, min_length = gems.size() + 1;
    
    while(end != gems.size()) {
    	if(cnt != num_of_gems) {
    		if(!m[gems[end]]) {
    			m[gems[end]] = 1;
    			cnt++;
    			end++;
			}
			else {
				m[gems[end]]++;
				end++;
			}
		}
		else {
			if(min_length > end - fnt + 1) {
				min_length = end - fnt + 1;
				min_end = end;
				min_fnt = fnt;
			}
			if(m[gems[fnt]] == 1) {
				cnt--;
				m[gems[fnt]] = 0;
                fnt++;
			}		
			else {
				m[gems[fnt]]--;
				fnt++;
			}
		}
	}
	if(min_fnt == 0 && min_end == 0) {
	    min_end = gems.size();
	}
	while(cnt == num_of_gems) {
		if(min_length > end - fnt + 1) {
			min_length = end - fnt + 1;
			min_end = end;
			min_fnt = fnt;
		}
		if(m[gems[fnt]] == 1) {
			cnt--;
			m[gems[fnt]] = 0;
            fnt++;
		}	
		else {
			m[gems[fnt]]--;
			fnt++;
		}
	}
    answer.push_back(min_fnt+1);
    answer.push_back(min_end);
    return answer;
}

음~ 좋아요~ 아주~ 좋아요~

이로써 어피치와의 설욕전을 이길 수 있었다. (뿌듯)

 

<Testing 코드>

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    map<string, int> m;
    set<string> s;
    
    for(int i = 0; i < gems.size(); i++) {
    	s.insert(gems[i]);
	}
	
	int num_of_gems = s.size();
    int fnt = 0, end = 0, cnt = 0;
    int min_fnt = 0, min_end = 0, min_length = gems.size() + 1;
    
    while(end != gems.size()) {
    	if(cnt != num_of_gems) {
    		if(!m[gems[end]]) {
    			m[gems[end]] = 1;
    			cnt++;
    			end++;
			}
			else {
				m[gems[end]]++;
				end++;
			}
		}
		else {
			if(min_length > end - fnt + 1) {
				min_length = end - fnt + 1;
				min_end = end;
				min_fnt = fnt;
			}
			if(m[gems[fnt]] == 1) {
				cnt--;
				m[gems[fnt]] = 0;
                fnt++;
			}		
			else {
				m[gems[fnt]]--;
				fnt++;
			}
		}
	}
	if(min_fnt == 0 && min_end == 0) {
	    min_end = gems.size();
	}
	while(cnt == num_of_gems) {
		if(min_length > end - fnt + 1) {
			min_length = end - fnt + 1;
			min_end = end;
			min_fnt = fnt;
		}
		if(m[gems[fnt]] == 1) {
			cnt--;
			m[gems[fnt]] = 0;
            fnt++;
		}	
		else {
			m[gems[fnt]]--;
			fnt++;
		}
	}
    answer.push_back(min_fnt+1);
    answer.push_back(min_end);
    
    cout << answer[0] << " " << answer[1] << endl;
    
    return answer;
}

int main(void)
{
	int N;
	cin >> N;

	vector<string> gems;
	string temp;

	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		gems.push_back(temp);
	}

	solution(gems);
	
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

젠장. 어피치.