6034 : 중복 문자 제거 — 사전순 최소
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
소문자 알파벳으로만 구성된 문자열이 주어집니다.
문자열에 등장하는 중복된 문자들을 제거하여, 모든 알파벳이 정확히 한 번씩만 등장하는 새로운 문자열을 만드십시오.
이때, 가능한 여러 문자열 중 사전순으로 가장 빠른(가장 작은) 문자열을 구하십시오.
단, 문자의 원래 상대적인 등장 순서 구조는 보존되어야 합니다.
[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 문자열 길이: $1 \le$ 길이 $\le 10{,}000$ (소문자로만 구성)
문자열에 등장하는 중복된 문자들을 제거하여, 모든 알파벳이 정확히 한 번씩만 등장하는 새로운 문자열을 만드십시오.
이때, 가능한 여러 문자열 중 사전순으로 가장 빠른(가장 작은) 문자열을 구하십시오.
단, 문자의 원래 상대적인 등장 순서 구조는 보존되어야 합니다.
[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 문자열 길이: $1 \le$ 길이 $\le 10{,}000$ (소문자로만 구성)
입력 설명
첫째 줄에 테스트케이스 수 $T$가 주어집니다. ($1 \le T \le 100$)
둘째 줄부터 $T$개의 줄에 소문자 문자열이 주어집니다. (길이 $\le 10,000$)
둘째 줄부터 $T$개의 줄에 소문자 문자열이 주어집니다. (길이 $\le 10,000$)
출력 설명
각 테스트케이스에 대해 중복 문자를 제거하고 남은 사전순 최솟값 문자열을 줄바꿈하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
cbacdcbc
bcabc
acdb
출력 예시
COPY
복사되었습니다!
복사되었습니다!
acdb
abc
acdb도움
각 문자의 남은 빈도 카운터를 유지하면서 단조 스택을 활용합니다. 스택의 top 문자가 현재 문자보다 크고 뒤에 더 등장할 여지가 있다면(카운터 > 0), 스택에서 pop하여 제거합니다.