[Baekjoon] 1083_소트

Gold V

문제(출처: https://www.acmicpc.net/problem/1083)

---

< 소트 >

 

문제 풀이 

 

가장 큰 값부터 앞으로 올 수 있는지 확인하며 가능하면 앞으로 가져온다.

 

 my solution (Java)

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;
import java.util.Comparator;
import java.util.StringTokenizer;

public class _1083_ { // 소트
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		ArrayList<int[]> list = new ArrayList<>();

		ArrayList<Integer> arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			arr.add(Integer.parseInt(st.nextToken()));
			list.add(new int[] { i, arr.get(i) });
		}

		int s = Integer.parseInt(bf.readLine());

		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[1] == o2[1])
					return o1[0] - o2[0];
				return o2[1] - o1[1];
			}
		});

		int idx = 0;

		while (s > 0) {
			for (int i = 0; i < list.size(); i++) {
				int info[] = list.get(i);
				if (info[1] > arr.get(idx) && info[0] - idx <= s) {
					s -= (info[0] - idx);
					arr.remove(info[0]);
					arr.add(idx, info[1]);
					break;
				}
			}
			list.clear();

			idx += 1;

			if (idx == n) {
				break;
			}

			for (int i = idx; i < n; i++) {
				list.add(new int[] { i, arr.get(i) });
			}

			Collections.sort(list, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					if (o1[1] == o2[1])
						return o1[0] - o2[0];
					return o2[1] - o1[1];
				}
			});
		}

		for (int i = 0; i < n; i++) {
			bw.write(arr.get(i) + " ");
		}
		bw.flush();
	}
}

변수)
n : 배열 크기
list : [index, 배열 값]
arr : 배열
s : 최대 교환 횟수
idx : 배열 바꿀 위치

 

배열 크기를 입력받는다. 배열 크기만큼 배열 값을 입력받아 arr에 저장한다. 소트한 결과가 사전순으로 가장 뒷서는 것을 출력하려면 큰 값이 앞에 와야 한다. ArrayList에 [index, 배열 값]을 저장한 후 배열 값이 큰 순서대로, 배열 값이 같다면 index가 작은 순서대로 정렬한다. 배열 0번째 값부터 큰 값으로 바꾸기 위해 idx를 0으로 초기화하며 s가 0보다 클 때 다음 과정을 반복한다.

 

1) 정렬한 list를 순환하며 현재 idx위치에 있는 배열 값 보다 크고 교환 횟수가 남아있다면 교환 횟수를 차감하고 값을 idx위치로 가져온 후 순환을 종료한다.

2) list를 비우고 다음 위치의 배열 값을 교한해야 하므로 idx+1을 한다.

3) idx가 n과 같다면 더 이상 교환할 값이 없으므로 종료한다.

4) 배열의 idx번째 값부터 끝까지 list에 [index, 배열 값]을 저장한 후 위에서의 정렬 조건과 똑같이 정렬한다.

 

배열을 출력한다.

---

---