[programmers] Lv.3 보석 쇼핑(c++)

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    map<string, int> check;
    vector<int> pos;
    for(int i=0; i< gems.size(); i++){
        check[gems[i]] = 0;
        if(i+1 != gems.size() && gems[i] != gems[i+1]) pos.push_back(i);
    }
    
    vector<int> answer = {1, (int)gems.size()};
    if(check.size() == gems.size()) return answer;
    else if (check.size() == 1) return {1, 1};
    
    for(int i=0; i<pos.size(); i++){
        int cnt = 0;
        for(int j=pos[i]; j<gems.size(); j++){
            if(check[gems[j]]==i){
                cnt++;
                check[gems[j]] += 1;
            }
            if(cnt == check.size() && 
               (answer[1] - answer[0] > j-pos[i] || 
                (answer[1]-answer[0] == j-pos[i] && pos[i] < answer[0]))){
                answer = {pos[i]+1, j+1};
                break;
            }else if(j == gems.size()-1 && cnt < check.size()) return answer;
        }
    }
    return answer;
}

 

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

using namespace std;

vector<int> solution(vector<string> gems) {
    map<string, int> check;
    vector<int> pos;
    for(int i=0; i< gems.size(); i++){
        check[gems[i]] = 0;
        if(i+1 != gems.size() && gems[i] != gems[i+1]) pos.push_back(i);
        if(i == gems.size()-2) pos.push_back(i+1);
    }

    set<int> range = {1};
    vector<int> answer = {1, (int)gems.size()};
    if(check.size() == gems.size()) return answer;
    else if (check.size() == 1) return {1, 1};
    
    int cnt = 0;
    for(int p: pos){
        if(check[gems[p]] == 0) cnt++;
        else range.erase(check[gems[p]]);
        range.insert(p+1);
        check[gems[p]] = p+1;
        
        if(cnt == check.size() && answer[1]-answer[0] > *range.rbegin()-*range.begin()) 
            answer = {*range.begin(), *range.rbegin()};
    }
    return answer;
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/67258

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

728x90

---

[접근]

O(n)으로 해결하자!!!는 목표

---

[접근1]

gems를 돌면서, 보석의 종류를 check에 저장하고(나중에 보석의 위치를 저장할 map), 보석이 바뀌는 위치를 저장한다.

(맨 마지막 보석이 바로 전 보석과 종류가 다르면 그것도 저장해주는걸 따로 적어줘야함)

map<string, int> check;
vector<int> pos;
for(int i=0; i< gems.size(); i++){
    check[gems[i]] = 0;
    if(i+1 != gems.size() && gems[i] != gems[i+1]) pos.push_back(i);
    if(i == gems.size()-2) pos.push_back(i+1);
}

---

[접근2]

처음에 range를 1로 설정해두고, 만약 보석 종류의 개수와 gems의 길이가 같다면 처음부터 끝까지 포함해야한다.

만약 보석의 종류 개수가 1이면 gems는 한가지 종류로만 구성되어있을것, 맨 처음 위치만 포함하면된다.

 

앞서 보석이 바뀌는 지점을 저장해둔 pos를 돌면서, gems를 다 포함할 때 까지 cnt를 증가시킨다.

range에 보석의 전 위치가 저장되어있다면 지우고, 새로운 위치를 넣어준다.

(set은 자동 정렬이 되기 때문에 각 보석 위치의 최소와 최대값을 구하기 편하다.)

check는 새로운 보석의 위치로 계속 갱신해준다.

cnt가 보석의 종류의 개수와 같고 range의 최소값과 최대값으로 이루어진 구간이 answer에 들어있는 구간보다 짧으면 answer를 교체해준다.

set<int> range = {1};
vector<int> answer = {1, (int)gems.size()};
if(check.size() == gems.size()) return answer;
else if (check.size() == 1) return {1, 1};

int cnt = 0;
for(int p: pos){
    if(check[gems[p]] == 0) cnt++;
    else range.erase(check[gems[p]]);
    range.insert(p+1);
    check[gems[p]] = p+1;

    if(cnt == check.size() && answer[1]-answer[0] > *range.rbegin()-*range.begin()) 
        answer = {*range.begin(), *range.rbegin()};
}