모든 나라를 방문할 가장 작은 날짜 수 구하기

/*

문제 :

모든 나라를 여행할 수 있는 가장 작은 날짜 수를 구하시오.

나라는 중복 방문해도 됨.

예제 :

아래 배열이 주어지면

A= { 7,3,7,3,1,3,4,1 }

1,3,4,7 을 모두 갖는 연속된 범위는 A[2] ~ A[6] 이므로

여행에 필요한 가장 작은 날짜 수는 5일이 됩니다.

*/

#include "stdafx.h"

#include <vector>

#include <map>

#include <assert.h>

using namespace std;

int min_value(map<int, int>& m) {

  int min = INT_MAX;

  for (auto it : m) {

    if (min > it.second) min = it.second;

  }

  return min;

}

int process(vector<int> v) {

  

  map<int, int> m;  // value, pos

  int spos = 0;

  int days = 0;

  int size = static_cast<int>(v.size());

  for (int i = 0; i < size; ++i) {

    bool exist = (m.find(v[i]) != m.end());

    m[v[i]] = i;

    int cur_days = i - spos + 1;

    if (exist) {

      //값이 존재했다면 시작 pos를 가장 작은 값으로 갱신

      spos = min_value(m);

      

      // min 값 체크

      if (cur_days < days) {

        days = cur_days;

      }

    } else {

      //값이 존재하지 않았다면 

      //이전 days 값은 무의미하므로 무조건 갱신

      days = cur_days;

    }

    

  }

  return days;

}

int main()

{

  assert(process({ 7,3,7,3,1,3,4,1 }) == 5); //1, 3, 4, 7

  assert(process({ 1,1,3,4,7,1 }) == 4); // ret = 4

  assert(process({ 2,3 }) == 2); // ret = 2

  assert(process({ 6 }) == 1);   // ret = 1

  assert(process({ 1,1 }) == 1); // ret = 1

  assert(process({ 0 }) == 1); // ret = 1

  assert(process(vector<int>()) == 0); // ret = 0

  assert(process({ 1,1,1,2,2,2 }) == 2); // ret = 2

  assert(process({ 1,1,1,2,3,1,1 }) == 3); // ret = 3

  assert(process({ 5,7,2,1,2,1,4 }) == 7); // ret = 7

  assert(process({ 1,1,1,1,1,1,1 }) == 1); // ret = 1

  

  printf("\nsuccessfully completed\n");

  return 0;

}