12주차 : 정렬 문제2

✔BOJ_18870

별로 어려운 문제는 아니었던 것 같은데.. 많이 헤맸습니도

첫 번째 제출은 정말 말 그대로 풀었습니다. 정렬 문제인데 ..^^

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

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());
        int[] arr= new int[n];
        int[] tmp  = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            tmp[i] = arr[i];
        }

        for(int i=0;i<n;i++){
            HashSet<Integer> s = new HashSet<>();
            for(int j=0;j<n;j++){
                if(i!=j && tmp[j] < tmp[i]) s.add(tmp[j]);
            }
            arr[i] = s.size();
        }

        for (int i : arr) {
            System.out.print(i+" ");
        }

    }
}

sublist를 이용하여 size()를 사용해 답을 내는 과정을 생각했습니다. 근데 이렇게 되면 sublist() 과정에서 많은 시간이 소요되어ㅠ 시간 초과가 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());
        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<Integer> s = new HashSet<>();
        for(int i=0;i<n;i++){
            arr.add(Integer.parseInt(st.nextToken()));
        }
        // Hash set에 넣고 set을 정렬하기
        for(int i=0;i<n;i++){
            s.add(arr.get(i));
        }
        // hashset 정렬
        ArrayList<Integer> lst = new ArrayList<>(s);
        Collections.sort(lst);

        for(int i=0;i<n;i++){
            int index = lst.indexOf(arr.get(i));
            ans.add(lst.subList(0, index).size());
        }
        for (Integer an : ans) {
            System.out.print(an+" ");
        }


    }
}

최종 답안이랑 비슷한 것 같긴한데 set에 값을 넣고 그것을 arraylist로 변경하여 정렬하고 다시 값을 얻어내는 과정에서 시간이 소요가 된것이 아닌가 ㅠ싶습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());
        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<Integer> s = new HashSet<>();
        for(int i=0;i<n;i++){
            arr.add(Integer.parseInt(st.nextToken()));
        }
        // Hash set에 넣고 set을 정렬하기
        for(int i=0;i<n;i++){
            s.add(arr.get(i));
        }
        // hashset 정렬
        ArrayList<Integer> lst = new ArrayList<>(s);
        Collections.sort(lst);

        Map<Integer, Integer> indexList = new HashMap<>();

        int rank = 0;
        for(int i=0;i<lst.size();i++){
            indexList.put(lst.get(i), rank);
            rank++;
        }

        for(int i=0;i<n;i++){
            ans.add(indexList.get(arr.get(i)));
        }
        for (Integer an : ans) {
            System.out.print(an+" ");
        }

    }
}

속이 터질 것 같아서 블로그 참조해서 풀었습니다ㅠ key 값 사용하는 것은 동일한데 생각해보니까 arraylist를 쓸 것이면 굳이 set을 사용하지 않아도되겠구나..는 것을 깨달을 수 있었습니다.

package BaekJoon.Sort;

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


// https://st-lab.tistory.com/279

public class BOJ_18870_adv {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] origin = new int[N];	// 원본 배열
        int[] sorted = new int[N];	// 정렬 할 배열
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	// rank를 매길 HashMap


        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            // 정렬할 배열과 원본 배열에 값을 넣어준다.
            sorted[i] = origin[i] = Integer.parseInt(st.nextToken());
        }

        // 정렬 할 배열에 대해 정렬을 수행해준다.
        Arrays.sort(sorted);


        // 정렬 된 배열을 순회하면서 map에 넣어준다.
        int rank = 0;
        for(int v : sorted) {
            /*
             *  이 때 만약 앞선 원소가 이미 순위가 매겨졌다면
             *  중복되면 안되므로, 원소가 중복되지 않을 때만
             *  map에 원소와 그에 대응되는 순위를 넣어준다.
             */
            if(!rankingMap.containsKey(v)) {
                rankingMap.put(v, rank);
                rank++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해준다.
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int key : origin) {
            int ranking = rankingMap.get(key);	// 원본 배열 원소(key)에 대한 value(순위)를 갖고온다.
            sb.append(ranking).append(' ');
        }

        System.out.println(sb);

    }
}