[Algorithm/Java] 백준 2605번 - 줄 세우기 (이해중)
https://www.acmicpc.net/problem/2605
🔍 문제 풀이
풀이 방법
두 가지 방식으로 풀 수 있다.
- List 삽입 방식 (ArrayList 활용)
ArrayList.add(index, value)
를 이용해 앞으로 갈 칸 수만큼 밀어 넣음- 코드 간결, 쉬움
- 배열 수동 삽입
result[]
배열을 직접 한 칸씩 밀어가며 삽입- 좀 더 복잡하지만, 어려운 시뮬레이션 문제에 적용 가능
문제 도식화
아래는 배열 수동 삽입 방식의 과정을 그림으로 나타낸 것이다.
💻 전체 코드
List.add(index, value) 사용
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];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<=n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// 로직
List<Integer> list = new ArrayList<>();
for(int i=1; i<=n; i++){
int idx = list.size() - arr[i];
list.add(idx, i);
}
// 출력
for (int num : list) {
System.out.print(num + " ");
}
}
}
배열 수동 삽입
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];
int[] result = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 로직
for (int i = 0; i < n; i++) {
int move = arr[i]; // 앞으로 갈 칸 수
int insertIdx = i - move; // 삽입할 위치
// insertIdx부터 오른쪽으로 한 칸씩 밀기
for (int j = i; j > insertIdx; j--) {
result[j] = result[j - 1];
}
result[insertIdx] = i + 1;
}
// 출력
for (int num : result) {
System.out.print(num + " ");
}
}
}
댓글남기기