[프로그래머스] 보석 쇼핑

2020 카카오 인턴십 - 보석 쇼핑

풀이

하지만 1차 시도에서 효율성 테스트를 모두 통과하지 못했다..!
check_gems()에서 map을 불필요하게 많이 돌았던게 원인이 됐던 것 같다.
그래서 모든 종류의 보석들이 들어있는 구간에 진입하기 전까지는 check_gems() 함수로 이동하는 것을 막았더니 모든 테스트를 통과할 수 있었다.
시작, 끝 구간을 확인하는 부분도 효율적으로 바꿀 수 있을 것 같다. 시도해봐야겠다.

set이란?

map과 비슷하게 동일한 자료형들을 모아 놓은 집합 역할을 한다
하지만 key, value를 동시에 저장, 관리하는 map과는 다르게, set은 저장하는 데이터 자체가 키로 사용되며 값은 저장되지 않는다.
-> key만 있는 map 이라고 우선 생각해두자
-> 중복을 허용하지 않는다(중복을 사용하려면 multiset을 사용해야 한다.)
-> 원소는 자동으로 정렬

map

map<string, int> m 형태에서 m[문자열]; 입력시 value가 어떻게 초기화가 되는지 궁금해서 직접 해봤다.

    unordered_map<string, int> mm;
    for(int i = 0 ; i < 5 ; i++){
        string str;
        cin >> str;
        mm[str]++;
    }
    for(auto it = mm.begin() ; it != mm.end() ; it++){
        cout << it->first << " " << it->second << endl;
    }
=> 출력결과
    AC 2
    AB 1
    AA 2

7/21 업데이트

다른 방법으로 풀어봤다!
투 포인터 알고리즘을 사용해서 카카오 기술 블로그에 나온 방법을 사용했다.

카카오 기술 블로그에서 알려주는 다른 방법!

문제 해설

1. 맵 자료구조에서, ‘map[보석 이름] = 빈도수’로 정의를 합니다.

2. 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킵니다.

3. 양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료합니다.

4. 양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 봅니다.(map의 사이즈를 체크합니다)

• 5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l를 증가시킵니다. 그리고 2로 갑니다.
• 5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r를 증가시킵니다. 그리고 3으로 갑니다.

즉, 왼쪽을 가리키는 포인터 l과 오른쪽을 가리키는 포인터 r을 이용하여 보석의 종류가 모자라면 r을 증가시키고, 보석의 종류가 충분하면 l을 증가시키는 과정을 반복하면서, 정답을 갱신시켜나갑니다. 이때 l을 증가시키기 이전, map자료구조에서 l번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 map에서 완전히 제거하여야 합니다. r을 증가시킬 때는 map자료구조에서 증가된 r번 진열대에 있는 보석의 빈도수를 증가시켜줍니다.

코드

1차 시도 코드

효율성 테스트 4, 12, 13, 15을 틀렸다.

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

unordered_map<string, int> m;
int front = 100000, back = -1;

void check_gems(){
    int left = 100000, right = -1;
    // 1. map을 순회했을 때 -1을 가진 값들이 없어야 한다.
    // 2. 1번을 만족한다면 front, back을 업데이트해준다.
    // 3. back-front 값이 동일해도 업데이트 해준다 -> 가장 짧은 구간이 여러개일 경우 시작 번호가 가장 작은 것을 return해준다.
    bool every_gems_find = true;
    for(auto it=m.begin() ; it != m.end() ; it++){
        if(it->second == -1) every_gems_find = false;
    }
    if(!every_gems_find) return;
    
    for(auto it=m.begin() ; it != m.end() ; it++){
        if(it->second > right) right = it->second;
        if(it->second < left) left = it->second;
    }
    if(abs(front-back) >= abs(left-right)){
        front = left;
        back = right;
    }
}
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int len = (int)gems.size();
    
    for(int i = 0 ; i < len ; i++) m[gems[i]] = -1;
    
    for(int i = len-1 ; i >= 0 ; i--){
        m[gems[i]] = i;
        check_gems();
    }
    answer.push_back(front+1);
    answer.push_back(back+1);
    return answer;
}

최종 코드 - 1

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

unordered_map<string, int> m;
int front = 100000, back = -1;
bool isFull = false;

void check_gems(){
    int left = 100000, right = -1;
    
    for(auto it=m.begin() ; it != m.end() ; it++){
        if(it->second > right) right = it->second;
        if(it->second < left) left = it->second;
    }
    if(abs(front-back) >= abs(left-right)){
        front = left;
        back = right;
    }
}
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int len = (int)gems.size();
    int total_gems_kinds = 0;
    
    for(int i = 0 ; i < len ; i++) m[gems[i]] = -1;
    
    // 보석 종류의 개수를 파악해야 한다.
    for(auto it = m.begin() ; it != m.end() ; it++) total_gems_kinds++;
    
    // 뒤에서부터 for문을 돌면서 최소 구간 발견
    for(int i = len-1 ; i >= 0 ; i--){
        if(m[gems[i]] == -1) // 새로 추가된 보석의 종류라면
        {
            m[gems[i]] = i;
            total_gems_kinds--;
            if(total_gems_kinds == 0) isFull = true;
        }
        else // 기존에 발견된 보석의 종류라면
        {
            m[gems[i]] = i;
        }
        
        if(isFull) check_gems();
    }
    answer.push_back(front+1);
    answer.push_back(back+1);
    return answer;
}

최종 코드 - 2

7월 21일 업데이트!

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;

set<string> gems_list;
unordered_map<string, int> m;

vector<int> solution(vector<string> gems) {
    int left = 0, right = 0, gems_cnt;
    int len = (int)gems.size();
    
    vector<int> answer(2);
    answer[0] = 0;
    answer[1] = len-1;
    
    for(int i = 0 ; i < len ; i++) gems_list.insert(gems[i]);
    gems_cnt = (int)gems_list.size(); // 보석 종류의 개수
    
    m[gems[0]]++;
    while(1){
        if(m.size() == gems_cnt){
            if(answer[1] - answer[0] > right - left){
                answer[1] = right;
                answer[0] = left;
            }
            if(left == right) break;
            else{
                m[gems[left]]--;
                if(m[gems[left]] == 0) m.erase(gems[left]);
                left++;
            }
        }
        else if(m.size() > gems_cnt){
            if(left + 1 >= len) break;
            else{
                m[gems[left]]--;
                if(m[gems[left]] == 0) m.erase(gems[left]);
                left++;
            }
        }
        else if(m.size() < gems_cnt){
            if(right + 1 >= len) break;
            else{
                m[gems[++right]]++;
            }
        }
    }
    answer[0]++;
    answer[1]++;
    return answer;
}