第12週目:並べ替え問題2

43011 ワード
アルゴリズム#アルゴリズム# テキストリンク
✔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()を用いて答えを与える過程を考察した.しかしこのようなリスト()の過程で多くの時間がかかり、タイムアウトします.
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+" ");
        }

    }
}
心が爆発しそうで、ブログ参照で解けたㅠ用キー値は同じですが、考えてみれば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);

    }
}
面接のこと
LinkedHashMap/Set?