import java.util.*;

class Solution {

    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] result = new int[n + 1];
        
        int left = 0;
        int right = n;
        
        // 문자열 s를 순회하면서 각 문자에 따라 적절한 값을 result 배열에 할당
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') { // 'I'인 경우
                result[i] = left; // 작은 값을 할당
                left++;
            } else { // 'D'인 경우
                result[i] = right; // 큰 값을 할당
                right--;
            }
        }

        // 마지막 요소는 남아 있는 left 값으로 설정
        result[n] = left;

        return result;
    }
}

Approaches

이 문제는 주어진 문자열 s에 따라 perm 배열을 구성하는 문제입니다. I와 D의 특성을 이용하여 가장 작은 값 left와 가장 큰 값 right를 적절히 배치하는 그리디 알고리즘을 사용합니다.

문자열 s의 각 문자에 대해 순회하면서,
- I이면 left 값을 배열에 추가하고 증가시킵니다.
- D이면 right 값을 배열에 추가하고 감소시킵니다.
마지막으로 남은 값은 left로 배열을 채웁니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 배열을 사용하여 추가적인 공간을 요구하므로 공간 복잡도는 O(n)입니다.

이 문제는 문자열을 다루는 기술과 그리디 알고리즘을 연습하는 데 유용합니다. 이를 통해 주어진 조건에 맞는 최적의 해를 찾는 방법을 배울 수 있습니다.

Algorithm
Greedy