카카오[보석 쇼핑]

Developer:Bird·2021년 1월 9일
0

알고리즘

목록 보기
5/17

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

[1.이해]

예시

보석 배열: [3,1,2,1,2,0,1,0,3]
종류: [0,1,2,3]
종류를 다 포함하는 가장 짧은 수열: [2,0,1,0,3]

모든종류가 다 들어왔는 지 확인하기 위해서 배열을 탐색하면서 보석을 컨테이너에 집어넣고 컨테이너의 사이즈=종류의 수 인지 비교하면 된다. 이때 컨테이너의 사이즈 뿐만 아니라 수열의 길이에 대해서 검사하기 위해서 컨테이너에는 보석의 종류 뿐만 아니라 값의 보석의 위치도 포함 되어야한다.

[2.알고리즘 선택]

먼저 보석의 종류와 위치정보에 대해서 가지고 탐색을 해 나가야한다.
이 문제를 푸는데 떠올린 생각은 2가지다.

1. 이분탐색

보석 담을 컨테이너: 순서가 정렬되어있는 Vector(다이나믹 어레이)

알고리즘 순서

  1. 보석을 넣을때마다 순서에 맞게 삽입한다.
  2. 이때 컨테이너에 이미있던 종류의 보석에 대해서 들어올 경우 위치를 바꿔치기 한다.
  3. 이때 바꿔치기에 의해서 시작지점이 변경된다면 이를 갱신한다.
  4. 길이(끝지점-시작지점)를 이전 최저길이와 비교한다.

시간복잡도

  • 하나의 데이터 삽입경우
    (1)삽입 부분 탐색시간: O(logN)
    (2)갱신 시간: O(N)의 복잡도를 보이게 된다.
    갱신 시간을 줄이기 위해서 우선순위큐를 쓰는방법도 고려 하였지만 보석의 위치들이 바꿔치기할 때마다 우선순위큐의 데이터도 변동을 시켜줘야 하는데 더 복잡해진다.
  • 전체 데이터 삽입시
    최악으로N*((logN+N))다음이 발생할 수 있다.

결론

사실상 브루트 포스방식의 탐색으로 생기는 시간복잡도 O(N^2)비교했을때 큰 장점이 없다.

2. 큐방식

1.컨테이너

  • 보석의 종류만 담겨있는 queue.
  • Queue에 같은 보석이 몇개나 들어왔는지 확인하기 위한 map<종류,수> kindsMap

2.순서

[1].탐색시 보석종류를 queue에 push하고 KindsMap[보석종류]+1한다.
[2].queue의 front에 해당하는 보석종류의 갯수가 여러개일 경우 queue.pop()한다.
pop하게 되면 [3]으로 넘어가고 그렇지 않다면 [4]로 넘어간다.
[3].pop을 된다면 시작지점을 +1하고 kindsMap[보석종류]-1한다.
[4].queue안에 모든 사이즈의 보석이 있다면( kindsMap사이즈를 가지고 판단) 현재까지의 최소 수열길이와 비교하고 갱신한다.

시간복잡도

  • queue를 사용하면 O(N)이 보장가능하다.

결론

이분탐색방식과 비교했을때 사용하기 간단하면서 훨씬 효율적이다.

[4.구현]

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> GemsMap; // key:보석이름 value:정수로 변환된 보석종류
vector<int> GemsVec;
unordered_map<int, int> KindsCount; //key=보석종류,value=수
queue<int> Gemque;
int start_ = 0, end_ = 0, tempStart = 0, tempEnd = 0;
int Kinds = 0;
int MinLength = 2e9;

vector<int> solution(vector<string> gems)
{
    for (auto &gem : gems)
    {
        if (GemsMap[gem] == 0)
        {
            ++Kinds;
            GemsMap[gem] = Kinds;
        }
        GemsVec.push_back(GemsMap[gem]);
    }
    for (auto gem : GemsVec)
    {
        Gemque.push(gem);                      //1
        KindsCount[gem]++;                     //1
        while (KindsCount[Gemque.front()] > 1) //2~3
        {
            KindsCount[Gemque.front()]--;
            tempStart++;
            Gemque.pop();
        }
        if ((int)KindsCount.size() == Kinds && (int)Gemque.size() < MinLength) //4
        {
            MinLength = Gemque.size();
            start_ = tempStart;
            end_ = tempEnd;
        }
        tempEnd++;
    }
    return vector<int>({start_ + 1, end_ + 1});
};

[5.고찰]

Queue로 푸는데 익숙해지자.

profile
끈임없이 발전하자.

0개의 댓글