[프로그래머스] 2020 카카오 인턴십 보석 쇼핑 C++ : 풀이 / 테스트케이스

프로그래머스

간만에 머리 조금씩 굴려가며 푼 문제이다.ㅠㅠ

 

 

 

 

---

초기 알고리즘 (효율성 0% 오답)

 

1. 전체 보석의 종류 수 구하기

    vector<string> type; // 보석이 있는지 확인을 위한 벡터
    vector<int> answer;  // 정답 채울 벡터
    int len = gems.size();

    int cnt = 0; // 보석의 전체 종류 수 저장
    for (int i = 0; i < len; i++) {
        // 만약에 벡터에 포함되지 않은 요소라면
        if (type.end() == find(type.begin(), type.end(), gems[i])) {
            // 벡터에 집어넣고, 전체 보석 종류 수 증가
            type.push_back(gems[i]);
            cnt++;
        }
    }
    // 보석 카운팅 하기 위해 채운 벡터는 비워준다.
    type.clear();

먼저 왜 그랬는지 기억이 나지 않지만,

map이 아닌 vector에서 find결과가 end인(vector 내부에 그런 요소가 없다는 의미) 경우

보석을 추가하고, 카운트를 증가했다.

보석을 담은 뒤에는 clear을 이용해 vector를 비워주었다.

 

 

 

2. 거의 전체를 순환하며 구간 찾기

    // 현재 최대로 나올 수 있는 사이즈로 시작,종료 지점 지정
    int s = 0, e = len;
    // 시작지점을 의미하는 i
    for (int i = 0; i < len; i++) {
        // i부터 돌며 종료지점을 의미하는 j 
        for (int j = i; j < len; j++) {

i : 구간의 start의 역할이다.

j : 구간의 end 역할이다.

(i,j) = (0,0)

(i,j) = (0,1)

(i,j) = (0,2)

 ...

(i,j) = (9,9)

이런 식으로  탐색을 한다.

 

 

 

 

3. 각 요소를 탐색하며  vector에 추가되지 않은 요소가 보인다면 추가한다.

            // 현재 요소가 벡터에 없다면,
            if (type.end() == find(type.begin(), type.end(), gems[j])) {
                // 벡터에 추가
                type.push_back(gems[j]);
            }

1. (0,0) : A는 벡터에 없으니 추가

2. (0,1) : B는 벡터에 없으니 추가

3. (0.2) : C는 벡터에 없으니 추가

4. (0.3) : B는 벡터에 이미 있으니 넘어감

5. (0.4) : F는 벡터에 없은 추가

 

 

 

4. (벡터의 길이 == 보석 종류의 개수)면 구간 업데이트

            // 만약에 지금 벡터길이가 전체 보석 종류수와 같을 때
            if (type.size() == cnt) {
                // 저장된 구간보다, 지금 구간이 짧다면,
                if ((e - s) > (j - i)) {
                    // 구간 업데이트 후 현재 루프 끝
                    s = i;
                    e = j;
                    break;
                }
            }

 

5. 새로운 루프를 위한 초기화

        // 새로운 시작을 위해 초기화
        type.clear();

 

 

효율성 0점으로 틀려버린다.

해당 기법은 조금 최적화 하였다해도

10만번 * 10만번의 루프를 돌려버린다는 것과 거의 다름이 없기 때문이다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> type;
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int len = gems.size();

    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (type.end() == find(type.begin(), type.end(), gems[i])) {
            type.push_back(gems[i]);
            cnt++;
        }
    }
    type.clear();

    int s = 0, e = len;
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            if (type.end() == find(type.begin(), type.end(), gems[j])) {
                type.push_back(gems[j]);
            }

            if (type.size() == cnt) {
                if ((e - s) > (j - i)) {
                    s = i;
                    e = j;
                    break;
                }
            }
        }
        type.clear();
    }
    answer.push_back(s+1);
    answer.push_back(e+1);
    return answer;
}

 

 

 

 

---

 

수정 알고리즘 (정답)

 

