[SWEA/Java] 5672. 올해의 조련사

[SWEA/Java] 5672. 올해의 조련사

SW Expert Academy

---

문제 해석

이 문제는 문자열로 이루어진 배열에서 사전적으로 가장 작은 문자열을 만들기 위해 앞뒤에서 문자를 하나씩 선택하는 시뮬레이션 문제이다. 앞 또는 뒤에서 문자를 선택하여 결과 문자열을 조합할 때, 매 선택에서 앞 또는 뒤 중 사전적으로 더 작은 문자를 선택한다. 만약 앞과 뒤의 문자가 같을 경우, 더 내부의 문자까지 비교하여 결정을 내려야 한다.

풀이 과정

제출된 코드는 주어진 배열의 맨 앞과 맨 뒤 문자를 비교하여 더 작은 문자를 결과 문자열에 추가하는 과정을 반복한다. 만약 두 문자가 같을 경우, check 함수를 재귀적으로 호출하여 더 안쪽의 문자까지 비교하고, 어느 쪽을 선택할지 결정한다. 이러한 과정을 배열의 모든 문자가 선택될 때까지 반복한다.

코드

package edu.ssafy.im.SWEA.D4.No5672;

import java.io.*;

public class Solution {
    private int N; // 문자의 개수
    private char[] arr; // 입력 문자를 저장하는 배열
    private StringBuilder sb = new StringBuilder(); // 결과를 저장하는 StringBuilder

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); // 문자열 길이
            arr = new char[N];
            for (int i = 0; i < N; i++) {
                arr[i] = br.readLine().charAt(0); // 문자를 배열에 저장
            }
            sb.append("#").append(t).append(" ");
            sol(); // 문제 해결 함수 호출
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        int i = 0, j = N-1;
        while(i < j) {
            if (arr[i] < arr[j]) sb.append(arr[i++]);
            else if (arr[i] > arr[j]) sb.append(arr[j--]);
            else {
                sb.append(arr[i]);
                if(check(i+1, j-1)) i++;
                else j--;
            }
        }
        sb.append(arr[i]).append("\n"); // 마지막 문자 추가
    }

    private boolean check(int i, int j) {
        if (i >= j) return true;
        if (arr[i] < arr[j]) return true;
        if (arr[i] > arr[j]) return false;
        return check(i+1, j-1); // 재귀 호출을 통해 내부 문자 비교
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 최악의 경우 각 문자 선택에서 내부 문자 비교(check 함수)까지 고려할 때 𝑂(𝑁^2)가 될 수 있다. 하지만 평균적으로는 각 문자 비교가 균등하게 분포되므로, 효율적으로 작동할 것이다.

느낀점

이 문제를 통해 사전적으로 문자를 선택하는 간단해 보이는 문제에서도 재귀적 사고를 통해 깊이 있는 비교를 수행할 수 있음을 배웠다. 또한, 시뮬레이션과 재귀 호출을 적절히 조합하는 방법에 대해 더 잘 이해할 수 있었다.