[BOJ/Gold 4] 백준 20956 아이스크림 도둑 지호(C++)

문제 링크

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

 

문제

지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코를 싫어한다. 아이스크림으로 이를 닦는다는 발상은 누가 한 것인지 궁금할 뿐이다. 아무튼 매번 아이스크림을 사 먹는 것이 지겨워진 지호는 이제부터 아이스크림을 훔쳐 먹기로 결심하였다.

아이스크림 가게에는 다양한 맛의 아이스크림 N개가 한 줄로 배치되어 있다. 아이스크림에는 번호가 매겨져 있는데, 가장 왼쪽 아이스크림이 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 아이스크림은 N번이다. 지호는 항상 양이 가장 많은 아이스크림을 선택하여 전부 먹는다. 양이 가장 많은 아이스크림이 여러 개라면 가장 왼쪽에 있는 것을 먹는다.

지호는 대다수의 사람과 마찬가지로 민트초코 맛을 싫어한다. 다행히 지호는 아이스크림의 양이 주어질 때 아이스크림의 맛을 알 수 있다. 지호의 판별법에 따르면, 아이스크림의 양이 7의 배수라면 민트초코 맛이고, 그렇지 않다면 민트초코 맛이 아니라고 한다.

지호는 민트초코를 싫어한다는 사실을 명심하라. 민트초코 맛 아이스크림을 먹은 지호는 크게 분노하여 남아 있는 아이스크림의 순서를 좌우로 뒤집는다. 즉, K개의 아이스크림이 있다면 i번째 아이스크림과 (K - i + 1)번째 아이스크림의 위치를 뒤바꾼다. (1 ≤ i ≤ ⌊K / 2⌋)

지호는 N개의 아이스크림 중 M개의 아이스크림을 먹으려 한다. 아이스크림의 양이 주어졌을 때, 지호가 먹은 아이스크림의 번호를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 전체 아이스크림의 개수 N과 지호가 먹을 아이스크림의 개수 M이 주어진다.

두 번째 줄에 N개의 정수 A1, A2, ..., AN이 주어진다. 이때 Ai는 i번 아이스크림의 양을 의미한다.

모든 입력은 공백으로 구분되어 주어진다.

 

출력

M개의 줄에 걸쳐 i(1 ≤ i ≤ M)번째 줄에는 지호가 i번째로 먹은 아이스크림의 번호를 출력한다.

 

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ N
• 1 ≤ Ai ≤ 1,000,000,000

 

예제 입력 1

5 4
7 6 8 6 5

예제 출력 1

3
1
4
2

예제 입력 2

7 5
7 7 7 7 7 7 7

예제 출력 2

1
7
2
6
3

 

알고리즘 분류

• 자료 구조

 

풀이

아이스크림은 최대 100,000개까지 존재하며, 매번 최대 100,000개의 아이스크림을 탐색하면서 최대의 양을 가진 아이스크림을 찾을 수는 없기 때문에 다른 방법이 필요하다.

그런데 문제를 보면, 아이스크림의 순서를 좌우로 뒤집는다는 문구가 존재한다. 따라서, 앞뒤로 원소를 push/pop할 수 있는 덱을 사용한다.

다만, 그냥 덱을 사용하면서 아이스크림 원소를 추가하고 꺼내면 매번 최대 100,000개의 아이스크림을 탐색하는 것과 다를 바가 없기 때문에, 최대 100,000개로 구성된 덱 배열을 선언한다.

그러니까 어떤 아이스크림의 맛이 i라면, 해당 아이스크림의 번호는 i번째 덱에 추가해서 관리하겠다는 뜻이다.

그런데 아이스크림의 맛은 최대 10억이므로, 값을 압축해야 한다.

이를 위해 먼저 아이스크림의 맛 종류들을 오름차순 정렬하고, 해싱을 해서 번호를 매긴다.

왜냐하면 어차피 아이스크림은 최대 100,000개까지만 등장하고, 따라서 등장하는 맛은 아무리 많아도 최대 100,000종류일 것이기 때문이다.

이렇게 최대 100,000개의 아이스크림의 번호를 덱에 추가하고, 아이스크림의 양이 가장 많은 덱부터 하나씩 원소를 제거한다.

근데 현재 덱에 해당하는 아이스크림의 양이 7의 배수면, 순서를 뒤집어야 한다. 근데 우리는 덱을 사용하기 때문에 순서를 뒤집었다는 boolean 변수만을 추가해서, false일 때는 front를, true일 때는 back을 확인하면 된다.

이렇게 M개의 아이스크림을 전부 맛봤으면 끝이다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <unordered_map>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int N, M, X;
vector<pair<int, int> > Icecreams;
vector<int> Values;
deque<int> DQ[MAX];
unordered_map<int, int> UM, UM2;
int ValueIndex = -1;
bool isReverse = false;

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> X;
        Icecreams.push_back(make_pair(i + 1, X));
        Values.push_back(X);
    }
}

void settings() {
    sort(Values.begin(), Values.end());
    Values.erase(unique(Values.begin(), Values.end()), Values.end());
    for (int i = 0; i < (int)Values.size(); i++) {
        UM.insert(make_pair(Values[i], ++ValueIndex));
        UM2.insert(make_pair(ValueIndex, Values[i]));
    }
    
    for (int i = 0; i < (int)Icecreams.size(); i++) {
        int Index = UM[Icecreams[i].second];
        DQ[Index].push_back(Icecreams[i].first);
    }
    
    while (true) {
        if (M == 0) break;
        
        if (DQ[ValueIndex].empty()) {
            ValueIndex--;
        }
        else {
            M--;
            if (isReverse) {
                int Now = DQ[ValueIndex].back();
                DQ[ValueIndex].pop_back();
                if (UM2[ValueIndex] % 7 == 0) {
                    isReverse = !isReverse;
                }
                cout << Now << "\n";
            }
            else {
                int Now = DQ[ValueIndex].front();
                DQ[ValueIndex].pop_front();
                if (UM2[ValueIndex] % 7 == 0) {
                    isReverse = !isReverse;
                }
                cout << Now << "\n";
            }
        }
    };
}

int main() {
    FASTIO
    input();
    settings();

    return 0;
}