1. 전체 보석의 종류 수 구하기

    int allKind = 0; // 보석 수 저장
    map<string, int> gKind; // 보석 임시 저장소
    for(int i = 0; i < gems.size(); i++) {
        // 현재 map에 없는 요소라면 
        if(gKind.find(gems[i]) == gKind.end()) {
            // map에 추가하고 카운트 증가
            gKind.insert(pair<string, int>(gems[i], allKind));
            allKind++; // 이렇게 안 하고 다 돌린 다음 allKind = gKind.size() 해도 된다.
        }
    }

- allKind : 전체 보석의 수를 센다.

- gKind : 보석이 map에 추가되어 있는 지를 이용해 전체 보석의 수를 헤아린다.

 

 

 

2. end가 증가하는 경우

end는 (map의 길이==보석종류의 수)일 때까지 증가한다.

그동안 각 지점을 탐색하며 보석의 등장 횟수를 센다,

map에 없는 보석이 등장하면 : 맵에 insert

map에 있는 보석이 등장하면 : map의 value값 증가

 

 

            // <보석이름 ,등장횟수>를 저장하는 map
            map<string, int> exist;

            // 현재 보석이 map에 저장되어 있지 않은 경우
            if(exist.find(gems[e]) == exist.end()) {
                // 등장횟수 1로 지정해 추가
                exist.insert(pair<string, int>(gems[e], 1));
            }
            // 현재 보석이 map에 있는 경우
            else { 
                // 해당 보석 등장 횟수 증가
                exist[gems[e]]++; 
            }

위 코드는 보석이 map에 저장되지 않은 경우에는 추가하고

이미 존재하는 경우에는 보석의 등장 횟수를 증가하는 모습이다.

 

 

 

        // (map의 크기== 보석의 종류 수)라면
        if(exist.size() == allKind){
            // 잠시 후 공개
        }
        else {
            e++; // end 증가
        }

보석을 추가하거나 횟수를 추가한 후에는

현재 map이 모든 보석을 포함한 구간인지

(map의 크기== 모든 보석의 수)를 통해 확인한다.

올바른 구간이 아닌 경우에는 end가 증가한다. 

 

 

 

3. start가 증가하는 경우

위에서 구간을 찾은 이후이다.

구간이 찾아지면 구간의 길이를 줄이는 작업을 시작한다.

 

 if(현재 구간이 모든 요소를 포함한다면)

1. 현재 Start의 등장 횟수를 줄이거나 지운다.

 - 등장횟수가 2이상 : 등장횟수 -1

- 등장횟수가 1 : 해당 요소 삭제

 

2. 현재 구간의 길이를 업데이트 한다.

rs : 최종 시작점

re : 최종 종료점

if(re-rs < e-s) : 지금 구간이 저장된 구간 보다 길 때

 

3. S를 증가한다.

 

else if (구간을 줄였더니 모든 요소를 포함하지 않는다면)

1. e가 증가된다. 

 

위의 이미지로 예를 들면

현재 A 2번, B 2번, C 1번이 등장했었다.

1) AABBC => A의 등장횟수를 감소하고 s++

2) ABBC => A의 등장횟수가 1이니 삭제하고 s++

3) BBC => d올바른 구간이 아니므로 e++

 

위의 이후 내용이다.

1) BBCA => e를 증가하면서 다시 구간이 맞추어졌다. 구간 줄이기 시작, s++

2) BCA => 구간이 맞추어졌다. 구간 줄이기 s++

 

이런 과정을 통해 최종적인 길이가 맞추어진다.

        // 만약 구간이 맞추어지면
        if(exist.size() == allKind){
            // 값 교환 부분
            // 현재 구간이 지금까지 최소구간보다 작을 때
            if(e-s < min) { 
                // 최종 시작/종료/구간길이 업데이트
                rs=s;re=e;min=e-s; 
            }
            // 구간 줄이기 부분
            // 지금 s의 요소가 하나라면
            // gems에서 보석이름 불러오고 그걸 map에 넣어서 등장횟수 확인
            if(exist[gems[s]] == 1) {
                // 현재 s 요소 삭제
                exist.erase(gems[s]);
            }
            // s의 요소가 2개 이상이라면
            else {
                // 등장횟수 감소
                exist[gems[s]]--;
            }
            // s를 증가해 구간 줄이기
            s++;
        }
        // 구간이 맞추어지지 않았다면
        else {
            // e를 증가해 탐색 구간 늘이기
            e++;
        }

 

 

