반응형
728x170
어렵다.
처음에 생각하기는 어렵지 않은데 효율성 문제가 어렵다.
https://programmers.co.kr/learn/courses/30/lessons/67258
효율성이 어렵다
생각나는대로 for문으로 한 번 풀어봤다.
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> solution(vector<string> gems){
vector <int> answer;
vector <pair<int, pair<int,int>>> rank; // 길이 , 시작, 도착
set <string> s(gems.begin(), gems.end()); // gems의 종류를 알기 위함.
int size_gem = gems.size(); // 총 탐색해야하는 보석 수
//시작지점
for(int i = 0; i<size_gem; i++){
vector<string> kind(s.begin(), s.end()); // 구간을 탐색하면서 체크하기 위함
string start = gems[i];
auto it = find(kind.begin(), kind.end(), start); // 해당 iterator 반환(없으면 kind.end()를 반환)
// 사실 start일 때 못찾으면 말이 안됨
if(it != kind.end()){
kind.erase(it); // 해당 보석 종류 삭제(it 가 kind.end()면 그냥 아무일 안일어남)
}else{
continue;
}
//도착지점
for(int j = i+1; j<size_gem; j++){
//비어있다면 이전 검색에서 모든 종류의 보석을 뽑은 것임 (다른 시작지점을 찾아야함 -> break)
if(kind.empty()){
int length = (j-i-1);
rank.push_back({length, {i+1,j}}); //배열은 0부터시작하지만 보기는 1부터 시작함
break;
}
// 비어있지 않으면 계속 뽑아야함
string end = gems[j]; // 현재 고름
it = find(kind.begin(), kind.end(), end); // 해당 iterator 반환(없으면 kind.end()를 반환)
if(it != kind.end()){
kind.erase(it); // 해당 보석 종류 삭제(it 가 kind.end()면 그냥 아무일 안일어남)
//삭제했을 때 비어있으면 거기까지도 기록해야함
if (kind.empty()) {
int length = (j - i - 1);
rank.push_back({ length, {i + 1,j+1} }); // 여기선 현재니까 j+1로 기록함
break;
}
}else{
continue;
}
}
}
sort(rank.begin(), rank.end());
answer.push_back(rank[0].second.first);
answer.push_back(rank[0].second.second);
return answer;
}
뭐 접근은 맞았을지 모르나 털려버림
투 포인터 알고리즘을 써야 한다고 한다.
그래서 남의 코드를 잠깐 리뷰해보았다. 그리고 풀었다.
#맞은 풀이
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <map> // 보석 종류
#include <climits>
using namespace std;
vector<int> solution(vector<string> gems){
vector <int> answer(2); // 크기 2로 설정
set <string> s(gems.begin(), gems.end()); // gems의 종류를 알기 위함.
int size_gem = gems.size(); // 총 탐색해야하는 보석 수
unordered_map<string, int> count; // 보석, 수 (key중복데이터 허용 x -> 중복되어도 오류가 생기진 않고 원소는 늘어나지 않음)
//(인덱스)
int start = 0;
int end = 0;
int m = INT_MAX; // 길이 최솟값 비교
int i;
//투포인터 사용 end 포인터 이동 조건과 start 포인터 이동조건 설정
//end가 더이상 움직이지 못하면(start도 다 움직인 이후에) 종료
while(1){
//1. end부터 움직임
for(i = end; i<size_gem; i++){
count[gems[i]]++; // 해당 종류의 보석 세기
//맵에 들어간 보석의 종류와 모든 보석 종류의 수가 같으면
if(count.size() == s.size()){
end = i; // end포인터는 우선 여기서 멈춤.
break;
}
}
//옮겨도 end가 업데이트 되지 않는 경우 -> end를 뒤로 보내도 조건이 만족하지 않는 경우
if(i == size_gem ) break;
//2. start 움직임
for(i = start; i<size_gem; i++){
//1이면 해당 보석을 빼면 안됨 -> start 갱신
if (count[gems[i]] == 1){
start = i;
break;
}
//해당 지점에서의 보석이 1이 아니라면 start를 더 뺄 수 있음.
else count[gems[i]]--;
}
//end 와 start를 한 번씪 움직여줬으면 해당 길이 조사
int length = end - start;
//현재 최솟값보다 작으면 갱신 -> 같으면 갱신 안해도 되는 것이 먼저나온 것이 우선이기 때문
if(m>length){
m = length;
answer[0] = start + 1; // start 지점
answer[1] = end + 1; //end 지점
}
//이제 다시 start를 움직였으니 end 포인터를 움직여야함
//그러기 위해서 while문 다시 들어가기 전에
//start에 있는 보석은 빼버리고 end를 옮김
//만약 안빼면 start는 바로 멈춤
count.erase(gems[start]);
start++;
end++;
}
return answer;
}
어렵다기보다
end 움직이는 조건
start 움직이는 조건
end가 움직이지 못할 때 조건
3가지를 생각해줘야해서 조금 까다로웠다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1987번, 알파벳 : C++ [CPP] *** (0) | 2021.11.27 |
---|---|
백준, BOJ, 2468번, 안전 영역 : C++ [CPP] *** (0) | 2021.11.27 |
프로그래머스, 네트워크 : C++ [CPP] (0) | 2021.11.19 |
프로그래머스, 정수 삼각형 : C++ [CPP] (0) | 2021.11.18 |
프로그래머스, 가장 큰 정사각형 찾기 : C++ [CPP] (0) | 2021.11.18 |