백준 15903 카드 합체 놀이 - JAVA

15903 문제 링크

---

https://www.acmicpc.net/problem/15903

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        } 
        List<Integer> answer = new ArrayList<>();
        
        for (int i = N; i >= 1; i--) {
            answer.add(arr[i-1], i);
        } 
        for (int num : answer) sb.append(num).append(" ");
        bw.write(sb.toString());
        bw.flush();
    }
}

 

알고리즘 설명

---

오랜만에 풀으려니 머리가 다 굳어버렸네요... 역시 정리를 해야 오래남는것 같습니다.

해당 문제는 키가 큰 사람부터 순차적으로 리스트에 삽입하면, 이미 배치된 큰 사람들이 ‘왼쪽에 큰 사람이 몇 명 있는지’ 조건에 영향을 주지 않기 때문에 조건을 자연스럽게 만족시킬 수 있습니다. 또한 ArrayList.add(index, value)를 사용하면 원하는 삽입 위치를 지정할 수 있어, 조건을 만족하는 최종 배열을 효율적으로 구성할 수 있습니다.

 

코드 해석

---

입력받은 N명을 배열에 저장합니다. 이후 생성한 리스트에 키가 큰 순서(N -> 1)대로 주어진 배열의 값을 인덱스로 설정하여 N부터 순차적으로 인덱스에 맞게 리스트에 삽입합니다. 이후 해당 리스트를 반복문으로 변수에 담아 출력합니다.