문제 링크
문제 요약
주어진 문자열 ()는 소문자 라틴 문자, 숫자, 밑줄 기호로 구성됩니다.
이 문자열에서 특정 한 종류의 문자를 선택하여 해당 문자의 모든 등장을 제거할 수 있습니다. 예를 들어, ‘a’를 선택했다면 문자열 내의 모든 ‘a’를 제거합니다.
이 작업을 통해 만들 수 있는 모든 문자열 중에서 사전순으로 가장 앞서는(가장 작은) 문자열을 찾아 출력하는 문제입니다.
풀이
문제의 목표는 사전순으로 가장 작은 문자열을 찾는 것입니다. 주어진 문자열 에서 단 하나의 문자를 선택하여 해당 문자의 모든 등장을 제거할 수 있습니다.
이 문제의 핵심은 입력 문자열 에 포함될 수 있는 고유한 문자의 종류가 매우 적다는 점입니다. 소문자 라틴 문자(26개), 숫자(10개), 밑줄 기호(1개)를 모두 합쳐도 최대 37가지의 고유한 문자만 존재할 수 있습니다.
따라서, 다음과 같은 전략을 사용합니다:
- 입력 문자열 에 등장하는 모든 고유한 문자들을 추출합니다. 이를
st(set of characters)에 저장합니다. st에 있는 각 고유 문자char에 대해 다음 작업을 수행합니다:- 원본 문자열 에서
char의 모든 등장을 제거한 새로운 문자열을 생성합니다. Python의str.replace(char, '')메서드를 사용하면 간편하게 구현할 수 있습니다. - 생성된 문자열을 리스트에 추가합니다.
- 원본 문자열 에서
- 모든 고유 문자에 대해 위 과정을 반복하면, 최대 37개의 서로 다른 문자열이 리스트에 저장됩니다.
- 이 문자열 리스트를 사전순으로 정렬합니다.
- 정렬된 리스트의 첫 번째 원소(가장 작은 문자열)를 출력합니다.
시간 복잡도:
- 고유 문자 추출 (
set(list(s))): O() - 각 고유 문자에 대해 문자열 생성 (
s.replace(char, '')): 고유 문자의 개수를 라고 할 때 (), 각 replace 연산은 O()입니다. 따라서 총 O(). - 생성된 문자열 정렬: 개의 문자열(최대 길이 )을 정렬하는 데 O()가 소요됩니다.
는 최대 이지만, 는 최대 37이므로 는 매우 작은 값입니다. 결과적으로 전체 시간 복잡도는 O()에 가깝기 때문에 주어진 제약 조건 내에서 충분히 효율적으로 동작합니다.
정답 코드
"""
[29300: Назначения](https://www.acmicpc.net/problem/29300)
Tier: Bronze 1
Category: implementation, string
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def solve():
s = inp()
st = set(list(s))
z = []
for i in st:
z.append(s.replace(i, ''))
print(sorted(z)[0])
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()