문제 설명
- s라는 문자열이 주어질 때, 단 한 번만 문자가 나오도록 해야 하며 사전순으로 더 앞에 있는 문자열을 반환하는 문제.
- Lexicographically Smaller : 사전순으로 더 앞에 있는 문자열
예를 들어, string s = "cbacdcbc" 가 있다고 했을 때, 출력은 acdb가 된다.
틀린 풀이
-
그 이유에 대해서 설명해보자면, 일단 한 번만 문자가 나오도록 해야 한다고 했으므로, 앞에서부터 c b a 이런 식으로 부분 문자열이 처리될 것이다.
-
그러다가 다음 문자인, 3번 인덱스 c를 순회하는 시점에 c는 이미 부분 문자열에 추가된 것이므로, 단 한 번만 문자가 나오도록 해야 한다는 것에 위배되므로 해당 인덱스는 넘어간다.
-
d의 경우에는 아직 부분 문자열에 나오지 않았으므로 추가되어 cbad가 된다.
-
그 다음에 있는 c -> b -> c 모두 부분 문자열에 추가되어 있으므로 정답은 cbad ??
-
위 풀이에 대해서 틀린 부분이 존재하는데, 그 부분은 바로 사전순으로 더 앞에 있는 문자열을 구하는 부분이 빠져있는 것이다.
-
사전순으로 더 앞에 있는지를 체크하기 위해서는 어떻게 해야 하는지 다시 살펴보자.
정상 풀이
- 다시 맨 처음부터 진행해보면, cb 이렇게 부분 문자열을 처리하다가 a라는 것을 만나는 순간, a는 b보다 사전순으로 더 앞에오는 문자가 된다. 즉, 만약에 b라는 문자가 입력값으로 주어진 문자열에서 뒤쪽에서 한 번이라도 등장한다면, b는 여기서 제거되어도 된다. 즉, 현재 상황에서는 b가 제거된, result에는 c만 들어가있는 상태가 된다.
- 그럼 이제 c뒤에 a를 붙이면 되는가? -> 아니다. c또한 사전순으로 보았을 때 a보다 더 뒤에 존재하므로, 입력값으로 주어진 문자열에 대해서 뒤쪽에 c 문자가 한 번이라도 더 등장한다면 c또한 현재 상황에서 제거되어도 된다. 따라서 c를 제거하고 a를 result에 추가시키면 된다.
- 이런 방식으로 문제를 풀이하면 되는데, 여기서 추가되어야 할 부분은 result의 맨 뒤(back)에 해당하는 문자를 지워도 되는지 안되는지에 대한 판단이 필요하다.
- 입력값으로 주어진 문자열에 대해서 추후에 현재 지우고 싶은 문자가 등장하느냐에 대한 파트만 처리하면 되는데 이는, unordered_map을 통해 주어진 입력 문자열을 모두 순회하면서 해당 문자가 등장하는 여러 인덱스에서 가장 큰 인덱스를 구한다면 처리할 수 있게 된다.
- 즉,
unordered_map<char, int> indexMap이라는 변수를 통해 해당 문자의 가장 뒤에 나오는 인덱스를 저장만 해둔다면 처리할 수 있게 된다.
전체 알고리즘
class Solution {
public:
string smallestSubsequence(string s) {
// 1. 문자열 내의 각 문자들에 대해서 가장 뒤에 나오는 인덱스를 먼저 구한다.
unordered_map<char, int> charIndexMap;
for (int i = 0; i < s.size(); i++)
{
charIndexMap[s[i]] = i;
}
string result = "";
unordered_set
<char> uniqueSet; // 고유한 문자인지 체크하는 변수.
for (int i = 0; i < s.size(); i++)
{
if (uniqueSet.contains(s[i]))
continue;
// 조건 : 사전순으로 s[i]가 더 작고, 추후에 result.back()에 해당하는 문자가 나온다면
// result.back()에 해당하는 문자는 제거되어도 된다.
while (result.empty() == false && result.back() > s[i] && charIndexMap[result.back()] > i)
{
uniqueSet.erase(result.back());
result.pop_back();
}
uniqueSet.insert(s[i]);
result += s[i];
}
return result;
}
};
No Comment! Be the first one.