반응형
https://www.acmicpc.net/problem/10811
<풀이>
- 각 바구니를 놓을 공간인 배열을 N 개의 개수만큼 생성한다.
- 가장 왼쪽이 첫번째 바구니, ... 가장 마지막이 N 번째 바구니이기 때문에, 각 배열의 공간에 해당하는 순번의 바구니를 배치한다.
- M 개의 줄만큼 반복하여 바구니를 섞는다.
- 역순을 고려하여 코드를 구현한다.
1 2 3 4 바구니 4개가 있을 경우에 1 4부터 변경을 해야한다고 생각하면 i = 1, j = 4이다.
아래와 같이 되어야 한다.
a[1] = a[4]
a[2] = a[3]
a[3] = a[2]
a[4] = a[1]
i 번째 바구니와 j 번째 바구니가 역순이 되어야 하기 때문에 두 바구니가 교환된다고 보면 된다. 이해가 안가면 위에 작성해놓은 순서를 보면 된다. 즉, 임시 변수에 a[i] 값을 보관해주고, a[i] 에는 a[j] 값을 넣는다. 보관해놓은 a[i] 값을 a[j] 에 넣는다.
* 실제 배열은 인덱스 값이 0부터 시작하므로 이도 고려해야 한다.
그리고 i 값은 증가하고, j 값은 감소한다는 특징을 볼 수 있다.
* 예시는 원활한 이해를 위해 인덱스 시작을 고려하지 않음
1. 1회차 :
tmp = a[1] // tmp = a[i]
a[1] = a[4]. // a[i] = a[j]
a[4] = a[1]. // a[j] = tmp
2. 2회차 :
tmp = a[2]
a[2] = a[3]
a[3] = a[2]
조건에 1 <= i <= j <= N 이 있을 뿐더러, i > j 가 된 경우까지 반복하면 두번 섞은게 된다.
다른 방법이 있을지도 모르겠지만, 난 위와 같은 논리로 풀었다.
package Study.src.bronze;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B10811 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String first = br.readLine();
st = new StringTokenizer(first);
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
if ( 1 > N || N > 100 || 1 > M || M > 100) return;
int[] a = new int[N]; // 1. 바구니만큼의 배열 공간 생성
// 2. 바구니 초기화
for (int i = 0; i < N ; i++) {
a[i] = i + 1;
}
// 3. 바구니 섞기
for (int k = 0; k < M; k++){
String b = br.readLine();
st = new StringTokenizer(b);
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
int tmp;
if (1 > i || i > j || j > N) return;
// i ~ j 까지 돌기
for (int q = i ; q <= j; q++){
if ( i > j) return;
tmp = a[i - 1];
a[i - 1] = a[j - 1];
a[j - 1] = tmp;
j --;
i ++;
}
}
for (int i=0; i < a.length; i++){
System.out.print(a[i] + " ");
}
}
}
반응형
