백준 23968 : 알고리즘 수업 버블 정렬 1

출처 : https://www.acmicpc.net/problem/23968

---

문제

오늘도 서준이는 버블 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 버블 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 버블 정렬 의사 코드는 다음과 같다.

bubble_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2
        for i <- 1 to last - 1
            if (A[i] > A[i + 1]) then A[i] <-> A[i + 1]  # 원소 교환
}

---

생각

1. 버블 정렬 다 해야하는건가..
2. k 값을 하고 하나 스왑할때마다 횟수 카운트 해서 그 카운트 나오면 종료하는 식으로
3. k 값이 교환 횟수보다 크면 -1 출력

---

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    // 입력값이 10000 이여서 입력으로 시간 초가 날거 같지는 않음
    int n, k;
    cin >> n >> k;

    vector<int> nums(n, 0);

    for(int ix = 0; ix < n; ++ix)
    {
        cin >> nums[ix];
    }

    // 횟수
    int count = 0;

    for(int ix= 1; ix < n; ++ix)
    {
        for(int jx = 0; jx < n - ix; ++jx)
        {
            if(nums[jx] > nums[jx+1])
            {
                swap(nums[jx], nums[jx+1]);
                count++;
                if(count == k)
                {
                    cout << nums[jx] << " " << nums[jx+1];
                    return 0;
                }
            }
        }
    }
    cout << -1;
}

---

결과

• 문제 풀이 시간 : 5분
• 메모리 : 2020 KB
• 시간 :  144 ms

  ---

배운점 및 고칠점

• 스왑하는거 인지 잘하자