문제
서로 다른 세 자연수를 입력받아 오름차순으로 정렬하여 출력하는 문제이다. 세 수는 한 줄에 공백으로 구분되어 주어진다.
입력
첫째 줄에 서로 다른 세 자연수가 공백으로 구분되어 주어진다. 각 수는 1 이상 1,000,000 이하이다.
출력
첫째 줄에 세 수를 오름차순으로 정렬하여 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 2 | 1 2 3 |
풀이
세 수만 비교하므로 라이브러리 없이 직접 교환(swap) 3회로 정렬한다. 선택 정렬 방식으로 가장 작은 수를 첫 번째 자리로 보내고, 나머지 두 수를 비교해 정렬한다.
- 한 줄의 입력을
StringTokenizer로 파싱하여 크기 3짜리 배열에 저장한다. arr[0]과arr[1]을 비교해 필요하면 교환한다.arr[1]과arr[2]를 비교해 필요하면 교환한다.arr[0]과arr[1]을 다시 비교해 필요하면 교환한다.- 세 수를 공백으로 구분하여 출력한다.
핵심 아이디어: 원소 3개를 정렬하는 데는 최대 3번의 비교·교환으로 충분하다. 버블 정렬 1패스(0→1, 1→2 교환) 후 0→1을 한 번 더 비교하면 세 수가 정렬된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day07BOJ2752세수정렬 { // 2752 세수정렬
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[3];
arr[0] = Integer.parseInt(st.nextToken());
arr[1] = Integer.parseInt(st.nextToken());
arr[2] = Integer.parseInt(st.nextToken());
if (arr[0] > arr[1]) {
int temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}
if (arr[1] > arr[2]) {
int temp = arr[1];
arr[1] = arr[2];
arr[2] = temp;
}
if (arr[0] > arr[1]) {
int temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}
System.out.println(arr[0] + " " + arr[1] + " " + arr[2]);
}
}복잡도
- 시간: O(1) — 입력 크기가 3으로 고정. 비교·교환 연산이 상수 번
- 공간: O(1) — 크기 3의 고정 배열