백준1138번 문제

문제 : 한 줄로 서기

---

---

문제 설명 : 키가 1부터 N까지인 사람들이 있다. 이때 두번째 줄에는 키가 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을 가질 수 있으니 큰사람의 오른쪽 or 왼쪽에 세운다. 이런식으로 큰사람부터 위치를 잡고 세우는 방식이다. 여기서 중요한 포인트는 이 순서를 배열로 하게 된다면 배열을 계속 바꿔야 하는 수고가 필요하므로 linked list 을 사용하는 방식으로 문제를 풀어야 한다.

linke list 선언 및 사용법 :

선언 :

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