Java 1138 한 줄로 서기

 

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

1138번: 한 줄로 서기

풀이 :

1. 우선 왼쪽에 서있는 사람들의 수를 저장할 배열을 생성해주고 입력 값으로 받아준다.

2. 비교하기 위해 Integer.MAX_VALUE값이 저장된 배열을 하나 더 생성해준다.

3. 첫번째 사람부터 for문을 돌며 최대값이 저장되어 있는 order 배열의 값과 현재 인덱스인 i를 비교하며 값이 크다면 tmp 변수에 1을 더해주고 index의 값은 크든 적든 1을 더해주며 순환해준다.

4. tmp변수의 값과 초기에 설정해둔 왼쪽에 있는 큰 사람에 대한 값이 같을 경우 다시 한번 while문을 진행하며 order[index]의 값이 i보다 클 경우에는 값을 업데이트 해주고 아니면 index에 1을 더하여 index를 업데이트 해준다. order[index]의 값이 i보다 작을 경우엔 이미 값이 업데이트 된 경우이기 때문에 값은 변경되면 안된다.

 

 

위의 로직대로 구현하였습니다.

 

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n+1];
        int[] order = new int[n+1]; // 값을 비교할 최대 값이 들어갈 배열

        for(int i = 1; i <= n; i++){
            arr[i] = Integer.parseInt(st.nextToken()); // 왼쪽에 있는 사람 수 입력 받기
            order[i] = Integer.MAX_VALUE; // 최대값 저장
        }
        
        for(int i = 1; i <= n; i++){
            int cnt = arr[i]; // 왼쪽에 있는 사람 수
            int tmp = 0; // 큰 사람에 대한 카운트
            int index = 1; // 인덱스

            while(true){
                // cnt와 tmp가 같아진 경우는 왼쪽에 큰 사람을 카운트 해준 경우
                if(cnt == tmp){
                    while(true){
                        //값이 클 경우에는 아직 해당 위치에는 업데이트가 이루어지지 않았으므로 업데이트
                        if(order[index] > i){
                            order[index] = i;
                            break;
                        }
                        //아닐 경우는 이미 값이 업데이트 된 경우기 때문에 index증가
                        index++;
                    }
                    break;
                }
                // 크다면 카운트 해준다
                if(order[index] > i){
                    tmp++;
                }
                index++;
            }
        }

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

    }
}