HackerRank - weighted-uniform-string

문제 [링크]

소문자 a ~ z 는 각각 1 ~ 26까지 대응한다.

동일한 연속된 알파벳은 각 숫자값이 누적해서 계산될수 있다.

예를 들어 abccddde 이라고 한다면 아래와 같이 1, 2, 3, 4, 5, 6, 8, 12 라는 숫자가 각각 적용되는 것이다.

a	1
b	2
c	3
cc	3+3 = 6
d	4
dd	4+4 = 8
ddd	4+4+4 = 12
e	5

입력은 

abccddde

6

1

3

12

5

9

10

이라고 입력된다. 제일 위에는 문자, 그 아래 숫자는 총 입력되는 숫자를 의미한다. (위에서는 자기 제외하고 6개 숫자가 입력된다는 의미)다.) 그리고 그밑의 1, 3, 12, 5, 9, 10 인데 여기서 9, 10은 적용되지 않는다. 적용되는건 Yes, 아닌건 No로 반환한다.

따라서 위의 입력이 되면 아래와 같이 반환되어야 한다.

Yes

Yes

Yes

Yes

No

No

풀이

function run(str) {
    const checkArr = [...new Float32Array(10000000)];
    let temp = num = str[0].charCodeAt() - 96;
    checkArr[num]++;
    for(let i = 1; i < str.length; i++) {
        if(str[i] === str[i-1]) checkArr[num += temp]++;
        else checkArr[temp = num = str[i].charCodeAt() - 96]++;
    }
    const result = [];
    for(let i = 0; i < checkArr.length; i++) {
        if(checkArr[i]) result.push(i);
    }
    return result;
}
 
function main() {
    var s = readLine();
    var n = parseInt(readLine());
    var check = run(s);
    for(var a0 = 0; a0 < n; a0++){
        var x = parseInt(readLine());
        // your code goes here
        
        console.log(check[x]> -1 ? "Yes" : "No" )
    }
}

처음에는 배열을 이용해서 각 배열마다 1부터 시작되는 숫자를 했었다.

하지만 테스트 해보니 거의 다 틀렸다고 나오길래 혹시나 해서 인풋 최대값인 10000000 으로 배열크기를 키웠다.

그랬더니 느리기는 했지만 어떻게 통과는 했다. 그래서 다시 조정을 했다.

// 개선1
function run(str) {
    const check = Object.create(null);
    let temp = num = str[0].charCodeAt() - 96;
    check[num] = 1;
    for(let i = 1; i < str.length; i++) {
        if(str[i] === str[i-1]) check[num += temp] = 1;
        else check[temp = num = str[i].charCodeAt() - 96] = 1;
    }
    return check;
}
 
// 개선2 - 1~26까지 값 연산하는게 더 느릴거 같아서 alpha에서 찾아 쓰게 변환
function run(str) {
    const check = Object.create(null);
    const alpha = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8, 'i':9, 'j':10, 
                   'k':11, 'l':12, 'm':13, 'n':14, 'o':15, 'p':16, 'q':17, 'r':18, 's':19, 
                   't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25, 'z':26};
    let temp = num = alpha[str[0]];
    check[num] = 1;
    for(let i = 1; i < str.length; i++) {
        (str[i] === str[i-1]) ? check[num += temp] = 1 : check[temp = num = alpha[str[i]]] = 1;
    }
    return check;
}
 
// 공통
function main() {
    var s = readLine();
    var n = parseInt(readLine());
    var check = run(s);
    for(var a0 = 0; a0 < n; a0++){
        var x = parseInt(readLine());
        console.log(check[x]? "Yes" : "No" )
    }
}

이렇게 했더니 성능이 훨씬 나아졌다.