백준 1138번 : 한 줄로 서기 java

이 문제는 키가 1 2 3 4인 사람이 순서대로 있을 때 자신의 왼쪽에 몇 명이 있었는지를 입력받아 자신의 자리를 찾아가는 문제입니다.

이를 그림으로 설명드리겠습니다.

위의 그림은 예제 1번의 상황을 나타낸 것입니다.

이제 문제를 해결하는 과정을 보여드리겠습니다.

우선 키가 1인 사람은 왼쪽에 자신보다 키가 큰 사람의 수가 2이니 2번 자리로 들어갑니다.

키가 2인 사람은 왼쪽에 자신보다 키가 큰 사람이 1명이니 1번 자리로 들어갑니다.

다음은 키가 3인 사람의 순서입니다.

키가 3인 사람은 왼쪽에 자신보다 키가 큰 사람의 수가 1이므로 우선 1번 자리로 갑니다.

하지만 1번 자리는 이미 자른 사람이 자리를 하고 있기 때문에 그 뒷자리를 봅니다.

우선 2번 자리가 비어있나 확인하지만 2번 자리도 이미 차있기 때문에 3번 자리로 이동합니다.

마지막 키가 4인 사람의 차례입니다.

키가 4인 사람은 자신보다 키가 큰 사람이 없기 때문에 아무 자리에 가도 상관이 없으니 남은 자리에 들어가 줍니다.

저는 이러한 규칙을 통해 이 문제를 해결하였습니다.

그 소스 코드를 보여드리겠습니다.

---

import java.util.*;
import java.io.*;

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[] intArr  = new int[N+1];
        int[] answer = new int[N+1];

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

        //i는 intArr[i]번 인덱스를 의미, j는 intArr[i]가 들어갈 자리
        for(int i = 1; i<=N; i++){
            int j = 1;

            while(true) {
                if (intArr[i] == 0 && answer[j] == 0) {
                    answer[j] = i;
                    break;
                }
                else if(answer[j] == 0)
                    intArr[i]--;

                //answer[j] == 0에도 j++해주는 이유는
                //intArr[i] != 0 && answer[j] == 0일 때 j번 자리는 비어있지만
                //intArr[i]가 0이 아니면 그 왼쪽에 자신보다 큰 수가 와야하기 때문에
                //한 칸 옆으로 이동해준다.
                j++;
            }
        }

        for(int i = 1; i<=N; i++)
            System.out.print(answer[i] +" ");
    }
}

 

이 코드에서 중요한 부분은 아래의 코드입니다.

for(int i = 1; i<=N; i++){
    int j = 1;

    while(true) {
        if (intArr[i] == 0 && answer[j] == 0) {
            answer[j] = i;
            break;
        }
        else if(answer[j] == 0)
            intArr[i]--;
        
        j++;
    }
}

저는 이 코드를 짤 때 j는 항상 1에서부터 시작하도록 하였습니다.

처음 자리에서 시작해서 자신이 위치할 자리를 찾아가는 것입니다.

if(intArr[i] == 0 && answer[j] == 0)

위와 같은 조건일 때는 그 사람이 들어갈 자리를 찾았기 때문에 answer[j] 자리에 i를 대입하고 break하면 됩니다.

하지만 아래와 같은 조건일 때를 조금 신경 써주셔야 합니다.

else if(answer[j] == 0)

위 코드는 아래의 코드와 같습니다.

if(answer[j] == 0 && intArr[i] != 0)

이것은 answer에서는 자신이 들어갈 장소가 비어있지만 왼쪽에 자신보다 더 큰 수가 와야 한다는 것입니다.

예를 들어서 아래와 같은 상황이 있습니다.

위의 그림에서 j는 초깃값인 1이고 이 자리는 비어있지만 intArr[i]는 2입니다.

따라서 위의 조건식을 적용하게 됩니다.

이 상황도 아까의 상황과 같으므로 한번 더 if문을 실행시킵니다.

이제 intArr[i]가 0이 되었으므로 answer[j]에 그 수를 대입합니다.

이를 반복하면 문제를 해결할 수 있습니다.