[Algorithm/Java] 백준 1138번 - 한 줄로 서기

---

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

---

🔍 문제 풀이

문제 설명

“왼쪽에 있는 키 큰 사람 수”가 라는 정보가 주어질 때, 사람들이 최종적으로 서게 될 키 순번을 출력하는 문제

문제 도식화

💻 코드

[방법 1] 키가 큰 사람부터 배치 (ArrayList)

‘왼쪽에 있는 큰 사람 수’ 가 삽입할 위치의 인덱스가 되는 것을 이용해 ArrayList의 삽입 기능을 활용한다.

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));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        List<Integer> ans = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=n; i>=1; i--) {
            ans.add(arr[i], i);
        }
        for(int v : ans) {
            System.out.print(v +" ");
        }
    }
}

[방법 2] 키가 작은 사람부터 배치

‘왼쪽에 있는 큰 사람의 수’가 ‘왼쪽에 있는 빈칸의 수’와 같다는 점을 이용해 빈자리를 직접 찾아 사람을 채워 넣는다.

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));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] ans = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++){
            int cnt = 0;
            for(int j=0; j<n; j++){
                if(ans[j] == 0) {
                    if(cnt == arr[i]) {
                        ans[j] = i;
                        break;

                    }
                    cnt++;
                }

            }
        }

        for(int i=0; i<n; i++){
            System.out.print(ans[i] + " ");
        }
    }
}