[백준 JAVA] 1138 : 한 줄로 서기

[백준 1138] 한 줄로 서기 : https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

 

---

문제 조건 정리

 

1. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다.
2. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.
3. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

 

---

입력

 

1. 첫째 줄에 사람의 수 N(10보다 작거나 같은 자연수)이 주어진다.
2. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다.
   i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

 

---

문제를 풀기 전

 

1. 각 자리에 들어갈 수 있는 수들을 구한 후에 소거하는 방식을 생각함!
2. 키가 큰 사람부터 배치하며 이후의 사람을 배치하는 방식도 생각함!

 

결과적으로 모두 효율적이지 못했음!

 

---

코드

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        
        // 결과값 배열 (1 ~ n)
        int[] res = new int[n + 1]; 

        for (int i = 1; i <= n; i++) {
            // 1. 키가 제일 작은 사람(i = 1)부터 배치
            // 2. 나(i) 앞에 몇 사람이 배치되어야 할까?
            // ex) 나보다 큰 사람이 2명 -> 나의 왼쪽에 2명이 있어야 함
            // 나의 왼쪽에 2명 -> 앞에 빈자리가 2개 있어야 함 -> 자신은 3번째에 배치됨
            int pos = Integer.parseInt(stringTokenizer.nextToken()) + 1;

            // 자신 왼쪽의 빈 칸(값이 할당 되지 않은 상태)을 카운트
            int count = 0; 
            
            for (int j = 1; j <= n; j++) {
                
                // 해당 자리가 0(값이 할당 되지 않은 상태)이라면
                if (res[j] == 0) {
                    count++;
                    
                    // 카운트 값이 (자신 앞의 빈 칸 + 1)과 같다면
                    if (count == pos) { 
                    	// 해당 자리는 나(i)의 자리
                        res[j] = i; 
                        // 다음 사람으로 넘어가기
                        break; 
                    }
                }
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        // 1번째부터 n번째 자리까지 순서대로 출력
        for (int i = 1; i <= n; i++) {
            stringBuilder.append(res[i]).append(" ");
        }
        System.out.println(stringBuilder);

    }
}

 

---

문제를 풀고 난 후

 

풀고 나니 너무 간단해서 고민했던게 너무 부끄러움!

 

구현 문제는 역시 재밌는 것 같음!