Shuffle String — UnStop 샘플 질문

문제 설명

Agoji 씨는 특수한 문자열을 무작위로 섞은 뒤섞인 문자열을 받았습니다. 스팅은 특정 단어를 여러 번 결합하여 형성되는 경우에만 스페셜이라고 합니다. 특수 단어는 숫자(0 <= 숫자 < 10)를 해당 단어로 매핑하는 것입니다. 예를 들어 '0'을 '0'으로 매핑, '1'을 '1'로 매핑 등이 있습니다. Agoji 씨는 섞인 문자열을 가장 작은 특수 숫자로 변환하도록 요청받습니다. 특수 숫자는 선행 0이 없는 숫자(0 <= 숫자 < 10)를 사용하여 형성된 숫자입니다. Agoji 씨는 숫자와 문자열에 서툴러서 도움을 요청합니다.

입력 형식

입력의 첫 번째 줄에는 T, 테스트 사례 수, 1 <= T <= 100이 포함됩니다. 각 테스트 사례에 대해 별도의 줄에 섞인 문자열이 있습니다.

1 <= 길이 <= 100000

출력 형식

각 테스트 사례에 대해 새 줄에서 가장 작은 특수 숫자는 문자열 형식입니다. 출력에 대한 몇 가지 참고 사항: 섞인 문자열은 항상 하나 이상의 유효한 특수 문자열로 변환할 수 있습니다. 섞인 문자열에는 작은 영어 알파벳만 포함됩니다. 섞인 문자열에 0만 포함된 경우 "0"을 출력해야 합니다.

접근하다:

1. 숫자를 단어로 매핑하기
2. 입력 문자열에서 문자의 빈도 맵 생성
3. 0에서 9까지의 모든 숫자를 순회하고 얼마나 많은 숫자가 문자열로 표현되는지 확인합니다. digit_freq 사전 에 저장
4. digit_freq 의 모든 숫자를 정렬 하고 그로부터 문자열을 만듭니다.
5. 우리가 돌봐야 할 극단적인 경우는 거의 없습니다. 모두 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;
    }
}

이 설명이 도움이 되셨다면 미디엄 과 유튜브 에서 저를 팔로우 해주세요 .

박수를 클릭하여 다른 사용자에게 이 기사를 찾는 도움말 알고리즘입니다. :)