2021-08-25 게시 됨2021-09-21 업데이트 됨Algorithm / Codeforces / Problems

Codeforces Round #740 (Div. 2) Problem. A

https://codeforces.com/contest/1561/problem/A
Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

A. Simply Strange Sort

TimeLimit	MemoryLimit	Difficulty	Tags
2 S	512 MB	800	`brute force` `implementation` `sortings`

Attr	SubNo	SolveTime	Time	Memory	Accept?
1	126892151	20min	31 ms	3600KB	Wrong answer
2	126900288	+25min (45m)	46 ms	3700KB	Accepted

문제 요약

조금 이상한 정렬..

n개의 원소를 가지고있는 배열 a(n개의 원소를 가진 배열, n: 홀수)이 주어진다.
배열 a를 오름차순으로 정렬한다.

알고리즘: f(i)를 수행한다.
i는 (1 <= i <= n-1)사이로 수행되고, 각 다음과 같은 알고리즘을 사용한다 :
만약 **a_i > a_i+1**이면, **a_i 와 a_i+1의 값을 변경한다.

알고리즘은 반복으로 구성되고, 숫자 1부터 시작한다. i번째 반복일 때, 다음과 같은 알고리즘을 수행한다

만약 i가 홀수이면: f(1), f(3),…,f(n-2);를 호출
만약 i가 짝수이면: f(2), f(4),…,f(n-1);를 호출

배열이 오름차순으로 정렬될 때까지 반복한다.

몇번의 반복을 해야 오름차순으로 정렬되는지 구하는 문제…

피드백

Input

1-st line : Testcase (1 <= t <= 100)
각 Testcase 마다
1-st line : 1개의 정수 (1 <= n <= 1000, n: 홀수)
2-nd line : n개의 정수 a₁, a₂…,a_n (1 <= a_i <= n)

모든 테스트케이스의 n의 합이 999를 넘지 않는다.

Output

각 Testcase 마다
최초로 오름차순으로 정렬이 되는 최소 반복 횟수를 출력

이미 정렬이 되어있다면, 0을 출력

문제 풀이

그냥 무시정으로 반복해도 해결할 수 있는 문제이다. 알고리즘도 다 알려주고 위에서 시키는대로 코드를 짜기만 하면 되는 문제

Attr 1 (Wrong answer on pretest 2)

처음에는 checkSorted라는 변수를 하나 만들어서 반복문 안에서 변경되는 점이 있으면 checkSorted를 꺼주고, checkSorted가 꺼지지 않으면 정렬이 된것으로 보고 반복문을 탈출시켜주는 코드였다.

에러가 떴다.

#include <iostream>
 
using namespace std;
 
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int result = 0;
        int n, arr[1001];
        cin >> n;
        arr[0] = 0;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        while(true) {
            result ++;
            int checkSorted = true;
            for(int i = (result%2==0?2:1); i < n; i+=2) {
                if(arr[i] > arr[i+1]) {
                    //cout << "exchange " << arr[i] << " and " << arr[i+1] << endl;
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    checkSorted = false;
                }
                if(arr[i-1] > arr[i]) checkSorted = false;
            }
            if(checkSorted) break;
        }
        
        cout << result - 1 << endl;
    }
    
    return 0;
}

Attr 2 (Accepted!)

에러가 날만한 테스트 케이스를 하나씩 넣어봤는데 바로 발견할 수 있었다.

1 2	5 1 2 3 5 4

위의 케이스를 넣었을때, 확인이 되지않고 0으로 출력이 되었다.
바로 해결할 수 있는 문제였는데, 햇갈려서 알고리즘을 다시 짜는 수준까지 가버렸다.

시간이 더 걸리더라도 그냥 배열이 정렬되었는지 미리 확인을 하는 코드를 추가했는데, 시간제한이 넉넉하다보니 문제없이 잘 작동하였었다.

~~바로 해결하지 못한 이유는 위 케이스의 답이 2가아닌 1이라 생각하고 삽질하고 있었다…~~

최종 해설

위의 해설이랑 똑같이 만들었다.

n을 먼저받고, 문제에서 1부터 시작했기 때문에 햇갈리지 않기 위해서 배열의 0은 0으로 채워주고 1부터 입력값을 받아주었다. (1~`n`)

그다음 정렬이 될 때까지 무한반복을 해주는데, 먼저 배열이 정렬되었는지 확인을 해준다. 단순히 for문으로 반복하면서 비교를 해주었다.

정렬이 되지않았으면 result값을 1 더해주고 문제에 나온 알고리즘을 수행해준다.

이렇게 반복하면 어렵지 않게 답을 구할 수 있다.

최종 코드

#include <iostream>
 
using namespace std;
 
 
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int result = 0;
        int n, arr[1001];
        cin >> n;
        arr[0] = 0;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        while(true) {
            //check if array sorted
            int i = 1;
            for(i; i < n; i++) 
                if(arr[i] > arr[i+1])
                    break;
            if(i == n) break;
 
            result ++;
            for(int i = (result%2==0?2:1); i < n; i+=2) {
                if(arr[i] > arr[i+1]) {
                    //cout << "exchange " << arr[i] << " and " << arr[i+1] << endl;
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            
        }
        
        cout << result << endl;
    }
    
    return 0;
}

느낀점

알람은 미리미리 맞춰놓자.
정신좀 차리자.

#Algorithm Problem Solve