문제 설명
Agoji 씨는 특수한 문자열을 무작위로 섞은 뒤섞인 문자열을 받았습니다. 스팅은 특정 단어를 여러 번 결합하여 형성되는 경우에만 스페셜이라고 합니다. 특수 단어는 숫자(0 <= 숫자 < 10)를 해당 단어로 매핑하는 것입니다. 예를 들어 '0'을 '0'으로 매핑, '1'을 '1'로 매핑 등이 있습니다. Agoji 씨는 섞인 문자열을 가장 작은 특수 숫자로 변환하도록 요청받습니다. 특수 숫자는 선행 0이 없는 숫자(0 <= 숫자 < 10)를 사용하여 형성된 숫자입니다. Agoji 씨는 숫자와 문자열에 서툴러서 도움을 요청합니다.
입력 형식
입력의 첫 번째 줄에는 T, 테스트 사례 수, 1 <= T <= 100이 포함됩니다. 각 테스트 사례에 대해 별도의 줄에 섞인 문자열이 있습니다.
1 <= 길이 <= 100000
출력 형식
각 테스트 사례에 대해 새 줄에서 가장 작은 특수 숫자는 문자열 형식입니다. 출력에 대한 몇 가지 참고 사항: 섞인 문자열은 항상 하나 이상의 유효한 특수 문자열로 변환할 수 있습니다. 섞인 문자열에는 작은 영어 알파벳만 포함됩니다. 섞인 문자열에 0만 포함된 경우 "0"을 출력해야 합니다.
접근하다:
- 숫자를 단어로 매핑하기
- 입력 문자열에서 문자의 빈도 맵 생성
- 0에서 9까지의 모든 숫자를 순회하고 얼마나 많은 숫자가 문자열로 표현되는지 확인합니다. digit_freq 사전 에 저장
- digit_freq 의 모든 숫자를 정렬 하고 그로부터 문자열을 만듭니다.
- 우리가 돌봐야 할 극단적인 경우는 거의 없습니다. 모두 0이면 0을 반환합니다. 또 다른 극단적인 경우는 결과 문자열의 앞에 0을 둘 수 없다는 것입니다. 요구 사항에 따라 가장 작은 숫자를 생성하기 위해 0이 아닌 첫 번째 숫자 뒤에 모든 0을 유지할 수 있습니다.
def smallest_special_number(string):
num_to_word = {
'0' : 'zero',
'1' : 'one',
'2' : 'two',
'3' : 'three',
'4' : 'four',
'5' : 'five',
'6' : 'six',
'7' : 'seven',
'8' : 'eight',
'9' : 'nine',
}
char_freq = {}
for char in string:
if char not in char_freq:
char_freq[char] = 1
else:
char_freq[char] += 1
digit_freq = {}
for digit in num_to_word:
word = num_to_word[digit]
count = char_freq.get(word[0], 0)
for char in word[1:]:
count = min(count, char_freq.get(char, 0))
digit_freq[digit] = count
result = ''
for num in sorted(digit_freq.keys()):
result += num * digit_freq[num]
# Handle special cases
if len(result) == 0:
return '0'
if result[0] == '0':
zeros = 1
for i in range(1, len(result)):
if result[i] == '0':
zeros += 1
else:
break
if zeros == len(result):
return '0'
if zeros != 0:
result = result[i] + '0' * zeros + result[i+1:]
return result
# Read input and process test cases
s = "ewtooetzrowon"
print(smallest_special_number(s))
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
scanner.nextLine();
while (t-- > 0) {
String s = scanner.nextLine();
String result = smallestSpecialNumber(s);
System.out.println(result);
}
scanner.close();
}
public static String smallestSpecialNumber(String string) {
Map<Character, String> numToWord = new HashMap<Character, String>() {{
put('0', "zero");
put('1', "one");
put('2', "two");
put('3', "three");
put('4', "four");
put('5', "five");
put('6', "six");
put('7', "seven");
put('8', "eight");
put('9', "nine");
}};
Map<Character, Integer> charFreq = new HashMap<>();
for (char c : string.toCharArray()) {
charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> digitFreq = new HashMap<>();
for (char digit : numToWord.keySet()) {
String word = numToWord.get(digit);
int count = charFreq.getOrDefault(word.charAt(0), 0);
for (int i = 1; i < word.length(); i++) {
count = Math.min(count, charFreq.getOrDefault(word.charAt(i), 0));
}
digitFreq.put(digit, count);
}
StringBuilder sb = new StringBuilder();
for (char digit = '0'; digit <= '9'; digit++) {
int freq = digitFreq.getOrDefault(digit, 0);
sb.append(String.valueOf(digit).repeat(freq));
}
String result = sb.toString();
// Handle special cases
if (result.length() == 0) {
return "0";
}
if (result.charAt(0) == '0') {
int zeros = 1;
int i = 1;
for (; i < result.length(); i++) {
if (result.charAt(i) == '0') {
zeros++;
} else {
break;
}
}
if (zeros == result.length()) {
return "0";
}
result = result.charAt(i) + "0".repeat(zeros) + result.substring(i + 1);
}
return result;
}
}
이 설명이 도움이 되셨다면 미디엄 과 유튜브 에서 저를 팔로우 해주세요 .
박수를 클릭하여 다른 사용자에게 이 기사를 찾는 도움말 알고리즘입니다. :)
