백준 31747번 점호 [C++]

https://www.acmicpc.net/problem/31747

 

 

#문제 간단 정리

 

2학년과 1학년이 섞인 줄에서

가장 앞에있는 2학년과 1학년을 

하나씩 없에는 기능을 구현하는

 

구현 + 시뮬레이션 문제

 

 

#문제 해결 방법

 

우선 나이브하게 

그냥 1학년과 2학년을 k만큼 탐색해서

벡터에서 제거해주는 나이브한 로직을 생각 해 낼 수 있는데

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

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    vector<int> line(n);

    for (int i = 0; i <n; i++) {
        cin >> line[i];
    }

    int time = 0;
    
    while (!line.empty()) {
        bool grade1 = false;
        bool grade2 = false;
        int grade1Index = 0;
        int grade2Index = 0;

        int checkLength = line.size();
        checkLength = min(k, checkLength);

        for (int i = 0; i < checkLength; i++) {
            if (line[i] == 1 && grade1 == false) {
                grade1Index = i;
                grade1 = true;
            }
            if (line[i] == 2 && grade2 == false) {
                grade2Index = i;
                grade2 = true;
            }

        }
        if (grade1 && grade2) {
            if (grade1Index < grade2Index) {
                line.erase(line.begin() + grade2Index);
                line.erase(line.begin() + grade1Index);
            }
            else {
                line.erase(line.begin() + grade1Index);
                line.erase(line.begin() + grade2Index);
            }
        }
        else if (grade2) {
            line.erase(line.begin() + grade2Index);
        }
        else if (grade1) {
            line.erase(line.begin() + grade1Index);
        }
           
;
        time++;
    }

    cout << time << '\n';

    return 0;
}

 

벡터에서 제거하는 부분에서도 시간초과가 날 수 있지만

 

그전에 간단하게 만약 k = n 이라고 하게 되면 

항상 n개를 탐색하게 되어서 매우 시간복잡도 가 크게 된다

 

 

때문에 나는

1학년과 2학년의 위치를

덱에 넣고

 

 

얼마만큼 빠져나간지 알도록 인덱스를 사용하였다

현재 줄에서 빠져나간 만큼 인덱스를 올려서 인덱스를 참조하도록 하였다.

 

여기서 1학년 덱과 2학년 덱을 조사해서 맨 앞에 있는 값이 

인덱스 + k 의 값 이하의 값을 가지고 있다면 

덱에서  pop 해주고 인덱스를 올려 줬다.

 

이렇게 남은 1학년과 2학년의 숫자와

줄의 길이를 빠르게 추적 가능하다

 

정확히 이런 기능을 어떻게 구현할지 물어보는 문제라고 볼 수 있겠다.

 

아 물론 덱을 안쓰고 벡터를 역순으로 집어 넣는다던가 하는 식으로 덱을 안써도 할 수 있겟지만

직관적으로 풀려고 덱을 사용하였다.

 

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <deque>;

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    deque<int> line(n);
    deque<int> grade1;
    deque<int> grade2;
    int lineSize = line.size();

    for (int i = 0; i < n; i++) {
        cin >> line[i];
 
        if (line[i] == 1) {
            grade1.push_back(i);
        }
        else {
            grade2.push_back(i);
        }
    }


    int time = 0;
    int index = 0;

    while (index < line.size()) {


        //남은 인덱스 확인
        int checkLength = index + k - 1;
        checkLength = min(lineSize -1 , checkLength);

        if (!grade1.empty() && grade1.front() <= checkLength) {
            index++;
            grade1.pop_front();
        }
        if (!grade2.empty() && grade2.front() <= checkLength) {
            index++;
            grade2.pop_front();
        }

        time++;
    }

    cout << time << '\n';

    return 0;
}