[Javascript] 1663. Smallest String With A Given Numeric Value -쉬운 설명

1663. Smallest String With A Given Numeric Value

 

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

 

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

 

Example 2: 

Input: n = 5, k = 73
Output: "aaszz"

 

 

 

계획

문제 해결 전략

 

우선 문제에서 말하는 lexicographically 의 의미는 사전적 순서를 의미합니다. 사전적 순서라는 정의로 모두 이해하기 힘들기때문에 예를 들어보겠습니다.

 

사전에서 children과 chill을 찾는 다고 가정해봅시다. 이 두단어 모두 chil을 공통적으로 가지고 있습니다. 그러면 둘중 어떤 단어가 먼저 보일까요? 

 

사전은 chil다음 character를 찾아봅니다. children에서 다음 character은 d이고 chil다음의 character은 l 입니다. 알파벳 순서로 d는 i 보다 앞에있습니다. 그러므로 children이 우선으로 보이고 다음 chill순서로 나타내게됩니다. 

 

우선 몇자리 string이 될지는 input인 n이 결정합니다. 그리고 정해진 자릿수를 유지해서 k를 맞춰야합니다. 

 

 

아래 예시를 먼저 살펴보겠습니다. 

 

우리가 function에 input으로 n과 k를 받게됩니다. 

 

n(자릿수)이 3이고 k(타겟넘버) 8입니다. 

그러면 우리가 주의해주어야할것은 1. 사전적 순서를 2. n의 길이를 맞추고 3. 조합의 합이 k 가되도록 해야합니다. 

 

우선 조합을 만들기위해 n개의 character가 답에있어야하기때문에, 반복문에서 답을 넣어줄때 n번만 넣어주면됩니다. 

 

 

구현 전략

 

위와같이, k는 h하나로 타겟넘버에 도달할수있지만 n, 즉 자리수가 4이므로 h하나로 리턴하게되면 n값을 충족못하게됩니다. 

 

이처럼 알파벳은 총 26개로 이루어져있기때문에 26 이하의 수는 하나의 알파벳으로 나타낼수있지만, n값을 먼저 확인하고 해야합니다. 

 

위 특징을 이용하면 반환할 문자열을 만들어줄때, 우리가 반복해야할 횟수를 구할수있습니다.  

 

n번만큼 반복하면됩니다. 

 

 

해설

 

 

var getSmallestString = function(n, k) { //n은 3 k = 27
   	
    //0을 나타내기위해 0의 자리에는 '' 비어있는 스트링을 적었습니다. 
    const alphabet = ['','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']
    
    let sum = 0
    
    //결과값이 s 에 들어가게됩니다. 
    let s = ''
    
    for (let i = n - 1; i >= 0; i--) {
    	//자리수를 맞추기위해서 현재 맞춰야할 타겟을 설정합니다. 현재 타겟은 
        //Input으로 넣어준 k - 현재 남은 자릿수(i) - 지금까지 더한수(sum)
        let target = (k - i) - sum
        
        //타겟이 위과정을 걸치고도 26이상이면 다시 타겟을 26으로 설정하고 
        if (target > 26) target = 26
        
        // 알파벳오더 array에서 target위치에있는 알파벳을 s결과값 앞부분에 붙여넣는다. 그리고 지금까지 만든 문자열을 뒤에 붙인다. 
        s = alphabet[target] + s
        
        //sum
        sum += target
        
    }

    return s
};