[PS] BOJ 10811 바구니 뒤집기

문제

문제링크

소스 코드

문제의 핵심은 배열의 구간을 반대로 뒤집는 부분을 구현하는 것이다. 예를들어 1 ~ 4 구간을 뒤집으면 아래와 같다.

  4 index -> 1 index
  3 index -> 2 index
  2 index -> 3 index
  1 index -> 4 index

홀수 개의 배열인 경우

  5 index -> 1 index
  4 index -> 2 index
  3 index -> 3 index
  2 index -> 4 index
  1 index -> 5 index

처음에 저렇게 숫자로만 쓰면서 패턴을 찾으려고 했는데 규칙이 잘 안보여서 그림을 그려봤다.

배열 뒤집기

원본 배열에서 뒤집고 싶은 부분만 임시 배열에 저장해 둔 다음 다시 원본 배열에 덮어쓰는 형식으로 풀었다. 그림으로 보면 결국 맨뒤와 맨 앞의 위치를 계속해서 바꿔주는 것을 알 수 있다. 문제에서 i 가 맨 첫번째 인덱스이고, j가 맨마지막 인덱스임을 알 수 있다. 결국 arr[i] = arr[j] 와 같은 코드가 필요하다. 이제 반복 횟수만 작성해 주면 된다.

  for (int c = 0; c <= T; c++, j--, i++) {
    tmpArr[i] = arr[j];
  }

이때 반복 횟수는 1 4가 입력되는 경우 4가 된다. 즉 반복 횟수는 입력에서 알 수 있고, 배열의 인덱스만 조절해 주면 된다. 그림처럼 i 에서 시작하는 인덱스는 1씩 증가하고 j 에서 시작하는 인덱스는 1씩 감소하는 것을 알 수 있다.

public class Boj_10811 {

      static FastReader scan = new FastReader();
      static StringBuilder sb = new StringBuilder();

      public static void main(String[] args) {
          input();
      }
      static void input(){
        int n = scan.nextInt();
        int m = scan.nextInt();

        int[] arr = new int[n + 1];

        for (int k = 1; k <= n; k++) {
          arr[k] = k;
        }

        for (int z = 0; z < m; z++) {
          int i = scan.nextInt();
          int j = scan.nextInt();
          int T = j-i;
          int[] tmpArr = new int[arr.length];

          for (int c = 0; c <= T; c++, j--, i++) {
            tmpArr[i] = arr[j];
          }

          for (int k = 0; k < tmpArr.length; k++) {
            if (tmpArr[k] != 0) {
              arr[k] = tmpArr[k];
            }
          }

        }

        System.out.println(Arrays.toString(arr).replace("[","").replace("]","").replace(",","").substring(2));
      }

      static class FastReader {
          BufferedReader br;
          StringTokenizer st;
          public FastReader() {
              br = new BufferedReader(new InputStreamReader(System.in));
          }
          public FastReader(String s) throws FileNotFoundException {
              br = new BufferedReader(new FileReader(new File(s)));
          }
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
          int nextInt() {
              return Integer.parseInt(next());
          }
          long nextLong() {
              return Long.parseLong(next());
          }
          double nextDouble() {
              return Double.parseDouble(next());
          }
          String nextLine() {
              String str = "";
              try {
                  str = br.readLine();
              } catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }
      }
}