4. 종료조건과 예외처리

2,3의 코드는 모두 무한루프 내에서 돌게 된다

따라서 종료 조건이 필요하다.

1) 보석 나열 벡터 - start 지점 < 모든 보석 종류 : 모든 보석종류보다 남은 리스트가 적을 때

2) end 지점 >=  보석 나열 벡터 : 더 확인할 보석이 없을 때

3) start > end : 시작점이 종료점을 역전할 때

    while(777) {
        if (gems.size() - s < allKind || e >= gems.size() || s > e) break;
        // 2, 3의 코드
    }

 

 

또한 e값은 보석을 추가하거나 등장횟수를 변경하는 데 쓰인다.

s가 움직였을 때 e를 이용해 등장횟수를 변경하는 경우가 생겨 오답이 도출되었기 때문에

e값이 변경된 경우에만 요소를 추가하거나 등장횟수를 변경하도록 했다.

1) 이전 c값을 저장하는 ce값 을 -1로 선언

int c = 0, ce = -1;

2) e와 ce 값이 다르다면 요소추가/변경 코드 동작

if(e!=ce)

3) ce 값을 현재 c값으로 변경

ce = c

4) c혹은 s값이 변경됨

- c값 변화시 : c는 1증가됨, ce는 값이 변하지 않음 => ce != c

- s값 변화시 : c는 그대로임 ce도 그대로임 => ce==c

    // 최근 탐색한 e
    int ce=-1;
    while(777) {
        // 종료조건 코드 ...

        // start가 움직인 경우에는 요소추가나 등장 횟수 변경이 없기 위함
        if(e != ce) {
            // 요소 추가하거나 등장횟수 변경 코드 ...
        }
        // ce값 업데이트
        ce = e;

        // 구간이 유효한지 확인
        if(exist.size() == allKind){
          // 시작/종료 값 업데이트 하는 코드 ...
          s++
        }
        else {
            // e의 변경
            e++;
        }
    }

5. 전체 코드

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

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int allKind = 0;
    map<string, int> gKind;
    // 모든 보석종류 파악
    for(int i = 0; i < gems.size(); i++) {
        if(gKind.find(gems[i]) == gKind.end()) {
            gKind.insert(pair<string, int>(gems[i], allKind));
            allKind++;
        }
    }

    int cnt =0;
    int s = 0, e = 0, rs,  re, min = gems.size()+1, ce=0;
    map<string, int> exist;
    // 구간 탐색
    while(777) {
        // 종료조건
        if (gems.size() - s < allKind || e >= gems.size() || s > e) break;
        // e값이 변경된 경우
        if(e != ce || e == 0) {
        // 신규 보석은 추가 등록된 보석은 등장횟수 증가
            if(exist.find(gems[e]) == exist.end()) { exist.insert(pair<string, int>(gems[e], 1)); }
            else { exist[gems[e]]++; }
        }
        // ce값 업뎃 : e값 변경 파악용
        ce = e;

        // 구간 유효성 파악 : 지금 map길이가 보석 종류 수와 같은가?
        if(exist.size() == allKind){
            // 최소값 보다 짧은 구간인가?
            if(e-s < min) { rs=s;re=e;min=e-s; }
            // 구간 좁히기
            // 지금 좁힐 녀석이 한 번만 등장했다면 삭제
            if(exist[gems[s]] == 1) { exist.erase(gems[s]); }
            // 2번 이상 등장했다면 등장 횟수 감소
            else { exist[gems[s]]--; }
            // s증가
            s++;
        }
        // 구간이 올바르지 않다면 : 모든 보석이 다 있는게 아닌 경우
        else { e++; } // 탐색 구간 확대
    }
    // 실제 정답은 시작 인덱스가 1부터라 1증가하여 넣기
    answer.push_back(rs+1);
    answer.push_back(re+1);
    return answer;
}

 

 

 

 

---

테스트 케이스

A A A A B B  : 3, 4

A : 1,1

A B B B B B B C B A : 8, 10

A B B C A B C A B C : 3, 5

A B B B C D D D D D D D B C A : 13, 15

 

 

---