백준 14646번 욱제는 결정장애야!!

문제 링크입니다: https://www.acmicpc.net/problem/14646

시간복잡도 O(N)으로 풀 수 있는 탐색 문제였습니다.

알고리즘은 아래와 같습니다.

1. 기존에 선택되지 않았던 칸이라면 벡터에 넣고 선택되었다고 표시합니다.

2. 기존에 선택되었던 칸이라면 지워야하는데 실제로 지우지 않고 지운 원소를 증가시킵니다.

3. 반복문의 끝마다 현재 스티커가 붙여있는 개수를 파악하고 최대 개수를 초기화합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N;

vector<int> wheel;

bool selected[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

 

        int result = 0;

        int erase = 0;

        for (int i = 0; i < 2 * N; i++)

        {

                 int num;

                 cin >> num;

 

                 //기존에 선택되지 않았다면

                 if (!selected[num])

                 {

                         wheel.push_back(num);

                         selected[num] = true;

                 }

                 //기존에 선택되었다면 지운다

                 else

                         erase++;

                 result = max(result, (int)wheel.size() - erase);

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~