풀이전략

1. 어떤 stl을 사용할까?

• 중복 없고, 두개의 값이 있어서 unordered_map으로 접근하려고 햇다.
  앞뒤 인덱스를 확인해야 하므로
  -> 인덱스 접근을 해야했다.
  unordered_map 접근 잘못 되었다.

• vector<pair<int,int>> 로도 접근 해볼까? 라는 생각도 함.

해당 문제에서는 키값을 찾는 것이 아니라 인덱스 접근을 하는 것이다.

2. 0번 인덱스와 마지막 인덱스에서는 어떻게 처리할 것인가??

• 인덱스 + 1, 인덱스 - 1 값이 2인지를 확인하는데
  맨앞일 경우 즉, 0번 인덱스와 -> 인덱스가 -1 또는 0으로?
  마지막 인덱스 일 경우에는 어떻게 처리할 것인지 -> 컨테이너를 더 확장할까?

결론

• 컨테이너를 + 2 만큼 크게 만들자.
• 초기화를 1로 하고, 추가 및 삭제 해봤자 마지막와 처음 값은 증가및 감소가 없을 것이다.
• 마지막에 출력할때 첫번째 인덱스와 마지막 인덱스의 개수는 2개 이므로
  2개를 빼자!

vector vs map

• 크기 차이
  

  vector로 map과 같이 사용할 수 있다면 vector를 사용하자.

• 체육복에서 vector를 사용해야 하는 이유
  1) 인덱스 접근이다.
  vector의 인덱스 접근은 시간 복잡도 1이다.
  unordered_map의 탐색은 1 또는 n이다.
  map의 탐색은 logN이다.
  그리고 map과 unordered_map의 인덱스 접근은 위험하다.

2) 연속된 인덱스 접근하는데 바이트 크기가 크다...

느낀점

다른 stl도 쓸 수 있을 것 같다라는 생각이 들었을때, 삽입이든, 탐색이든,
각 stl의 사이즈든 어떤 것을 사용할때 효율적일지 고민해보자.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    vector<int>man(n + 2, 1);
    
    for(const auto & i : lost)
        man[i]--;
    
    for(const auto & i : reserve)
        man[i]++;
    
    for(int i = 1; i <= man.size() ; i++)
    {
        if(man[i] == 0)
        {
            if(man[i - 1] == 2)
            {
                man[i - 1] = 1;
                man[i] = 1;
            }
            else if(man[i + 1] == 2)
            {
                man[i + 1] = 1;
                man[i] = 1;
            }
        }
    }
    
    for(const auto & i : man)
    {
        if(i != 0)
            answer++;
    }
    answer -= 2;
    return answer;
}