アルゴリズム学習9週目[実施]01


白駿1138題


質問:キュー



ある人の身長は1からNまでです。このとき2行目は身長iの人を基準に、左に自分より背の高い人が何人いるかを入力します。そして順番に並べばいいです。(つまり、初めて与えられたのが身長順ではない場合、身長順に一人一人の左側に背の高い人の数で揃えるのはどうやって立っているのかという問題)


コード:

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

public class Main_1138 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arr[]= new int[N];
        for(int i=0;i<N;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(N));
        for(int i=N-2;i>=0;i--){
            list.add(arr[i],i+1);
        }
        for(int i=0;i<N;i++){
            System.out.print(list.get(i)+" ");
        }
    }
}

本題は背の高い人から固定して、中に小人を挟むといいです。一番大きい人を先に立って、それから0と1で、大きい人の右か左に立っています。このように大物から位置づけられる方法です。ここで重要なのは、この順序を配列に設定すると、配列を変更し続ける必要があるため、linklistを使用して問題を解決する必要があることです。


リンクリストの宣言と使用方法:

宣言:

LinkedList<Integer> integers1 = new LinkedList<Integer>(); // 타입 지정
LinkedList<Integer> integers2 = new LinkedList<>(); // 타입 생략 가능
LinkedList<Integer> integers3 = new LinkedList<>(integers1); // 다른 Collection값으로 초기화
LinkedList<Integer> integers4 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5)); // Arrays.asList()

追加:

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> colors = new LinkedList<>();
        // add() method
        colors.add("Black");
        colors.add("White");
        colors.add(0, "Green");
        colors.add("Red");

        // set() method
        colors.set(0, "Blue");

        System.out.println(colors);
    }
}

削除:

import java.util.Arrays;
import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> colors = new LinkedList<>(Arrays.asList("Black", "White", "Green", "Red"));
        String removedColor = colors.remove(0);
        System.out.println("Removed color is " + removedColor);

        colors.remove("White");
        System.out.println(colors);

        colors.clear();
        System.out.println(colors);
    }
}
関連項目:https://psychoria.tistory.com/767