Codeforces : 144A - Arrival of the General

문제

• 링크

코드

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

public class A_Arrival_of_the_General {
	
	static BufferedReader br;
	static StringTokenizer stk;
	static StringTokenizer toToken(String msg) {
		stk = new StringTokenizer(msg);
		return stk;
	}
	static int toInt(String msg) {
		return Integer.parseInt(msg);
	}
	
	static int N;
	static int[] arr;
	static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	static int size=0;
	public static void main(String[] args) throws IOException{
		br = new BufferedReader(new InputStreamReader(System.in));
		N = toInt(br.readLine());
		arr = new int[N];
		stk = toToken(br.readLine());
		for(int i = 0 ; i < N ; i++) {
			arr[i] = toInt(stk.nextToken());
		}
		int minIndex = Integer.MAX_VALUE;
		int minValue = Integer.MAX_VALUE;
		for(int i = 0 ; i < N ; i++) {
			if(minValue >= arr[i]) {
				minValue = arr[i];
				minIndex = i;
			}
		}
		for(int i = minIndex ; i < N-1 ; i++) {
			swap(i,i+1);
			size++;
		}
		
//		System.out.println(Arrays.toString(arr));
//		System.out.println(size);
		
		
		int maxIndex = Integer.MIN_VALUE;
		int maxValue = Integer.MIN_VALUE;
		for(int i = N-1 ; i >= 0 ; i--) {
			if(maxValue <= arr[i]) {
				maxValue = arr[i];
				maxIndex = i;
			}
		}
		for(int i = maxIndex ; i > 0 ; i--) {
			swap(i,i-1);
			size++;
		}
	
//		System.out.println(Arrays.toString(arr));
		System.out.println(size);
		
	}
	
}

회고

• 문제에서 역방향 순서대로 정렬 방식을 직접 구현

• 중복되는 것이 있으면, 최소값의 위치를 구하는 부분에서는 가장 우측에 있는 친구를

• 중복되는 최대값의 위치를 구하는 부분에서는 가장 좌측에 있는 최대값의 위치를 반환

• 그래야 최소 횟수의 이동으로 장군이 원하는 정렬을 만들 수 있음