백준 번호표 교환 (99클럽 코딩테스트 25일차 TIL)

목표

이번에는 백준사이트에서 알고리즘을 문제를 풀어야할것같다. 프로그래머스에서 적응을 했는데 다른 사이트에서 알고리즘을 풀려고하니깐 적응에 시간이 필요한것같다. 그래서 적응하기 위해서 백준사이트에서 공부할려고 노력한다.

문제

내가 생각했을때 문제에서 원하는부분

첫 번째 줄에 학생의 수와 카드의 수를 나타내는 정수 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) 이 공백으로 구분되어 입력된다.
두 번째 줄부터 N줄에 걸쳐서 각 학생이 가지는 번호표의 값 Ai (1 ≤ Ai ≤ 1000) 가 주어진다.
게임이 종료된 후에 각 학생이 가지는 번호표의 값을 한 줄에 하나씩 출력한다.

내가 이 문제를 보고 생각해본 부분

입력 데이터가 이미 순서대로 주어지기 때문에 버블 정렬을 사용하면 교환 횟수를 최소화할 수 있다고 생각했다.
버블 정렬은 구현이 간단하고 직관적인 알고리즘이어서 선택했다.
문제의 게임 규칙에 따라 M번의 카드 순환이 모두 끝난 후의 결과를 출력해야 한다.
이를 위해 k번 카드 순환을 바깥쪽 for문으로 처리했다.
문제에서 제시한 대로 modulo 연산 후의 값을 비교하여 정렬한다.

코드로 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        for(int k = 1; k <= M; k++) {
            for(int j = 0; j < N-1; j++) {
                if(A[j]%k > A[j+1]%k) {
                    int temp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = temp;
                }
            }
        }

        for(int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
        sc.close();
    }
}

시간복잡도 O(N^2)

장점
구현이 쉽다.
데이터의 순서에 영향을 받지 않는다.
추가 메모리를 필요로 하지 않는다.
데이터의 최악의 경우에도 잘 동작한다.

단점
시간 복잡도가 높다.
데이터 크기가 커지면 수행 속도가 급격히 느려진다.
이미 정렬된 배열의 경우 불필요한 교환이 많이 발생한다.

마무리

오늘은 이렇게 백준 사이트에서 알고리즘 문제를 풀었는데 프로그래머스랑 다르게 어렵게 느껴지는것같다. 문제를 아직 많이 안풀어봐서 그런것같다.