[Golang으로 도전하는 Leetcode] Smallest String With A Given Numeric Value

제목1 본고딕 오늘 풀 문제는 Smallest String With A Given Numeric Value라는 문제이며

링크는 leetcode.com/problems/smallest-string-with-a-given-numeric-value/입니다

이 문제는 각 알파벳을 a를 1로 z를 26로합니다 

그리고 k에 해당하는 만큼의 숫자를 알파벳 스트링으로 만드는 문제입니다

알파벳 길이는 n만큼이어야한다는 조건도 있습니다

또한 사전순배열로 되어야 하는 조건도 있습니다

저는 그리디로  사전순 배열이 되어야 하므로 뒤에서부터 z를 다채우는 식으로 접근을 하였습니다

뒤에서부터 26으로 나누고 26보다 크면 z로 채우고 26보다 작으면 그 해당하는 인덱스를 채우고 0이면 a로 채우는 로직으로 하였습니다

코드는 아래와 같습니다

 

func getSmallestString(n int, k int) string {
    start_num := k -n;
    var temp_list []string = make([]string, n)
    alphabet := [27]string{"", "a", "b", "c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
    for n > 0 {
        if(start_num + 1 > 26){
            temp_list[n-1] =  alphabet[26];

            start_num = start_num - 25
        }else if(start_num == 0){
            temp_list[n-1] =  alphabet[1];

        }else{
            temp_list[n-1] = alphabet[start_num + 1];
            start_num = 0;
        }

        n--;
    }
    
    return strings.Join(temp_list, "")
    
}

 

처음에 리스트로 받지 않고 string concat으로 구현하였는데 이 부분이 O(n^2)이 되어가지고 시간초과가 났습니다

하나 배우게 해준 문제입니다

감사합니다