[정렬] 장난꾸리기

 

 

 

설명

 

 

 

 

 

 

풀이

 

자료구조는 int형 배열을 사용한다.

 

로직은 다음과 같다.

• 정답으로 리턴할 데이터는 ArrayList<Integer> 형으로 생성한다.
• 원본 배열을 깊은 복사한다. clone 메소드를 이용한다. 이 배열을 복사된 배열이라고 하자.
• 복사된 배열을 오름차순 정렬한다. Arrays 클래스의 sort 메소드를 이용한다.
• 반복문을 돌면서 원본 배열과 복사된 배열의 값을 비교한다.
  • 값이 다르다면 정답에 add 한다. 이 때 인덱스 값에 +1을 해야 배정받은 번호가 된다. (번호는 1부터 시작이고 인덱스는 0부터 시작이므로)
• 정답 배열을 리턴한다.

 

 

 

 

코드

 

package inflearn._6_6;

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

public class Main {

    public static ArrayList<Integer> solution(int n, int [] arr) {

        ArrayList<Integer> answer = new ArrayList<>();

        int [] tmp = arr.clone(); // 배열 깊은 복사

        Arrays.sort(tmp);

        // 반복문 돌면서 다른 인덱스 찾기
        for(int i = 0; i < n; i++) {
            if (arr[i] != tmp[i])
                answer.add(i+1); // i에 +1을 해줘야 배정받은 번호가 됨
        }

        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

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

        int [] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i< n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer> answer = solution(n, arr);

        for(int x : answer) {
            sb.append(x).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();
    }
}