프로그래머스 - 보석 쇼핑 (Lv.3)

문제 링크

• 보석 쇼핑

구현(효율성 테스트 5개 Fail)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool cmp(string s1, string s2){
    return s1<s2;
}

void set_gem_no_overlap(vector<string>& cpy_gems, vector<string>& gems_no_overlap){
    string ref = cpy_gems[0];
    gems_no_overlap.push_back(ref);
    for(int i=1; i<cpy_gems.size(); i++){
        if(ref != cpy_gems[i]){
            ref = cpy_gems[i];
            gems_no_overlap.push_back(ref);
        }
    }
}

// 진열대 번호는 1번부터 시작
void set_gems_idx(vector<string>& gems, vector<string>& gems_category, vector<int>& gems_idx){
    for(int dsp_num=0; dsp_num<gems.size(); dsp_num++){
        for(int ctg=0; ctg<gems_category.size(); ctg++){
            if(gems[dsp_num] == gems_category[ctg]){
                gems_idx[dsp_num+1] = ctg;
                break;
            }
        }
    }
}

vector<int> get_shortest_range(vector<int>& num_gems, vector<int>& gems_idx){
    int len = gems_idx.size();
    int start = 1;
    int end;
    num_gems[gems_idx[start]] += 1;
    
    int ctg_len = num_gems.size();
    vector<bool> visited(ctg_len, false);
    visited[gems_idx[1]] = true;
    int ctg_cnt = 1;
    bool flag = true;
    for(int i=2; i<len; i++){
        int ctg_idx = gems_idx[i];
        num_gems[ctg_idx] += 1;
        if(visited[ctg_idx]==false){
            ctg_cnt++;
            visited[ctg_idx] = true;
        }
        if((ctg_cnt==ctg_len) && flag) {
            end = i;
            flag = false;
            break;
        }
    }
    
    vector<int> ret = {start, end};
    int nstart;
    int nend;
    int diff = end - start + 1;
    while(end<len && start<end){
        nstart = start + 1;
        nend = end;
        int ctg_idx = gems_idx[start];
        num_gems[ctg_idx] -= 1;
        if(num_gems[ctg_idx]==0){
            num_gems[ctg_idx] += 1;
            end+=1;
            if(end<len)
                num_gems[gems_idx[end]] += 1;
        }
        else{
            if(diff > (nend-nstart+1)){
                ret[0] = nstart;
                ret[1] = nend;
                diff = nend-nstart+1;
            }
            start = nstart;
        }
    }
    return ret;
}

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    vector<string> cpy_gems = gems;
    sort(cpy_gems.begin(), cpy_gems.end(), cmp); // 오름차순 정렬
    
    vector<string> gems_category;
    set_gem_no_overlap(cpy_gems, gems_category);
    int ctg_len = gems_category.size();
    if(ctg_len == 1) {
        answer.push_back(1);
        answer.push_back(1);
        return answer;
    }
    
    // 진열대 번호는 1번부터 시작
    // gems_idx[num]은 num번 진열대에 존재하는 보석의 인덱스값
    vector<int> gems_idx(gems.size()+1, 0);
    set_gems_idx(gems, gems_category, gems_idx);
    
    // 현재 구간에서 존재하는 보석별 개수 (0 ~ ctg_len-1)
    vector<int> num_gems(ctg_len, 0);
    answer = get_shortest_range(num_gems, gems_idx);
    
    return answer;
}

개선한 점

• 보석 이름을 정수화하여 인덱스로 표현하는 과정에서 시간 복잡도가 O(n^2)이 된다고 판단
• map 자료구조를 활용하여 {“보석 이름”, 현재 칸에서 개수} 의 딕셔너리 형태로 자료를 다룰 수 있도록 한다.

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

using namespace std;

int get_ctg_len(vector<string> cpy_gems){
    int len = cpy_gems.size();
    sort(cpy_gems.begin(), cpy_gems.end());
    int ctg_len = 1;
    string ref = cpy_gems[0];
    for(int i=1; i<len; i++){
        if(ref != cpy_gems[i]){
            ctg_len++;
            ref = cpy_gems[i];
        }
    }
    
    return ctg_len;
}

vector<int> solution(vector<string> gems) {
    vector<int> answer = {1, 1};
    int ctg_len = get_ctg_len(gems);
    int gems_len = gems.size();
    int dsp_start = 1;
    int dsp_end;
    
    map<string, int> dict;
    map<string, int>::iterator iter;
    string gem;
    for(int i=0; i<gems_len; i++){
        gem = gems[i];
        iter = dict.find(gem);
        if(iter==dict.end()) // 찾을 수 없다면 end 반환
            dict[gem] = 1;
        else
            dict[gem]++;
        if(dict.size()==ctg_len){
            dsp_end = i+1;
            break;
        }
    }
    
    // 보석 종류가 1개라면 [1,1] 반환
    if(dict.size()==1)
        return answer;
    
    // 보석 종류가 2개 이상인 경우
    int nstart, nend;
    int diff = dsp_end - dsp_start + 1;
    answer[0] = dsp_start; answer[1] = dsp_end;
    while(dsp_start<dsp_end && dsp_end <= gems_len){
        nstart = dsp_start + 1;
        nend = dsp_end;
        gem = gems[dsp_start-1];
        dict[gem]--;
        if(dict[gem]==0){
            dict[gem]++;
            dsp_end++;
            if(dsp_end<=gems_len)
                dict[gems[dsp_end-1]]++;
        }
        else{
            if(diff > (nend - nstart + 1)){
                diff = nend - nstart + 1;
                answer[0] = nstart;
                answer[1] = nend;
            }
            dsp_start = nstart;
        }
    }
    return answer;
}

• map.find(str) 함수는 str을 찾지 못할 경우 map.end() 반복자를 반환한다.