[백준] JAVA / 바구니 뒤집기

BOJ/백준 10811 - 바구니 뒤집기

백준 10811 - 바구니 뒤집기

1. 문제 분석

문제 이해

1 ~ N번까지의 번호를 가진 바구니가 있다
M번의 바구니의 순서를 역순으로 만들 것이다

M번의 역순을 다 한 후, 바구니 번호를 왼쪽 부터 출력하는 문제 이다.

바구니의 개수 N = 5
역순의 개수 M = 4

1 2 3 4 5의 바구니가 있을 때

• (1, 2) 수행하면 -> 2 1 3 4 5
• (3, 4) 수행하면 -> 2 1 4 3 5
• (1, 4) 수행하면 -> 3 4 1 2 5
• (2, 2) 수행하면 -> 3 4 1 2 5 이런식으로 풀어가는 것이다

풀이 방법

• 바구니 번호 배열 저장

for(int i = 0; i < N; i++) {
	arr[i] = i + 1;
}

• 투 포인터 알고리즘 사용으로 역순으로 표현

while(front < end) {
	int temp = arr[end];
	arr[end] = arr[front];
	arr[front] = temp;
				
	front++;
	end--;
}

💡 투 포인터는 양쪽 끝에서 시작해서 서로 마주 보는 방향으로 좁혀 오는 알고리즘

front는 오른쪽으로 이동 end는 왼쪽으로 이동하면서 역순으로 표현하는 것

2. 코드 구현

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

public class No_10811 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[N];
		
		//1. 배열 저장
		for(int i = 0; i < N; i++) {
			arr[i] = i + 1;
		}
		
		//2. 역순 부분 입력
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int front = Integer.parseInt(st.nextToken()) - 1;
			int end = Integer.parseInt(st.nextToken()) - 1;
			
			
			//3. 역순으로 표현 - 투 포인터 사용
			while(front < end) {
				int temp = arr[end];
				arr[end] = arr[front];
				arr[front] = temp;
				
				front++;
				end--;
			}
		}
		
		//4. 마지막으로 저장된 배열 출력
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}