[BOJ]2605번: 줄 세우기

2605: 줄 세우기

풀이

이 문제는 여러가지 방법으로 풀 수 있다는 생각을 했다.

스택으로도 풀 수 있고, swap으로도 풀 수 있다는 생각을 했지만 나는 swap으로 했다.

별로 추천하고 싶은 방법은 아니지만 도저히 이 방법 밖에는 생각이 나지 않았기 때문에 이 방식으로 문제를 해결했다.

1) 우선 나는 1부터 n까지의 숫자를 배열에 다 채웠다.

2) 반복문을 i = 0 ~ i < n  만큼 도는데, 변수 idx의 값은 i에 따라 바뀐다.(순서대로 돌기 때문에)

3) 뽑은 번호를 x라고 할 때 x == 0이면 아무런 행동도 취하지 않으므로 continue를 해주고 나머지 경우에는

    x번 만큼 반복문을 돌면서 swap을 해주면 된다.

4) 마지막 출력!!!

 

아직도 잘 모르겠다고요? 네 충분히 이해합니다. 저도 다른 블로그에서 이렇게 써 놨으면 바로 이해는 못 했을테니 말이죠.

그렇다면 우리 예제를 보면서 이해해봅시다.

예제로는

 

이렇게 주어져 있죠. 저의 방식대로 1번 순서대로 따라간다면 배열에 {1, 2, 3, 4, 5} 라는 값이 채워져 있을 겁니다.

그리고 우리는 idx라는 애를 가지고 놀아야 합니다. 처음에 idx = 0이죠. 아무짓도 하지 않습니다.

그 다음, idx = 1 이죠. 한 칸을 움직여야 합니다. 그런데 사실 잘 보면 앞에 값과 swap하는 것입니다.

다음 idx = 2은 앞에 상황과 같으니 패스하고 idx = 3일 때를 봅시다. 

이제는 우리가  배열에 {2, 3, 1, 4, 5} 라는 값을 가지고 있습니다.

4가 앞으로 3칸 움직여야 합니다. 저는 이때 고민했습니다. 그냥 4가 3칸 가고 뒤에 애들이 뒤로 한 칸씩 밀려나면 되는 거 아닐까? 라고는 생각했지만 그러기에는 너무 귀찮았죠.

그래서 "한번 4가 3칸 움직이는 과정(swap 방식)을 직접 적어보자" 하고 적어 봤습니다.

1.     4 3 1 2 5

2.     4 2 1 3 5

3.     4 2 3 1 5

... 끝내줍니다. 그냥 스왑을 계속 해주면 됐어요. 물론 스왑하는 인덱스 값의 차이만 좁혀주면서 말이죠.

그렇다면, idx = 4 일 때도 위와 같겠죠?

저의 설명은 끝입니다.

직접 적어보는 것도 꽤나 도움이 되더라고요. 참고로 이건 초등부 문제입니다( ㅎㅎㅎㅎㅎㅎ)

코드

#include <stdio.h>
 
int n, x, arr[102], idx = 0, swap_temp;
int main()
{
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) { arr[i - 1] = i; }
    for (int i = 0; i < n; ++i) { 
        idx = i;
        scanf("%d", &x);
        
        if (!x)
            continue;
        else {
            for (int i = 0; i < x; ++i) {
                swap_temp = arr[idx];
                arr[idx] = arr[idx + i - x];
                arr[idx + i - x] = swap_temp;
            }
        }
    }
 
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    return 0;
}