[코드트리/NOVICE MID] 정렬된 숫자 위치 알아내기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Number implements Comparable<Number> {
    int num, pos;
 
    public Number(int num, int pos) {
        this.num = num;
        this.pos = pos;
    }
 
    @Override
    public int compareTo(Number n) {
        if(this.num == n.num)    // 동일한 원소의 경우, 먼저 입력으로 주어진 원소를 앞으로
            return this.pos - n.pos;
        return this.num - n.num;    // 숫자 기준 오름차순 정렬
    }
}
 
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().trim());
        Number[] numbers = new Number[N];
        int[] nums = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            int n = Integer.parseInt(st.nextToken());
 
            nums[i] = n;
            numbers[i] = new Number(n, i + 1);
        }
 
        Arrays.sort(numbers);    // Custom Comparator
 
        boolean[] visited = new boolean[N];    // 값이 같은 숫자가 여러 개인 경우, 앞에서부터 나오게 하고, 중복 방지 위한 배열
 
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < numbers.length ; j++) {
                if(!visited[j] && nums[i] == numbers[j].num) {
                    System.out.print(j + 1 + " ");
                    visited[j] = true;
                    break;
                }
            }
        }
    }
}

 

🧩  해결 아이디어

• 사용자 정의 정렬

- 동일한 원소의 경우, 인덱스 기준 오름차순 정렬

- 다른 원소의 경우, 원소 값 기준 오름차순 정렬

 

- boolean 배열을 활용한다.

값이 같은 숫자가 여러 번 나오는 경우,

앞에서 부터 나오게 하고, 중복 인덱스를 나오지 않도록 한다. (Line 38-48)

 

 

---

🔺 다른 풀이

1) (숫자, 원래 위치)를 인덱스에 저장한다.

2) 1에서 저장한 값을 오름차순으로 정렬한다. <- Custom Comparator

3) 각 위치에 있던 원소가 어디로 이동한 것인지 저장 위해 별도 배열 만들어 활용

// 정렬된 숫자들의 원래 인덱스를 활용한 정답 배열 저장
for(int i = 0 ; i < N ; i++) {
	answer[numbers[i].idx] = i;
}

ㄴ 이렇게 풀면 약 50ms 정도 줄일 수 있다.

 

---

💬 느낀 점

조곰 난이도가 있었다....

이 문제 복습을 잘 해야지.

풀긴 풀었는데 시간이 조곰 오래 걸려서 푸는 시간도 줄여야지..

 

암튼 이렇게 객체 정렬 / 사용자 정의 정렬 파트 끝!!

 

1회독	2회독	3회독	4회독	5회독
V