[백준] 10811. 바구니 뒤집기(Java)

프로그래밍 언어 활용/JAVA

[백준] 10811. 바구니 뒤집기(Java)

프린이8549 2024. 3. 15. 19:03

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

예제

예제 입력

예제 출력

3 4 1 2 5

문제 풀이

숫자의 순서만 바꾸면 되는 문제였으나, 자꾸 버블정렬의 알고리즘을 사용하려고 애쓴 탓에 스스로 문제를 더 복잡하게 만들어버려 결국 포기하고 다른 사람들의 아이디어를 참고하여 문제를 해결했다.

본 문제의 본질은 배열 내의 값들의 순서를 변경하는 것이다. 단순히 순서만 바꾸면 되는 것이다.

본 문제를 접근할 때 중요한 아이디어는

1. 배열 내 값들의 순서를 바꾸는 경우 임시 변수를 설정할 것

2. 순서를 바꾸려는 두 값 a, b의 인덱스값은 무조건 b의 인덱스 값이 커야한다는 것.

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

class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer strTk;
		try {
			// strs 배열에 첫줄에 입력받은 숫자들을 띄어쓰기를 기준으로 하나씩 add
			strTk = new StringTokenizer(br.readLine(), " ");
			// 첫 번째 숫자는 N 두 번째 숫자는 M
			int N = Integer.parseInt(strTk.nextToken());
			int M = Integer.parseInt(strTk.nextToken());
			// 각 바구니의 번호는 순차적으로 부여됐기에 바구니 번호의 집합을 int형 배열로 가정
			// 앞서 입력받은 숫자 N은 곧 바구니의 갯수를 의미하기에 이를 배열의 크기로 대입
			int busket[] = new int[N];
			// 생성한 배열에 순차적으로 번호 부여함으로써 바구니 번호 생성
			for(int i = 0; i < busket.length ; i++) {
				busket[i] = i + 1;
			}
			// 두 번째 줄부터 입력받을 숫자들을 넣기 위한 int형 변수 선언
			int a = 0;
			int b = 0;
			//M개의 줄을 입력받기 위한 반복문
			for(int i = 0 ; i < M ; i++) {
				// 한 줄씩 2개의 숫자들을 입력받아 배열에 추가
				strTk = new StringTokenizer(br.readLine(), " ");
				// 미리 선언한 변수들에 대입(단, 인덱스는 0부터 시작하기에 1을 빼서 대입)
				a = Integer.parseInt(strTk.nextToken()) - 1;
				b = Integer.parseInt(strTk.nextToken()) - 1;
				// 역순을 만들기 위해 숫자 한 개를 임시로 대입할 변수 선언
				int tmp = 0;
				// 역순은
				// 1. a번째 값 - b번째 값 자리 변경
				// 2. (a+1)번째 값 - (b-1)번째 값 자리 변경
				// 3. 단 a >= b 가 되면 안됨
				while(a < b) {
					// b번째 값을 미리 tmp 변수에 대입
					tmp = busket[b];
					// b번째 값에 a번째 값 대입
					busket[b] = busket[a];
					// a번째 값에는 tmp의 값 대입
					busket[a] = tmp;
					// 자리를 변경한 후에는 다음 (a+n)번째 - (b-n)번째 값의 자리를 바꿔야 함
					a++;
					b--;
				}
			}
			for(int i : busket) {
				bw.write(i + " ");
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				bw.flush();
				bw.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

}