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

풀이 방법

  1. 첫 번째 풀이
    이 문제는 어제 풀었던 도현이의 바구니 시리즈편인 것 같습니다. 그래서 이 문제도 간단하게 배열로 구현했습니다… 하지만, 정답이 틀렸다는 결과가,ㅜㅜ 그래서 무엇이 틀린지 코드를 분석해보는데 틀린 부분이 없었습니다.

제가 푼 방식은 우선, 바구니를 뒤집을 범위를 입력 받고 난 다음에 i부터 (i+j)/2 까지 반복문을 돌면서 조건을 검사합니다. int형 변수인 temp를 만듭니다. i번째 바구니와 j번째 바구니를 바꾸고, (i+1)번째 바구니와 (j-1)번째 바구니를 바꿉니다… 이 과정을 반복합니다.

저는 이 로직으로 구현했습니다만 테스트 케이스는 맞았지만, 정답이 틀렸다는 결과를 얻었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package language;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ10811 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        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 k=0;k<M;k++){
            st = new StringTokenizer(bf.readLine()," ");
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            
            for(int m=i;m<=(i+j)/2;m++){
                 int temp = arr[m];
                 arr[m] = arr[j];
                 arr[j] = temp;
                 j--;
            }
        }

        for(int i=1;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }

}
  1. Stack을 이용한 풀이
    내 생각에는 정확히 풀었다고 생각을 했는데, 결과는 틀렸다고 했습니다… 그래서 다른 사람들은 도대체 어떻게 풀었으며 제가 예전에 어떻게 풀었는지 확인해보았습니다. 먼저, 예전에 저는 자바가 아닌 C++을 이용해서 풀었습니다. 도움이 되지 않으니 패스, 그리고 다른 사람들은 Stack을 이용해서 문제를 풀었습니다. 사람들은 왜 Stack을 사용해서 풀었는지 의문이 생겼고 직접 Stack을 이용해서 문제를 풀어보았습니다.

Stack은 후입선출(LIFO)의 구조를 가지는 자료구조입니다. 문제에서 원하는대로 바구니를 뒤집을 범위를 입력받으면 Stack에 push하고 다시 pop을 해서 원래 배열에 담으면 뒤집어진 상태로 출력이 되기 때문에 원하는 결과를 얻을 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ10811 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        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 k = 0; k < M; k++) {
            Stack<Integer> stack = new Stack<>();
            st = new StringTokenizer(bf.readLine(), " ");
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            for (int m = i; m <= j; m++)
                stack.push(arr[m]);

            for (int m = i; m <= j; m++)
                arr[m] = stack.pop();
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++)
            sb.append(arr[i] + " ");

        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        bf.close();
    }

}

배운점

가끔 다른 사람의 코드를 참고하여 문제를 이해하거나 풀이를 확인해서 로직을 이해하는데 이로 인해 배움을 얻고 이해를 하는 것이 좋은 과정이라고 생각합니다. 굿굿~