[선택정렬] 백준 1427번

문제

1번째 줄에 정렬할 수 N이 주어진다.
N은 1,000,000,000 보다 작거나 같은 자연수다
(주어진 N을 내림차순으로 정렬하시오)

 

문제분석

- 자연수를 받아서, 정렬하는 문제이므로 먼저 숫자를 배열로 넣어야한다
ex) 2143 -> 2,1,4,3 (분리필요)
- 선택 정렬을 이용하여 문제풀이 진행

• 과정
  • 빨간색 : 정렬된 수
  • 파란색 : 정렬해야하는 범위

순서	과정
첫번째	4	1	2	3
두번째	4	3	2	1
세번째	4	3	2	1

 

슈도코드

N(정렬할 수 입력)
arr(N을 분리하여 배열로 저장)
for(i=0 ~ arr 크기만큼 반복){
   for(j= i ~ arr 크기만큼반복){
       현재 범위에서 최대 인덱스값 찾기
   }
   if (현재 i값과 maxIdx값이 다르면){
       swap (arr[i], arr[maxIdx])
   }
}

정렬된 배열 출력

 

구현하기

• 입력받은 값 분리 방법 2가지
  • 방법1) 나머지연산 이용하기
  • 방법2 ) substring() 이용하기
    • 항상 숫자를 받는경우가 아닐수 있으므로, 예외처리는 필요 (왠만하면 문자열로 나누는 것을 사용 권장)
• 선택정렬 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            
        String inputStringArray = bf.readLine();
        int arrSize = inputStringArray.length();
        int []arr = new int[arrSize];

        /*
         * 나머지를 이용한 array 나누기 (방법1)
         */
        int inputIntArr = Integer.parseInt(inputStringArray);
        int remainNum = inputIntArr;
        for(int i = arrSize-1 ,j = 0; i >= 0 && j < arrSize; i--, j++){
            arr[j] = remainNum/(int)(Math.pow(10,i));    
            remainNum = inputIntArr%(int)(Math.pow(10,i));
        }

        /*
         * String 메서드를 이용한 나누기 (방법2) 
         */
        for (int i =0; i< arrSize; i++){
            arr[i] = Integer.parseInt(inputStringArray.substring(i, i+1));
        }

        //선택정렬
        for(int i =0; i<arrSize; i++){
            int maxIdx = i;
            for (int j = i+1; j<arrSize; j++){
                if(arr[maxIdx] < arr[j]){
                    maxIdx = j;
                }
            }
            
            if(i != maxIdx){
                int temp = arr[i];
                arr[i] = arr[maxIdx];
                arr[maxIdx] = temp;
            }
            
        }

        for ( int i : arr) {
            bw.write(i+"");
        }

        bw.flush();
        bw.close();
        
        
    }
}