programmers | 보석 쇼핑

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스

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

using namespace std;

class Jewels {
    private:
        int                 _start;
        int                 _end;
        int                 _min_range;
        int                 _min_start;
        int                 _min_end;
        string              _seek;

    public:
        map<string, int>    map;
        void                init(int start, int end) {
            _start = start;
            _end = end;
            _min_range = _end - _start;
            _min_start = _start;
            _min_end = _end;
        }
        int                 get_start() {
            return _start;
        }
        int                 get_end() {
            return _end;
        }
        void                inc_start() {
            _start++;
        }
        void                inc_end() {
            _end++;
        }
        void                min_save() {
            if (_min_range > _end - _start) {
                _min_range = _end - _start;
                _min_start = _start;
                _min_end = _end;
            }
        }
        void                set_seek(string seek) {
            _seek = seek;
        }
        string              get_seek() {
            return(_seek);
        }
        int                 get_min_start() {
            return _min_start;
        }
        int                 get_min_end() {
            return _min_end;
        }
};

int ft_how_many_kind(vector<string> gems) {
    sort(gems.begin(), gems.end());

    std::vector<string>::iterator it;
    it = unique(gems.begin(), gems.end());
    gems.erase(it, gems.end());
    return gems.size();
}

void ft_init_jewels(vector<string> gems, Jewels &jewels, int num) {
    int i = -1;
    while (42) {
        ++i;
        if (jewels.map.find(gems[i]) == jewels.map.end()) {
            jewels.map.insert(make_pair(gems[i], 1));
            if (jewels.map.size() == num) {
                jewels.init(0, i);
                return ;
            }
        } else {
            jewels.map[gems[i]]++;
        }
    }
}

void ft_left_throw(vector<string> gems, Jewels &jewels) {
    while (42) {
        if ((--jewels.map[gems[jewels.get_start()]]) == 0) {
            jewels.set_seek(gems[jewels.get_start()]);
            jewels.inc_start();
            break;
        } else {
            jewels.inc_start();
            jewels.min_save();
        }
    }
}

int ft_right_search(vector<string> gems, Jewels &jewels) {
    string seek = jewels.get_seek();
    while (42) {
        jewels.inc_end();
        if (jewels.get_end() == gems.size()) {
            return (false);
        }
        else if (gems[jewels.get_end()] != seek) {
            jewels.map[gems[jewels.get_end()]]++;
        } else {
            jewels.map[gems[jewels.get_end()]]++;
            jewels.min_save();
            return (true);
        }
    }
}

vector<int> ft_full_search(vector<string> gems, int num_jewel) {
    Jewels jewels;

    ft_init_jewels(gems, jewels, num_jewel);
    int i = 0;
    while (42) {
        ft_left_throw(gems, jewels);
        if (ft_right_search(gems, jewels) == false) {
            break;
        }
    }
    
    vector<int> rtn;

    rtn.push_back(jewels.get_min_start() + 1);
    rtn.push_back(jewels.get_min_end() + 1);
    return (rtn);
}

// 일단 sort를 하던지, 보석 종류를 세는게 중요해 보임.
// 배열에서 완전탐색을 한번 한 다음. 
// 인덱스를 저장함.
// 그러니까 배열을 하나 더 만들어야함.
vector<int> solution(vector<string> gems) {
    vector<int> answer;

    vector<string> kind;
    int num_jewel = ft_how_many_kind(gems);

    // ft_first_candidate_search(gems, pair, kind);
    answer = ft_full_search(gems, num_jewel);
    // answer = pair[index];
    return answer;
}

• 테스트 케이스는 통과하지만,
• 효율성 테스트 6, 9, 10번은 탈락