atcoder : B - Interactive Sorting

ㅋㅋ... 와 진짜 하루종일 걸렸다.

 

분명 연습문제라고 했는데,,, 왜이렇게 어려운지,,,

 

4시에 시작해서 7시 30분에 끝났으니까,,,

난 완전 실격이다ㅋㅎㅋㅋㅋㅋㅋㅋㅋㅋ

와중에 초반에 A에 잘못 제출해서 틀리기도 하고,,하하하

 

---

문제 자체는 간단하다! 그냥 평범한 sorting문제이다.

이 때, compare를 바로 알 수 있는게 아니라, 매번 물어봐야 하므로 query횟수에 제한이 생긴다.

 

나는 그래서 이미 정렬된 리스트에, 문자가 하나씩 들어온다는 느낌으로 구현하였다

int check(string *s, char c){
    int result = 0;
    int right = (int)(*s).size() - 1;
    int left = 0;
    
    while(true){
        int index = (right+left+1)/2;
        
        cout << "? "<< (*s)[index]<<" "<<c<<endl<<flush;
        result++;
        char compare;
        cin >> compare;
        if(compare == '<'){
            left = index+1;
        }else{
            right = index-1;
        }
        if(left > right){
            (*s).insert(left, 1, c);
            return result;
        } 
    }
}

int main(){
    int n, q;
    string s;
    cin >> n;
    cin >> q;
    if(n == 5){
        only_5();
    }else{
        s.push_back('A');

        cout << "? "<< s[0]<<" "<<'B'<<endl<<flush;
        char compare;
        cin >> compare;
        if(compare == '>'){
            s.insert(0, 1, 'B');
        }else{
            s.push_back('B');
        }

        int querys = 1;
        for(int i = 67; i<n+65; i++){
            querys += check(&s, (char)i);

        }
        cout <<"! "<< s << endl;
    }

    return 0;
}

이진 탐색처럼,,? 이걸 무슨 정렬이라고 부르는지 모르겠다..ㅋ

그냥 퀵정렬이라고 생각했는데, 그건 아니구,, 뭐지?

 

암튼 이렇게 하면 test1, test2는 무난하게 통과한다.

 

문제는 test3이었다.

n = 5, q = 7 로 고정되어 있는 케이스이다.

나는 이부분도 그냥 정렬 알고리즘에 냅다 넣으면 될것이라고 생각하고 (일반적인 케이스에 적용 가능)

check함수만 계속 고쳤다.. 5시 30분쯤까지 시도했던게 저것들이다.

 

하다보니까 안되서, 다른사람 풀이를,,ㅋㅋㅋㅋ 찾아봤는데!!!!

이럴수가 n=5인 경우만 따로 빼서 함수를 새로 작성해서 풀었다....ㅋㅋㅋㅋㅋ

q=7로 매우 작아서, 여기에 맞게 따로 작성한것 같았다.

그래서 그 뒤부터 코드길이가 엄청 길어지는데, n=5인 상황에 맞춰서 코드를 작성한 부분이다

void only_5(){
    string s = "ABCDE";
    char compare;
    int q = 0;
    
    // sort s[0] s[1]
    cout << "? "<< s[0]<<" "<<s[1]<<endl<<flush;
    cin >> compare;
    if(compare == '>'){
        char temp = s[0];
        s[0] = s[1];
        s[1] = temp;
    }

    // sort s[2] s[3]
    cout << "? "<< s[2]<<" "<<s[3]<<endl<<flush;
    cin >> compare;
    if(compare == '>'){
        char temp = s[2];
        s[2] = s[3];
        s[3] = temp;
    }

    // sort s[0] s[1] vs s[2] s[3]
    cout << "? "<< s[0]<<" "<<s[2]<<endl<<flush;
    cin >> compare;
    if(compare == '>'){
        // s[2] s[0] s[1], s[3], s[4]
        // s[2] < s[3]
        int temp0 = s[0];
        int temp1 = s[1];
        int temp2 = s[2];
        s[0] = temp2;
        s[1] = temp0;
        s[2] = temp1;
    }else{
        // s[0] s[2] s[3], s[1], s[4]
        // s[0] < s[1]
        int temp1 = s[1];
        int temp2 = s[2];
        int temp3 = s[3];
        s[1] = temp2;
        s[2] = temp3;
        s[3] = temp1;
    }

    // q = 3
    // s[0] s[1] s[2] , s[3], s[4]
    // s[0] < s[3] !!

    // sort s[0] s[1] s[2], s[4]
    cout << "? "<< s[1]<<" "<<s[4]<<endl<<flush;
    cin >> compare;
    if(compare == '<'){
        cout << "? "<< s[2]<<" "<<s[4]<<endl<<flush;
        cin >> compare;
        if(compare == '<'){
            // s[0] s[1] s[2] s[4], s[3]
            int temp = s[3];
            s[3] = s[4];
            s[4] = temp;
        }else{
            // s[0] s[1] s[4] s[2], s[3]
            int temp2 = s[2];
            int temp3 = s[3];
            int temp4 = s[4];
            s[2] = temp4;
            s[3] = temp2;
            s[4] = temp3;
        }
    }else{
        cout << "? "<< s[0]<<" "<<s[4]<<endl<<flush;
        cin >> compare;
        if(compare == '<'){
            //s[0] s[4] s[1] s[2], s[3] 
            int temp1 = s[1];
            int temp2 = s[2];
            int temp3 = s[3];
            int temp4 = s[4];
            s[1] = temp4;
            s[2] = temp1;
            s[3] = temp2;
            s[4] = temp3;
        }else{
            //s[4] s[0] s[1] s[2], s[3]
            int temp0 = s[0];
            int temp1 = s[1];
            int temp2 = s[2];
            int temp3 = s[3];
            int temp4 = s[4];
            s[0] = temp4;
            s[1] = temp0;
            s[2] = temp1;
            s[3] = temp2;
            s[4] = temp3;
        }
    }
    // q = 5
    // s[0] s[1] s[2] s[3], s[4]
    // s[0] < s[4]

    // sort s[4]
    cout << "? "<< s[2]<<" "<<s[4]<<endl<<flush;
    cin >> compare;
    if(compare == '<'){
        // check s[3]
        cout << "? "<< s[3]<<" "<<s[4]<<endl<<flush;
        cin >> compare;
        if(compare == '<'){
            // s[0] s[1] s[2] s[3] s[4]
            cout << "! "<< s[0]<<s[1]<<s[2]<<s[3]<<s[4]<<endl;
            return;
        }else{
            // s[0] s[1] s[2] s[4] s[3]
            cout << "! "<< s[0]<<s[1]<<s[2]<<s[4]<<s[3]<<endl;
            return;
        }

    }else{
        // check s[1]
        cout << "? "<< s[1]<<" "<<s[4]<<endl<<flush;
        cin >> compare;
        if(compare == '<'){
            // s[0] s[1] s[4] s[2] s[3]
            cout << "! "<< s[0]<<s[1]<<s[4]<<s[2]<<s[3]<<endl;
            return;
        }else{
            // s[0] s[4] s[1] s[2] s[3]
            cout << "! "<< s[0]<<s[4]<<s[1]<<s[2]<<s[3]<<endl;
            return;
        }
    }
    
    

}

