반응형
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/67258
문제
풀이 및 코드 (투포인터 알고리즘)
이 문제를 사용하기 위해 투포인터 알고리즘을 사용하였습니다.
투포인터 알고리즘이란?
https://bendeng-life.tistory.com/130
투포인터 알고리즘이란 두 포인터를 이용하여 특정한 합을 가지는 부분 연속 수열의 합을 구할때 자주 사용하는 알고리즘이라고 할 수 있습니다.
이런 문제에서 저는 아무생각없이 dfs로 진입하였다가 시간초과로 뚜들겨 맞고 투포인터 알고리즘으로 호다닥 바꾸었습니다..ㅋㅋㅋㅋㅋㅋㅋ
문제를 예시인 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]를 기준에 뒤에 RUBY를 추가한 그림과 함께 보겠습니다.
즉, 조건에 충족(잼의 종류== 현재 잼의 종류) 할때까지 end 인덱스를 미루면서 충족을 할때는!!
start인덱스를 다시 밀게 되면서 반복합니다.
end인덱스가 마지막 그림인 start인덱스가 sapphire일때(마지막 그림, 조건을 충족했으니 start인덱스++을했음) 조건을 충족하지 않으니 end인덱스++를 하게 되면서 반복문을 이탈하는 구조를 가지게 하였습니다.
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer;
map<string, int> m;
int start = 0; // 시작지점
int end = 0; // 끝나는 지점
int gemCount = 0; // 보석 현재 갯수
int startAns, endAns; // 위치 임시 저장
int len = 100000;
// 보석 종류의 갯수 세기
for (int i = 0; i < gems.size(); i++) {
m[gems[i]] = 0;
}
int gemType = m.size(); // 보석의 종류 갯수
while (1) {
if (gemType == gemCount) {
// 최소 길이인지 확인하고 갱신
if (end - start < len) {
startAns = start;
endAns = end;
len = end - start;
}
if (m[gems[start]] > 1) {
m[gems[start]]--;
start++;
}
else {
m[gems[start]]--;
start++;
gemCount--;
}
}
else {
// 종류와 현재 갯수가 다를 때, end를 이동시키면서 현재 종류와 같아지도록 함
if (end == gems.size())
break;
if (m[gems[end]] == 0)
gemCount++;
m[gems[end]]++;
end++;
}
}
answer.push_back(startAns + 1);
answer.push_back(endAns);
return answer;
}
반응형
'알고리즘 > c++ 프로그래머스' 카테고리의 다른 글
[프로그래머스 징검다리 건너기] c++ (풀이,코드,이분탐색) (0) | 2023.07.03 |
---|---|
[프로그래머스 스티커 모으기] c++ (풀이, 코드, DP) (0) | 2023.06.29 |
[프로그래머스 불량 사용자] c++ (풀이,코드,dfs,set) (0) | 2023.06.27 |
[프로그래머스 베스트앨범] c++ (풀이, 코드, map과vector 정복) (0) | 2023.06.26 |
[프로그래머스 기지국 설치] c++ (풀이,코드,그리디) (0) | 2023.06.26 |
댓글