[백준/C++] 20956번. 아이스크림 도둑 지호 deque풀이

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

20956번: 아이스크림 도둑 지호

 

0. 잡설

deque에 배열을 선언할 수 있다는 사실을 간과하고 Priority queue로 풀려다가 많은 '틀렸습니다' 를 받았습니다.

풀었던 방법을 오래 기억하고 싶어 기록합니다!

 

지호가 민초를 먹고 배열을 어떻게 돌리던간에, 가장 양이 많은 아이스크림을 먹는다는 점은 바뀌지 않습니다.

그래서 Priority Queue의 top과 같은 원소를 배열에서 앞뒤로 찾으려고 했는데요, 45%쯤에서 시간 초과를 받게 되었습니다. 

dqeue를 배열로 활용하여 정답을 맞출 수 있었습니다.

 

1. 접근 방식

아이스크림 배열을 앞에서 접근하던, 뒤에서 접근하던, 가장 양이 많은 아이스크림을 먹게됩니다.

따라서 dq를 충분하게 길게 설정한 뒤 dq[0]은 가장 양이 많은 아이스크림 모음으로, dq[1]은 두번째로 양이 많은 아이스크림 모음으로, dq[2]는 그다음.... 으로 설정해주면 양쪽에서 접근할 수 있습니다. 

예를 들어 보겠습니다.

우리에게 우선순위는 다음과 같습니다.

1. pair의 원소에서, first가 큰 것이 왼쪽으로 올 것
2. pair의 원소에서 first가 같다면, second가 오름차순이 될 것 -> 이렇게 하면 같은 양의 아이스크림이 입력 순서로 저장되어 stable sort가 된다.

우선순위대로 정렬되도록 comp함수를 마련합니다. 

입력과 sort까지 구현된 코드입니다.

#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;
deque<pair<int, int> > dq[101010];
int n, m;

bool comp(const pair<int, int> &left, const pair<int, int> &right){
    if(left.first > right.first){
        return left.first > right.first;
    }
    else if(left.first == right.first){
        return left.second < right.second;
    }
    else{
        return left.first > right.first;
    }
    
}

void input(){
    cin>>n>>m;
    int temp;
    for(int i=1; i<=n; i++){
        cin>>temp;
        v.push_back({temp, i});
    }
    
    sort(v.begin(), v.end(), comp);
...... 이하 아래에서 설명

이제 중요한 것은 원소를 왼쪽에서 접근할 수도, 오른쪽에서 접근할 수도 있다는 것입니다.

다음과 같이 deque를 구성하면 양쪽에서 접근할 수 있을 것 같습니다.

 

dq[0]은 가장 많은 양의 집합, dq[1]는 두번째로 많은 양의 집합..... 입니다. 

여기까지 코드로 구현하면 다음과 같습니다.

//
//  아이스크림 도둑 지호.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/02/04.
//

#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;
deque<pair<int, int> > dq[101010];
int n, m;

bool comp(const pair<int, int> &left, const pair<int, int> &right){
    if(left.first > right.first){
        return left.first > right.first;
    }
    else if(left.first == right.first){
        return left.second < right.second;
    }
    else{
        return left.first > right.first;
    }
    
}

void input(){
    cin>>n>>m;
    int temp;
    for(int i=1; i<=n; i++){
        cin>>temp;
        v.push_back({temp, i});
    }
    
    sort(v.begin(), v.end(), comp);
    
    int old = v[0].first;
    int idx = 0;
    
    dq[0].push_back({v[0].first, v[0].second});
    
    for(int i=1; i<n; i++){
        if(v[i].first == old){
            dq[idx].push_back({v[i].first, v[i].second});
        }
        else{
            idx+=1;
            dq[idx].push_back({v[i].first, v[i].second});
            old = v[i].first;
        }
    }
}

이제 아이스크림을 먹어봅시다! 

처음은 왼쪽에서 오른쪽으로 양이 많은 수대로 아이스크림을 먹고, 만약 민초를 먹어서 순서가 뒤바뀌면 오른쪽에서 왼쪽으로 아이스크림을 먹어치웁니다.  

dq의 각 배열 인덱스에 접근하는 원소는 따로 관리해줍시다. 해당 인덱스에 해당하는 아이스크림을 다 먹은 경우에는 idx를 하나 추가해주어 다음으로 많은 양의 아이스크림을 먹어줍니다.

그럼 정답 코드 보시겠습니다.

 

2. 정답 코드

//
//  아이스크림 도둑 지호.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/02/04.
//

#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > v;
deque<pair<int, int> > dq[101010];
int n, m;

bool comp(const pair<int, int> &left, const pair<int, int> &right){
    if(left.first > right.first){
        return left.first > right.first;
    }
    else if(left.first == right.first){
        return left.second < right.second;
    }
    else{
        return left.first > right.first;
    }
    
}

void input(){
    cin>>n>>m;
    int temp;
    for(int i=1; i<=n; i++){
        cin>>temp;
        v.push_back({temp, i});
    }
    
    sort(v.begin(), v.end(), comp);
    
    int old = v[0].first;
    int idx = 0;
    
    dq[0].push_back({v[0].first, v[0].second});
    
    for(int i=1; i<n; i++){
        if(v[i].first == old){
            dq[idx].push_back({v[i].first, v[i].second});
        }
        else{
            idx+=1;
            dq[idx].push_back({v[i].first, v[i].second});
            old = v[i].first;
        }
    }
}


void solve(){
   input();
   
   
   // true: 오른쪽 방향으로
   // false: 뒤집힌 방향
   bool direction = true;
   int idx = 0;
   while(m--){
       if(direction){
           //오른쪽 방향으로
           if(dq[idx].size() > 0){
               cout<<dq[idx].front().second<<"\n";
               
               if(dq[idx].front().first % 7 == 0) direction = false;
               
               dq[idx].pop_front();
           }
           else{
               idx += 1;
               cout<<dq[idx].front().second<<"\n";
               
               if(dq[idx].front().first % 7 == 0) direction = false;
               
               dq[idx].pop_front();
           }
       }
       else{
           //오른쪽에서 왼쪽으로
           if(dq[idx].size() > 0){
               cout<<dq[idx].back().second<<"\n";
               
               if(dq[idx].back().first % 7 == 0) direction = true;
               
               dq[idx].pop_back();
           }
           else{
               idx += 1;
               
               cout<<dq[idx].back().second<<"\n";
               
               if(dq[idx].back().first % 7 == 0) direction = true;
               
               dq[idx].pop_back();
           }
       }
       
   }
}

int main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   solve();
}