[ 백준 - 1377 ] 버블 소트

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

문제 이름은 버블 소트 이지만.... 버블 소트를 구현하는 문제는 아니였다.

물론 O(n^2)의 느린 기본적인 정렬이기 때문에 아닐거라고는 예상은 했지만...

어쨋든 시간내에 풀지는 못하고, 책에 있는 코드를 보고 풀었다.

---

[ 📌 풀이 ]

swap이 되지 않은 루프의 인덱스를 구하는 문제이다.

1) 기본으로 제공하는 sort 함수를 이용한다.

2) sorted 배열의 인덱스와 기존에 있던 배열의 인덱스의 차이를 보고 최대 값을 구한다.

 

최대 값의 의미: 버블 정렬은 요소를 바로 옆으로 이동하기 때문에 이동거리가 1씩 증가면서 가장 마지막 인덱스의 요소는 최대 값이 들어간다.

그렇기 때문에 한 번의 sorting이 진행이 되면 1씩 증가하게 되는데 swap이 필요없는 요소는 양수로 남게 된다.

 

Example)
number             => 10 1  5  2  3
sorted number =>  1  2  3  5  10

index             => 0  1   2  3  4
sorted index => 1  3  4  2  0

gap => 1  2  2  -1  -4

gap에 2부터는 swap이 이뤄지지 않았다고 보면 된다. (swap이 이뤄지지 않는지 돌아가는 반복문도 포함해서 + 1)

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.11.24(Fri)
# Spend Time: overtime 30m
# Runtime   : 1008 ms
# Memory    : 105516 KB
# Algoritm  : Bubble Sort
"""

import sys
input = sys.stdin.readline

N = int(input())
arr = []

for idx in range(N):
  arr.append((int(input()), idx))

Max = 0
sorted_arr = sorted(arr)

for i in range(N):
  if Max < sorted_arr[i][1] - i:
    Max = sorted_arr[i][1] - i


print(Max + 1)

 

[ 📌 코드 - Java ]

/**
* Author    : Lee In Bok 
* Date      : 2023.11.24(Fri)
* Spend Time: overtime 30m
* Runtime   : 1784 ms
* Memory    : 76172 KB
* Algoritm  : Bubble Sort
 */
 
package BaekJoon.Sorting.Q1377;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

class Q1377_BubbleSort{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Num[] arr = new Num[N];
        Num[] sorted = new Num[N];

        for(int i = 0; i < N; i++){
            Num num = new Num(Integer.parseInt(br.readLine()), i);
            arr[i] = num;
        }

        Arrays.sort(arr, new Comparator<Num>() {
            public int compare(Num n1, Num n2){
                return n1.num - n2.num;
            }
        });

        int max = 0;

        for(int i = 0; i < N; i++){
            if(max < arr[i].orgIdx - i){
                max = arr[i].orgIdx - i;
            }
        }

        System.out.println(max + 1);
    }
}

class Num{
  int num;
  int orgIdx;

  Num(int num, int orgIdx){
    this.num = num;
    this.orgIdx = orgIdx;
  }
}

---

[ 📌 결과 - Python & Java ]

[ Result - Python & Java ]