[백준] 12단계 문제 모음

12

정렬

배열의 원소를 순서대로 나열하는 알고리즘

---

1

2750

수 정렬하기

시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(bfr.readLine());
		//ArrayList<Integer> array = new ArrayList<Integer>();
		int a[] = new int[T];
		for(int i = 0 ; i<T; i++)
		a[i] = (Integer.parseInt(bfr.readLine()));
		
		Arrays.sort(a);
		
		for(int i=0; i<T; i++)
			bfw.write(a[i] + "\n");
		
		bfw.flush();
		bfw.close();
	}

}

 

 

---

2

2751

수 정렬하기 2

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;


public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(bfr.readLine());
		ArrayList<Integer> array = new ArrayList<Integer>();
		for(int i = 0 ; i<T; i++)
			array.add(Integer.parseInt(bfr.readLine()));
		
		Collections.sort(array);
		
		for(int i=0; i<T; i++)
			bfw.write(array.get(i) + "\n");
		
		bfw.flush();
		bfw.close();
	}

}

 

 

---

3

10989

수 정렬하기 3

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(bfr.readLine());
		//ArrayList<Integer> array = new ArrayList<Integer>();
		int a[] = new int[T];
		for(int i = 0 ; i<T; i++)
		a[i] = (Integer.parseInt(bfr.readLine()));
		
		Arrays.sort(a);
		
		for(int i=0; i<T; i++)
			bfw.write(a[i] + "\n");
		
		bfw.flush();
		bfw.close();
	}

}

 

 

---

4

2108

통계학

정렬을 활용하는 문제

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int array[] = new int[T];
		for(int i=0; i<T; i++)
			array[i] = scan.nextInt();
		
		Arrays.sort(array);
		
		//산술평균
		double sum = 0;
		for(int i = 0; i<T; i++) 
			sum += array[i];
		System.out.println(Math.round((double)sum/T));//반올림

		//중앙값
		System.out.println(array[T/2]);
		
		//최빈값
		int count[] = new int[T];
		int x= 0;
		count[0]++;
		for(int i = 1; i<T; i++) {
			if(array[i] == array[i-1])
				count[x] ++;
			else {
				x = i;
				count[x]++;
			}
		}
		int max = 0;
		int counting = 0;
		for(int i=0; i<T; i++) {
			if(max< count[i]) {
				max = count[i];
				counting = i;
			}
		}
		int testcount = 0;
		for(int i=0; i<T; i++) {
			if(max == count[i]) testcount++;
			if(testcount ==2) {
				counting = i;
				break;
			}
		}
		
		System.out.println(array[counting]);
		
		//범위
		System.out.println(array[array.length-1] - array[0]);
		
	}

}

 

 

---

5

1427

소트인사이드

숫자를 정렬하는 문제

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String N = scan.nextLine();
		char array[] = new char[N.length()];
		for(int i =0; i<N.length(); i++) {
			array[i] = N.charAt(i);
		}
		Arrays.sort(array);
		
		for(int i=array.length-1; i>-1; i--)
			System.out.print(array[i]);

	}

}

 

 

---

6

11650

좌표 정렬하기

좌표를 정렬하는 문제

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int position[][] = new int [T][2];
		for(int i=0; i<T; i++) {
			position[i][0] = scan.nextInt();
			position[i][1] = scan.nextInt();
		}
		
		Arrays.sort(position, new Comparator<int[]>() {
			public int compare(int a[], int b[]) {
				if(a[0]==b[0]) return a[1]-b[1];
				else return a[0] - b[0];
			}
		});
		
		for(int i=0; i<T; i++) {
			
		
			System.out.println(position[i][0] + " " +position[i][1]);
			
		}
	}

}

 

 

---

7

11651

좌표 정렬하기 2

좌표를 다른 순서로 정렬하는 문제

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int position[][] = new int [T][2];
		for(int i=0; i<T; i++) {
			position[i][0] = scan.nextInt();
			position[i][1] = scan.nextInt();
		}
		
		Arrays.sort(position, new Comparator<int[]>() {
			public int compare(int a[], int b[]) {
				if(a[1]==b[1]) return a[0]-b[0];
				else return a[1] - b[1];
			}
		});
		
		for(int i=0; i<T; i++) {
			
		
			System.out.println(position[i][0] + " " +position[i][1]);
			
		}
	}

}

 

 

---

8

1181

단어 정렬

단어의 순서를 정의하여 정렬하는 문제

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		scan.nextLine();
		String array[] = new String[T];
		for(int i=0; i<T; i++) 
			array[i] = scan.nextLine();
		
		
		Arrays.sort(array, new Comparator<String>() {
			public int compare(String a, String b) {
				if(a.length() == b.length()) return a.compareTo(b);
				else return a.length() - b.length();
			}
		});
		System.out.println(array[0]);
		for(int i=1; i<T; i++) {
			if(!array[i].equals(array[i-1]))
			System.out.println(array[i]);
			
		}
	}

}

 

 

 

---

9

10814

나이순 정렬

값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘을 안정 정렬(stable sort)이라고 합니다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		String array[][] = new String [T][2];
		for(int i = 0 ; i<T; i++) {
			array[i][0] = scan.next();
			array[i][1] = scan.next();
		}
		
		Arrays.sort(array, new Comparator<String[]>() {
			public int compare(String[] a, String[] b) {
				return Integer.parseInt(a[0]) - Integer.parseInt(b[0]);
			}
		});
		
		for(int i=0; i<T; i++) {
			System.out.println(array[i][0] + " " + array[i][1]);
		}
	}

}