[백준 알고리즘] 10811번 바구니 뒤집기 - JAVA

 

이번 문제는 생각을 많이하게 된 문제라 따로 정리하려고 한다. 

 

 

 

https://www.acmicpc.net/problem/10811

10811번: 바구니 뒤집기

 

 

일단 문제의 답은 다음과 같다. 

 

package step4;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 *  바구니의 총 개수 N
 *  M번 바구니의 순서를 역순으로 만든다.
 *  순서를 역순으로 바꿀 때, 역순 범위를 정하고, 그 범위 안에 들어있는 바구니의 순서를 바꾼다.
 */
public class Q9_10811_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        for(int i = 0; i<N; i++){
            arr[i] = i + 1;
        }
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken()) -1;
            int to = Integer.parseInt(st.nextToken()) -1;

            for(int j =from; j<=to;j++,to--){
                int temp = arr[j];
                arr[j] = arr[to];
                arr[to] = temp;
            }

            /**
             * 1번부터 4번을 역순
             *  2 1 4 3 5
             *
             *  from&j 0, to 3,
             *  = 3 1 4 2 5
             *
             *  from&j 1, to 2
             *  = 3 4 1 2 5
             *
             *  from&j 2 to 1
             *
             *
             */
        }

        for(int i=0; i<arr.length;i++){
            sb.append(arr[i]).append(" ");
        }

        bw.write(sb.toString().trim());
        bw.close();
    }
}

 

 

 

📑 1번째 생각과 오답 

 

 

문제는 i와 j를 입력받고 (1<=i<=j<=N) i번째부터 j번째까지의 바구니 순서를 역순으로하라였다. 근데 나는 역순이 아닌 정렬, 즉 내림차순 정렬로 생각했다. 

 

문제는 2 1 4 3 5라는 숫자가 주어졌을 때 1번부터 4번째 있는 바구니의 순서를 역순으로 바꿔라. 

=> 3 4 1 2 5 가 나와야되는데 

 

나는 2 1 4 3 5라는 숫자가 주어졌을 때 1번부터 4번째 있는 바구니의 순서를 내림차순 정렬해라.

=> 4 3 2 1 5 가 나와야된다 생각했다.

 

그래서 Arrays.sort(배열, from index , to index, 정렬 방식)을 사용했다. 

 

★참고로 arrays.sort에서 index 사용시 from index부터 to inex -1 번째 수를 정렬한다. 즉 1번부터 4번을 index에 넣었을 시 1번부터 3번 3개만 정렬한다. 

 

 

package step4;

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

/**
 *  바구니의 총 개수 N
 *  M번 바구니의 순서를 역순으로 만든다.
 *  순서를 역순으로 바꿀 때, 역순 범위를 정하고, 그 범위 안에 들어있는 바구니의 순서를 바꾼다.
 */
public class Q9_10811 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        Integer[] arr = new Integer[N];
        for(int i=0; i<N;i++){
            arr[i] = i+1;
        } // 1 2 3 4 5
        for(int i=0; i<M; i++){
            st =  new StringTokenizer(br.readLine()," ");
            //Arrays.sort(arr,fromIndex,toIndex) -> fromIndex값부터 toIndex-1값까지!
            Arrays.sort(arr,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken()), Collections.reverseOrder());
        }

        sb.append(Arrays.toString(arr));
        bw.write(sb.toString());
        bw.close();

    }
}

 

 

이렇게 한 번 내 개념에 빠져버리면 헤어나오기 쉽지 않다. 맞는데 왜 틀리지?라는 생각에 빠져버린 원인 첫번째.

 

 

📑 2번째 생각과 오답 

 

for문이란? 어떤 명령문들을 반복하고자 할 대 사용하는 제어문 중 하나로 반복횟수가 정해진 경우 '주로' 사용한다. 반대로 반복횟수를 모를 경우 '주로' while문을 사용한다. 

 

for(초기식; 반복조건(=조건식); 증감식){
     반복문이 true일 때 실행할 명령문들;
} 

 

초기식은 for문이 실행될 때 최초 1회만 실행되는 코드이다. 반복 조건은 true 또는 false가 나오는 식으로 true일 경우 명령문을 실행, false일 겨웅 for문을 종료하게 된다. 

 

즉) 초기식 -> 반복조건 -> 참인 경우 for문 안으로 -> 증감식 -> 반복조건 -> 참인경우 for문 안으로 ... 이를 반복한다.

 

 

 

정렬이 아닌 역순이구나를 깨닫고 난 후 처음 생각 했던 식은 우측과 같다. for문의 초기식이 반복될 때매다 실행되는거라 헷갈려, from의 값을 증감시켰다. 그러니 from의 값은 증감하는데 j값이 증감하지 않아 반복문이 생각했던 것 보다 더 많이 실행되는 것이다. 우측처름 작성하지 말고 좌측처럼 작성해야 생각했던 대로 코드가 실행된다.

 

 

 

 

 

이런 사소한 허점 탓에 사간을 허비하니 처음부터 코드를 짤 때 제대로 잡고 가자.