문제
도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.
도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.
바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.
접근 과정 / 풀이 과정
단계 별 문제풀이에서 배열 카테고리에 속해 있는 문제이다.
카테고리 내에서 밑으로 내려갈 수록 문제가 어려워진다고 느껴졌는데, 본 문제는 밑에 있는 문제이지만 경우의 수를 생각할 필요가 없어 쉽게 느껴졌다.
도현이는 I번부터 J번까지의 바구니를 역순으로 만든다고 하였다.
그렇다면 반복문의 범위를 I부터 J까지 만들고 첫번째 뒤집기에선 I번 바구니와 J번 바구니를 뒤집고,
두번째 뒤집기에선 I+1바구니와 J-1 바구니를 뒤집으면 되지 않을까?
다행히도 잘 구현이 된 것 같다.
import java.io.*;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine() , " ");
//바구니 N개
int[] N = new int[Integer.parseInt(st.nextToken())];
// 1 부터 N까지 대입
for(int i = 0; i < N.length; i++)
N[i] = i+1;
int M = Integer.parseInt(st.nextToken());
//줄 M개
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine() , " ");
int I = Integer.parseInt(st.nextToken());
int J = Integer.parseInt(st.nextToken());
int num = 1;
//I번에서 J번까지
for(int j = I; j < J; j++) {
// I번이 J번보다 크지 않을 때만 대입
if(j-1 < J-num) {
int tmp = N[j-1];
N[j-1] = N[J-num];
N[J-num] = tmp;
num++;
}
}
num = 1;
}
for(int n : N)
System.out.print(n + " ");
}
}배운점
순위에 올라와 있는 코드와 비교하였다.
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));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder str = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N+1];
for(int i = 1; i <= N; i++)
arr[i] = i;
for (int n = 0; n < M; n++){
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
// 앞뒤로 바꿔줌
while(i < j){
int tmp = arr[i];
arr[i++] = arr[j];
arr[j--] = tmp;
}
}
for(int i = 1; i <= N; i++)
str.append(arr[i]).append(" ");
System.out.print(str);
br.close();
}
}비교 하였을 때 접근 방법은 유사한 것 같으나 좀 더 깔끔하다고 생각했다.
개선할 점은, 나는 for문 안에서 I가 J보다 크지않을 때까지라는 조건을 걸었는데,
이는 사실 위 순위 코드의 while( i < j )라는 짧은 코드로 대체가 된다.
그리고 사용하지 않아도 되는 변수를 만들었다. I는 ++하고 J는 --하면 된다.