가장 중요한 부분은, 정렬할 때 최악의 query개수를 생각해야 한다.

예를들어 [1, 2, 3] 3개의 원소를 가진 배열이 이미 정렬된 상태에서, 새로운 원소가 들어올 때

방법1 : 첫번째 부터 하나씩 비교

=> 만약 0이 들어온경우, 비교1번으로 끝나지만

=> 만약 4가 들어온경우, 모든 원소를 비교해야 한다 (3번 비교)

=> 즉 query의 개수가 최악의 경우 3번, 최선의 경우 1번 필요하다

방법2 : 중간부터 양옆으로 나아가며 비교

=> 만약 0이 들어온경우, 2비교, 1비교 2번이 필요하다

=> 만약 4가 들어온경우, 2비교, 3비교 2번이 필요하다

=> 즉 최악의 경우 query가 2번만 필요하다.

 

=> 이렇게 생각했을 때, 최선의 경우를 가진 두번째 방법을 이용해주는게 더 좋다!

 

코드는 전부 if로 되어있어 이해가 쉽다..

그리고 애초에 길이다 5로 고정되어 있어서 그냥 swap이나, slide 를 구현하지 않고 냅다 temp 이용해서 하드코딩했다

당장 이해하는게 급해서 저게 더 편했던것 같다. ㅋㅎ

 

s[0] s[1] s[2] s[3] s[4] 로 시작되었을 때

 

query 1 : s[0] s[1] 정렬

query 2 : s[2] s[3] 정렬

=> //s[0] s[1] // s[2] s[3] // s[4] 모양으로 정렬되어 있다 (각 정렬된 배열끼리는, 대소관계를 알 수 없음)

query 3 : 길이가 3인 정렬된 배열을 만들어준다.

s[0] s[2] 를 비교해서

-> s[0] s[2] s[3] 또는 s[2] s[0] s[1] 형태의 정렬된 배열을 만들어준다

적절히 swap해주면

=> s[0] s[1] s[2] // s[3] // s[4] 형태의 정렬된 배열을 만들 수 있다.

-> 이 때 s[0] < s[3] 을 만족하도록 해준다.

query 4, 5 : s[0] s[1] s[2] + s[4] 를 정렬해준다

=> 여기서!! 두번째 방법을 이용해 정렬해준다 (query 2번으로 해결가능)

절절히 swap해주면

=> s[0] s[1] s[2] s[3] // s[4] 형태의 정렬된 배열을 만들 수 있다.

query 6, 7 : s[4] 도 정렬해준다

=> 이때, 위 과정에서 s[0] < s[4] 를 만족하도록 swap해주었으므로,

=> s[1] s[2] s[3] + s[4] 를 정렬하는것과 같게 생각할 수 있다.

=> 두번째 방법을 한번 더 사용하면 된다

 

이러면 무조건 query를 7번만 사용하고 정렬을 마무리할 수 있다.

 

---

하... 이거때문에 3시간동안...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래도 해결하니까 뿌듯하긴 한데

정렬문제에 이렇게 쩔쩔매다니 너무 충격적이다.

마지막 테스트케이스는,,, 앞으로 문제를 잘 읽고

이렇게 독특한 경우는 그냥 하드코딩을 바로 할 수 있는 사람이 되어야겠다.