[백준] 1138. 한 줄로 서기 (자바 JAVA)

[ 문제 ]  [백준] 1138. 한 줄로 서기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

---

# 접근 방법 및 풀이 

 

• 구현 문제다. 아이디어를 떠올렸다면 쉽게 풀었을 수도 있지만, 약간 생각하는데 시간이 걸렸다.
• 먼저, 문제에서 입력으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇명 있는지 주어진다.
• 예제대로 N = 4일 때, 2 1 1 0 으로 입력을 받아 arr[] 배열에 담아준다. 편의상 키가 1인 사람부터 시작하므로 다음과 같이 표현할 수 있다.

• 1번	2번	3번	4번
  2	1	1	0

• 정답을 담을 배열 ans[ ] 를 N크기 만큼 선언해주고, ans[0]번부터 N-1번까지 답을 채워보자.

• 0	1	2	3

• 여기서 ans배열의 인덱스는 "인덱스만큼 왼쪽에 있을 수 있는 사람 수"다. ans[0]이면 왼쪽에 0명, ans[1]이면 왼쪽에 1명, ans[2]면 왼쪽에 2명이 있을 수 있다.
• 키가 큰 순서부터 내림차순으로 arr[] 배열을 4번부터 1번사람까지 탐색하며 ans배열 값을 채워준다.
• arr배열의 인덱스는 i로, ans배열의 인덱스는 j로 선언했다. 
• j = 0 일때, 4번사람은 왼쪽에 0명이 있으므로 ans[0]에 4를 넣어준다. 그러나 4는 숫자가 제일 크기 때문에 ans배열의 0~3번 어디에 서도 자신보다 큰 수는 없기때문에 어디에 위치해도 상관없다.

• 0	1	2	3
  4

• j = 1일때, 3번사람은 왼쪽에 1명이 있을 수 있고, ans의 인덱스가 1이므로 ans[1] = 3이 된다.

• 0	1	2	3
  4	3

• j = 2일 때, 2번 사람은 왼쪽에 1명이 있다. ans[2]에 2번 사람을 놓으면, 왼쪽에 4, 3이 있기 때문에 틀린다. 따라서 ans[1]에 2번 사람을 놓고 ans[1]에 있던 3번사람은 뒤로 한칸 밀린다. 

• 0	1	2	3
  4	2	3

• j = 3일 때, 1번 사람은 왼쪽에 2명이 있다. ans[3]에 1번 사람을 놓으면, 왼쪽에 4,2,3으로 세명이 있기 때문에 틀린다. 따라서 ans[2]에 1이 오고 ans[2]에 있던 3은 뒤로 한칸 밀린다.

• 0	1	2	3
  4	2	1	3

• 따라서 다음과 같이 답을 완성시킬 수 있다.
• 예시로 N = 5,  2 1 0 1 0 으로 문제를 풀어보면 로직을 찾을 수 있다. 이때 정답은 3 2 1 5 4 이다.
• 자세한건 코드참조

# 주의할 점 

 

• 예제가 한개 뿐이므로 테케 만들어서 풀어보기

 

JAVA 코드

package Silver;

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

public class bj1138_한줄로서기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		String arr[] = in.readLine().split(" ");
		int ans[] = new int[arr.length];
		for (int i = arr.length-1, j = 0; i >= 0; i--, j++) {
			int cnt = Integer.parseInt(arr[i]);
			if(cnt == j) {
				ans[j] = i+1;
			}else {
				for (int k = j; k > cnt; k--) {
					ans[k] = ans[k-1];
				}
				ans[cnt] = i+1;
			}
		}
		for (int i = 0; i < ans.length; i++) {
			System.out.print(ans[i] + " ");
		}
	}
}

 

 

 

REVIEW