[백준] 2947번 - 나무 조각

문제 링크 : https://www.acmicpc.net/problem/2947

문제 탐색하기

1) 문제 분석

한 행에 다섯 개의 숫자가 입력된다.
위치가 바뀔 때마다 현재 순서를 출력한다.

2) 가능한 시간복잡도

(1) 입력 처리

한 줄에 주어진 다섯 개의 숫자(split(' ').map(Number)를 배열로 변환 -> O(1)

(2) 정렬 처리

문제는 인접한 두 수를 비교하고, 조건에 맞으면 swap하며 과정을 반복한다.
이는 버블 정렬과 동일한 구조로 동작한다.
- 버블 정렬의 최악 시간복잡도는 O(N의 제곱)이며,
- 여기서 N = 5이므로, O(25) = O(1) 수준의 연산이다.

(3) 출력 처리

sawp이 일어날 때마다 현재 배열 상태를 출력 -> 최대 N(N-1)/2번까지 가능하다.
출력 1회당 O(N)(배열을 join하여 문자열로 변환)
- 최악 : O(N의 제곱)번 출력, 각 출력당 O(N)
- 총 출력 비용 : O(N의 세제곱)
- 하지만 N = 5로 고정이므로, 실제 실행 시간은 매우 작다.

(4) 전체 시간복잡도

입력 처리 : O(1)
정렬 처리 : O(N의 제곱)
출력 처리 : O(N의 세제곱)-> 총합 : O(N의 제곱) ~ O(N의 세제곱) (N = 5인 문제이므로 실질적으론 상수 시간이다.)

3) 알고리즘 선택 이유

이 문제는 주어진 5개의 나무 조각 숫자를 '인접한 두 조각을 조건에 따라 swap'하는 과정을 반복면서 최종적으로 오름차순으로 만드는 과정 전체를 출력하는 문제이다.
이 과정은 전형적인 버블 정렬 알고리즘의 변형이며, 버블정렬은 구현이 간단하고 문제 조건에도 딱 들어 맞는다.
입력 크기가 현재 5로써 작기 때문에 O(N의 제곱)의 알고리즘이어도 큰 문제가 되지 않으며, 매 swap마다 배열을 출력해야 하므로, 단순 정렬 알고리즘보다 이 버블 방식이 더 자연스럽고 직관적이라고 생각했다.

코드 설계하기

1. 실행 구조

1) 5개의 숫자를 입력 받는다.

2) 해당 숫자를 공백 기준으로 분리하고, 숫자로 변환하여 배열로 저장한다.

3) 함수의 인자값으로 넘긴 뒤에, 종료 조건(flag)값이 변하지 않을 때만큼 연산을 반복한다.

4) 배열의 길이 만큼 반복문을 진행하여, 값을 비교하여 swap 여부를 판단한다.

5) 만약 swap이 발생하였다면, swap을 진행한 상태의 배열을 출력한다.

2. 고민이 되었던 부분

JavaScript

do {
    flag = 0; // 한 번 탐색을 위해서는 flag를 0으로 초기화

    // 배열 길이 만큼 탐색하면서 swap 조건 발견하면 swap 진행 후 출력
    for (let i = 0; i < input.length-1; i++){
        if (input[i] > input[i + 1]) {
            [input[i], input[i+1]] = swap(input[i], input[i + 1]); // swap
            console.log(input.join(" ")); // 출력
            flag = 1; // swap 발생으로 인한 flag를 1으로 변경
        }
    }
} while (flag != 0);

swap을 진행해야 할 경우가 있는지를 먼저 파악하는 것이 핵심이라고 생각했다. 그렇다면 반복문 구조상, 조건을 먼저 확인하기보다는 행동을 먼저 수행한 뒤 조건을 평가하는 방식이 적절하다고 판단되었고, 이에 따라 do~while문을 사용하는 것이 최적이라고 생각했다.

또한, swap이 발생했는지를 판단하기 위해 flag 변수를 도입했고, 이 값이 변경되었다면 아직 정렬이 진행 중이라는 신호이므로, 이를 기반으로 반복의 계속 여부를 결정할 수 있도록 했다.

이처럼 단순한 반복 구조라고 할지라도, 어떤 흐름이 더 적절한지 고민하고, 그에 맞는 구조를 선택하여 구현해 나가는 과정 자체가 이번 문제에서 가장 인상 깊었다. 특히, 문제 해결 과정 속에서 작은 의사결정 하나하나가 전체 흐름에 영향을 줄 수 있음을 다시금 체감할 수 있었다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 기준대로 배열을 정렬하고, swap 발생시 출력하는 함수
function getSwapAndSort(input) {

    let flag = 0; // 종료 조건을 위한 변수

    // 탐색 후 종료 조건을 확인하는 것을 위해 do~while문 사용
    do {
        flag = 0; // 한 번 탐색을 위해서는 flag를 0으로 초기화

        // 배열 길이 만큼 탐색하면서 swap 조건 발견하면 swap 진행 후 출력
        for (let i = 0; i < input.length-1; i++){
            if (input[i] > input[i + 1]) {
                [input[i], input[i+1]] = swap(input[i], input[i + 1]); // swap
                console.log(input.join(" ")); // 출력
                flag = 1; // swap 발생으로 인한 flag를 1으로 변경
            }
        }
    } while (flag != 0);

    return input; // 결과를 return
}

// 두 수를 swap하는 함수
function swap(num1, num2) {
    return [num2, num1];
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 입력 받은 행의 값을 숫자로 변환 후 배열로 저장
const scores = input[0].split(' ').map(Number);

// 함수 실행
getSwapAndSort(scores);

마무리하며

WhyDev를 시작하고 지금까지 풀어왔던 문제들 중에서, 이번 문제는 유독 많은 고민이 필요했던 문제였던 것 같다. 처음 문제를 마주했을 때, 제시된 조건들이 다소 복잡하고 낯설게 느껴져서 쉽게 구조를 파악하기 어려웠다. 한 단계씩 읽어 내려가면서 이 조건들을 코드로 어떻게 구현할 수 있을지 감이 잘 오지 않아 처음엔 막막하기도 했다.

하지만 잠시 멈춰서 문제의 핵심 흐름을 분석해보니, 주어진 조건들이 일종의 버블 정렬과 매우 유사한 구조를 가지고 있다는 것을 발견할 수 있었다. 이 깨달음을 통해 문제의 전반적인 구조가 명확해졌고, 익숙한 알고리즘을 바탕으로 설계를 이어나갈 수 있었다.

특히 정렬이 완성되기까지 swap 여부를 확인하며 반복문을 설계하는 과정에서, 단순한 반복문 구조에도 의사결정이 필요하다는 것을 새삼 느꼈고, 그 선택 하나하나가 전체 로직의 자연스러움과 효율성을 좌우한다는 점을 다시 한번 깨달았다.

결국 초반의 막막함을 딛고 문제를 해결해 나가는 과정 자체가 굉장히 의미 있었고, 작은 아이디어 하나로 복잡했던 흐름이 명확해지는 경험이 인상 깊었다. 앞으로도 낯선 조건이나 복잡한 설명에 압도되지 않고, 본질적인 구조를 파악하려는 태도를 꾸준히 유지하고 싶다.

최근 글