[Java] 백준 1015 (수열 정렬) 자바 문제 풀이

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

 

 

알고리즘 분류

• 정렬

 

똑같은 두개의 배열을 두고 하나는 비내림차순(오름차순) 으로 정렬할 때

순서에 맞게 index 번호를 출력하는 문제이다.

 

 

우선, StringTokenizer를 사용하여 입력된 수들을 배열에 하나씩 저장하였다.

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < temp.length; i++) {
			temp[i] = Integer.parseInt(st.nextToken());
		} // for

 

 

 

 

그 다음, 배열을 복사한 뒤 원본 배열은 Arrays.sort() 함수를 사용하여 오름차순으로 정렬해주었다

		int [] arr = temp.clone();
		Arrays.sort(temp);

 

 

 

이제 두 개의 배열을 비교하며 원래 배열의 각 요소가 정렬된 배열에서 어떤 인덱스에 위치하는지 찾아내었다.

중복되는 값이 있을 수 있으므로, 이미 방문한 인덱스는 -1로 변경하여 중복 처리를 방지하였다.

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if(arr[i] == temp[j]) {
					sb.append(j).append(" ");
					temp[j] = -1;
					break;
				}
			}
		}

 

위 과정을 통해 각 요소의 인덱스를 StringBuilder에 순서대로 저장하였다.

 

아래는 전체 코드이다.

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

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

		int []temp = new int [N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < temp.length; i++) {
			temp[i] = Integer.parseInt(st.nextToken());
		} // for
		
		int [] arr = temp.clone();
		Arrays.sort(temp);
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if(arr[i] == temp[j]) {
					sb.append(j).append(" ");
					temp[j] = -1;
					break;
				}
			}
		}
		
		System.out.println(sb.toString());
	}
}