lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이번 바구니 뒤집기 문제는 배열의 일정 인덱스의 범위만큼을 담아둘 임시 배열을 활용하여 풀 수 있었다.

아이디어 도출

N만큼의 길이를 가지는 원본 배열에서 주어지는 i와 j만큼의 범위만큼을 잘라서 역순으로 담은 임시배열을 원본 배열에 덮어씌우는 방식을 적용하였다.

  • N과 M을 입력받고 N만큼의 길이를 가지는 배열을 생성한 뒤 1부터 N까지의 값으로 초기화한다.
  • M만큼 반복하면서 i와 j를 입력받고, i와 j의 인덱스의 범위를 가지는 임시배열을 초기화 한다.
    • 여기서 임시배열의 크기는 j-i+1만큼을 가져야 한다.
  • 원본 배열을 역순으로 임시배열에 담기 위해 j부터 i까지 역순으로 순회하면서 j-i의 인덱스 범위만큼 역순으로 임시배열에 담는다.
  • 특정 범위만큼 역순으로 담긴 임시배열이 만들어졌다면 원본배열에 해당되는 범위에 임시배열의 값을 덮어씌운다.


아이디어를 말로 설명하자니 조금 복잡할 수 있다.
바로 코드를 작성해보자.

1
2
3
4
5
6
7

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];

for(int i=1; i<=N; i++) {
    arr[i-1] = i;
}

N과 M을 공백 기준으로 입력받은 후, N의 크기를 가지는 arr 배열을 선언하고 1부터 N까지의 값으로 초기화한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for(int idx=0; idx<M; idx++) {
    st = new StringTokenizer(br.readLine());
    int i = Integer.parseInt(st.nextToken()) - 1;
    int j = Integer.parseInt(st.nextToken()) - 1;

    int[] tmp = new int[j-i+1];
    int ridx = 0;
    for(int r=j; r>=i; r--) {
        tmp[ridx] = arr[r];
        ridx++;
    }
    ridx = i;
    for(int r : tmp) {
        arr[ridx] = r;
        ridx++;
    }
}

M만큼 반복하면서 앞서 말했던 임시배열을 원본배열에 덮어씌우는 로직을 수행한다.

  1. i부터 j까지의 범위를 역순으로 담을 임시배열 tmp를 생성한다. 이 떄, tmp는 j-i+1의 크기를 가져야 해당 범위만큼 역순으로 담을 수 있게 된다.
  2. 원본배열의 역순으로 접근한 특정 범위의 값들을 tmp 배열에 순차적으로 담기 위해 ridx라는 인덱스를 별도로 선언한다.
  3. 임시 배열에 원본배열의 특정 범위를 역순으로 삽입한다.
  4. 원본배열에 특정 범위에 임시배열을 덮어씌우기 위해 ridx를 i번째 인덱스 값으로 설정한다.
  5. 임시배열을 순회하면서 원본배열에 임시배열 값을 삽입하여 덮어씌운다.



작성코드

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
45
46
47
48
49

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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=1; i<=N; i++) {
            arr[i-1] = i;
        }

        for(int idx=0; idx<M; idx++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken()) - 1;
            int j = Integer.parseInt(st.nextToken()) - 1;

            int[] tmp = new int[j-i+1];
            int ridx = 0;
            for(int r=j; r>=i; r--) {
                tmp[ridx] = arr[r];
                ridx++;
            }
            ridx = i;
            for(int r : tmp) {
                arr[ridx] = r;
                ridx++;
            }
        }

        for(int res : arr) {
            bw.write(res + " ");
        }
               
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 배열의 특정 범위의 값을 역순으로 만들어 저장하기 위해 임시 배열을 별도로 만들어 덮어씌우는 방식을 생각해낼 수 있었다.

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy