문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

문자열 s가 주어진다. 다음의 알고리즘을 사용하여 재정렬해라.

1. s에서 가장 작은 문자를 제거하고 결과에 추가해라.
2. s에서 마지막에 추가된 문자보다 큰 가장 작은 문자를 제거하고 결과에 추가해라.
3. 더 이상 제거할 수 없을 때까지 2단계를 반복해라.
4. s에서 가장 큰 문자를 제거하고 결과에 추가해라.
5. s에서 마지막에 추가된 문자보다 작고 가장 큰 문자를 제거하고 결과에 추가해라.
6. 더 이상 제거할 수 없을 때까지 5단계를 반복해라.
7. s에서 모든 문자를 제거할 때까지 1단계에서 6단계까지 반복해라.

가장 작은 문자나 가장 큰 문자가 한 번 보다 더 나타나면 임의의 문자를 선택하여 결과에 추가할 수 있다.
알고리즘을 사용해서 문자열 s를 재정렬한 후 결과를 반환해라.

Example

#1
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"

#2
Input: s = "rat"
Output: "art"

Constraints

• 1 <= s.length <= 500
• s는 오직 영어 소문자로 구성된다.

Solved

class Solution {
    public String sortString(String s) {
        int [] freq = new int[26];

        for (char ch: s.toCharArray()) {
            freq[ch - 'a'] += 1;
        }

        StringBuilder result = new StringBuilder();
        
        while (result.length() < s.length()) {
            for(int i = 0; i < 26; i++) {
                if (freq[i] > 0) {
                    result.append((char) (i + 'a'));
                    freq[i]--;
                }
            }

            for(int i = 25; i >= 0; i--) {
                if (freq[i] > 0) {
                    result.append((char) (i + 'a'));
                    freq[i]--;
                }
            }
        }
        
        return result.toString();
    }
}