316. Remove Duplicate Letters (중복된 글자 제거)

문자열 s가 주어지면 모든 문자가 한 번만 표시되도록 중복된 문자를 제거합니다. 결과가 다음과 같은지 확인해야 합니다
가능한 사전 순서대로

 

예시 1:

입력: s = "bcabc"
출력: "abc"

 

예시 2:

입력: s = "cbacdcbc"
출력: "acdb"

 

 

 

조건:

• 1 <= s.length <= 10^4
• s는 소문자 영어로 구성됩니다.

 

정답:

public class Solution {
    public string RemoveDuplicateLetters(string s) {
         string result = "";

        string sequence = string.Concat(s.Distinct());
        char[] charArray = sequence.ToCharArray();
        Array.Sort(charArray);
        sequence = String.Join("", charArray);

        int resultLength = sequence.Length;

        int pointer = 0;

        while (result.Length != resultLength)
        {
            string testS = s.Substring(s.IndexOf(sequence[pointer]));
            
            if (sequence.Length == string.Concat(testS.Distinct()).Length)
            {
                result += sequence[pointer];
                s = testS;
                s = s.Replace(sequence[pointer].ToString(), "");
                sequence = sequence.Replace(sequence[pointer].ToString(), "");
                pointer = 0;
            }
            else
            {
                pointer += 1;
            }
        }
  
        return result;
    }
}

해설: 문자열 s가 주어졌을때 가장 이상적인 배열을 구하기 위하여 중복 제거 이후 순차적으로 정렬을 해줍니다.

그리고 해당 문자열을 sequence로 저장해줍니다.

sequence 첫번째 문자를 문자열s에서 찾은 이후 해당 문자를 기준으로 자른 이후 중복제거를 했을 때 sequence의 길이와 같다면 사전이 완성이 될 수 있다는 것이므로 result에 해당 문자를 저장하고 해당 문자를 모두 제거해줍니다.

만약 해당 문자를 제거했을 때 사전이 완성되지 않는다면 해당 문자는 넘어가고 다음 문자를 찾아 해당 작업을 반복합니다.