[Codeforces] Shoe Shuffling

이제는 백준에서 더 나아가 영어로 알고리즘 풀이를 해보고 싶어서 망설임없이 코드 포스에 입문했다.

마침 코드 포스에 가입한 다음날에 열리는 대회에 참가해보았다.

 

결과는 확실히 망했다...

흑흑 그래도 첫 도전에 의미를 담으며...ㅎㅎ

 

대회 중간에 통과하지 못했던 Problem B를 대회 이후에 풀어보았다.

알고보니 어이 없는 잘못을 저질러서 실패했던 것이었다.

 

https://codeforces.com/contest/1691/problem/B

Problem - B - Codeforces

핵심

💚 학생들의 신발 사이즈 $s_{i}$가 비내림차순(non-decreasing)으로 정렬되어있다.

💚 학생들은 본인의 신발을 안 신고, 본인의 사이즈와 동일하거나 큰(greater than or equal to) 신발을 신어야 한다.

 

처음에는 일반적인 permutation을 해야하나 싶었지만 여러 테스트 케이스를 시도하다보니 하나의 패턴을 찾았다.

바로 오른쪽의 신발을 왼쪽으로 전달해나가면 왼쪽 학생들은 신발을 신을 수 있다.

그런데 그렇게 하다보면 제일 오른쪽에 있는 학생들은 신을 신발이 없다.

그렇다면 처음부터 끝까지 모든 신발 사이즈가 동일해야만 순열을 만들 수 있는걸까?

 

정답은 No!

저 위에서는 본인의 사이즈와 동일한 경우를 잘 고려하지 않은 케이스이다.

 

같은 신발 사이즈인 학생들은 서로 바꿔 신어야 한다. 그리고 그거보다 큰 신발을 신는 것은 불가능하다.

왜냐하면 작은 신발 사이즈를 큰 신발 사이즈를 신은 학생들에게 신기면, 큰 신발 사이즈인 학생들은...신을 신발이 없다..

 

그래서 결국 같은 신발 사이즈를 가진 학생들끼리만 신발을 바꿔신어야 한다.

 

여기서 문제가 발생했다.

나는 단순히 같은 신발 사이즈를 가진 구간의 신발 번호를 flip해줬다. 구간 내 같은 신발 사이즈를 가진 학생들의 수가 짝수라면 문제가 발생하지 않는데, 홀수라면 문제가 발생한다.

 

만약 1,2,3번 학생의 신발을 바꿔신으면 3,2,1이 된다. 즉 여기서 2번 학생은 본인의 신발을 신게 된다.

그래서 단순히 flip하는 게 아니라, 절대로 겹치지 않는 교환방식으로 바꾸니 통과되었다.

 

그 전에 같은 사이즈를 가진 학생이 없다면, 즉 혼자만 그 사이즈면 반드시 -1을 출력하도록 해야 한다.

 

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int t;
    
    cin >> t;
    while(t--) {
        long long n;
        cin >> n;
        
        vector<long long> shoes(n);
        for(long long i = 0;i < n;i++) {
            cin >> shoes[i];
        }
        
        if(n == 1) {
            cout << -1 << '\n';
            continue;
        }
        
        int start = 0;
        int end = 1;
        bool flag = true;
        vector<long long> answer;
        while(end < n) {
            if(shoes[start] == shoes[end]) {
                end++;
            }
            else {
                if(start == end - 1) {
                    flag = false;
                    break;
                }
                //start ~ end - 1
                answer.push_back(end);
                for(int i = start;i < end - 1;i++) {
                    answer.push_back(i + 1);
                }
                start = end;
            }
            
            if(end == n) {
                break;
            }
        }
        
        if(start == n - 1) {
            flag = false;
        }
        else {
            answer.push_back(n);
            for(int i = start;i < n - 1;i++) {
                answer.push_back(i + 1);
            }
        }
        
        if(flag) {
            for(long long i = 0;i < answer.size();i++) {
                cout << answer[i] << " ";
            }
        }
        else {
            cout << -1;
        }
        cout << '\n';
    }
    return 0;
}