[알고리즘 / 백준] 2750 - 수 정렬하기

 

문제는 위와 같으며 기본적으로 제공되는 sort() 를 사용하여 문제를 해결하였습니다.

 

먼저 파이썬 코드는 다음과 같습니다.

from sys import stdin

N = int(stdin.readline())
nums = list()
for _ in range(N):
    nums.append(int(stdin.readline()))

nums.sort()
print("\n".join(str(i) for i in nums))

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }
}

 

이외에도 기본적인 정렬 방법을 통해 문제를 해결할 수 있습니다.

 

1. 선택 정렬

주어진 리스트에서 최소값을 찾아 맨 앞 데이터와 바꿔주고 맨 앞 데이터를 뺀 나머지 데이터를 다시 비교, 반복하며 앞에서부터 정렬하는 방식입니다.

 

파이썬 코드입니다.

from sys import stdin

N = int(stdin.readline())
data_list = list()
for _ in range(N):
    data_list.append(int(stdin.readline()))

for stand in range(len(data_list) - 1):
    lowest = stand # 가장 작은 원소의 인덱스
    for num in range(stand + 1, len(data_list)):
        if data_list[lowest] > data_list[num]:
            lowest = num
    data_list[stand], data_list[lowest] = data_list[lowest], data_list[stand] # 가장 작은 원소를 찾아 swap

for i in range(len(data_list)):
    print(data_list[i])

 

자바 코드입니다.

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int stand = 0; stand < dataList.length - 1; stand++) {
            int lowest = stand; // 가장 작은 원소의 인덱스
            for (int num = stand + 1; num < dataList.length; num++) {
                if (dataList[lowest] > dataList[num]) {
                    lowest = num;
                }
            }
            // swap
            int tmp = dataList[stand];
            dataList[stand] = dataList[lowest];
            dataList[lowest] = tmp;
        }

        for (int i = 0; i < dataList.length; i++) {
            System.out.println(dataList[i]);
        }
    }
}

 

2. 버블 정렬

두 인접 데이터를 비교하여 앞에 있는 데이터가 더 큰 경우 둘의 위치를 바꾸는 방식으로 뒤에서부터 정렬되는 방식입니다.

 

파이썬 코드입니다.

from sys import stdin

N = int(stdin.readline())
bs = list()
for _ in range(N):
    num = int(stdin.readline())
    bs.append(num)

for i in range(len(bs) - 1):
    swap = False
    for index in range(len(bs) - i - 1):
        if bs[index] > bs[index+1]:
            bs[index], bs[index+1] = bs[index+1], bs[index]
            swap = True

    if swap == False:
        break

for i in range(len(bs)):
    print(bs[i])

 

자바 코드입니다.

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < bs.length - 1; i++) {
            boolean swap = false;
            for (int index = 0; index < bs.length - i - 1; index++) {
                if (bs[index] > bs[index+1]) {
                    int tmp = bs[index];
                    bs[index] = bs[index+1];
                    bs[index+1] = tmp;
                    swap = true;
                }
            }

            if (!swap) {
                break;
            }
        }

        for (int i = 0; i < bs.length; i++) {
            System.out.println(bs[i]);
        }
    }
}

 

3. 삽입 정렬

두 번째 인덱스부터 시작하여 앞에 있는 데이터(B)와 비교하고 기준 인덱스 데이터가 저 작으면 데이터를 서로 바꾸다가 기준 인덱스 데이터가 더 큰 경우가 되면 해당 반복을 중지하고 기준 인덱스를 원래 기준 인덱스의 다음으로 이동시키면서 정렬하는 방법입니다.

 

파이썬 코드입니다.

from sys import stdin

N = int(stdin.readline())
data_list = list()
for _ in range(N):
    data_list.append(int(stdin.readline()))

for stand in range(len(data_list) - 1):
    for num in range(stand + 1, 0, -1):
        if data_list[num] < data_list[num - 1]:
            data_list[num], data_list[num - 1] = data_list[num - 1], data_list[num]
        else:
            break

for i in range(len(data_list)):
    print(data_list[i])

 

자바 코드입니다.

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int stand = 0; stand < dataList.length - 1; stand++) {
            for (int num = stand + 1; num > 0; num--) {
                if (dataList[num] < dataList[num - 1]) {
                    int tmp = dataList[num];
                    dataList[num] = dataList[num - 1];
                    dataList[num - 1] = tmp;
                }
            }
        }

        for (int i = 0; i < dataList.length; i++) {
            System.out.println(dataList[i]);
        }
    }
}