문제
도현이는 바구니를 총 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)
도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.
출력
모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.
예제
예제 입력
5 4
1 2
3 4
1 4
2 2
예제 출력
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();
}
}
}
}
[문제 출처] https://www.acmicpc.net/problem/10811
'프로그래밍 언어 활용 > JAVA' 카테고리의 다른 글
IO입출력: 파일에 객체 정보 저장하기, 파일로부터 객체 정보 가져오기 (0) | 2024.02.14 |
---|---|
네트워크 : TCP 통신 구현하기 (0) | 2024.02.13 |
컬렉션 프레임워크 : 각론 (0) | 2024.02.05 |
다형성 실습 문제 (3) | 2024.01.25 |
05. 클래스와 객체 1 (0) | 2024.01.18 |