12/22 nest.js & 알고리즘

내일배움캠프 오늘 학습 내용

 

• nest.js의 기본 기능 익히기.
• 알고리즘 문제 해결

 

알고리즘

 

매일 알고리즘 풀기를 진행하고 있었는데 이번에 막힌 문제가 있어 그것을 소개하고자 한다. (프로그래머스 옹알이 2)

https://school.programmers.co.kr/learn/courses/30/lessons/133499

프로그래머스

특정 문자열이 포함되는지를 확인하고 발음할 수 있으면 +1 하여 반환하는 문제이다. 이 문제를 처음 풀었을 때의 코드는 이러하였는데, 정답이 100%가 되지 않았다. 각 문자가 포함되는지 확인하고, 두 번 반복되는 안 된다는 조건에 따라 repeat를 사용해 반복되지 않도록 하여, 전부 문자열이 지워진다면 해당 문장은 발음할 수 있다는 것으로 filter를 사용하여 length를 구하는 방식이었다.

function solution(babbling) {
    var answer = 0;
    const canSpoke = ["aya", "ye", "woo", "ma"];
    const result = babbling.filter((e)=>{
        let comparison = e;
        canSpoke.forEach((word)=>{
            if(e.includes(word) && !e.includes(word.repeat(2))){
                comparison = comparison.replaceAll(canSpoke[i],"");
            }
        });
        if(comparison === ""){
            return true;
        }
    })
    answer = result.length;
    return answer;
}

 

 

프로그램에 100% 테스트 성공이 되지 않자 우선 반례를 먼저 찾아보기 시작하였다. 내 경험으로는 반례를 찾고 그 반례를 만족시키도록 코드를 수정하는 것이 편했기 때문이다. 그렇게 하여 찾은 반례는 다음과 같다.

console.log(solution(["ayamayaa"]));
//aya ma yaa로 나뉘지만, 위의 코드에서는 aya를 두 번 지우고 남은 m a를 합쳐 또 지워버리기 때문에 true가 되어버린다.

 

해당 문제를 해결하기 위해 우선 지우기 전에 해당 문자가 포함이 되는지 includesArr를 새로 만들어 선체크를 하고, 해당 arr에서 true일 때만 문자열을 지우도록 코드를 바꿔보았다. 하지만 위의 반례 역시 ma와 aya가 include로 들어가 있어 해결책이 되지는 못하였다.

 

const result = babbling.filter((e)=>{
    let comparison = e;
    let includesArr = [];
    canSpoke.forEach((word)=>{
        if(e.includes(word) && !e.includes(word.repeat(2))){
            includesArr.push(true);
        } else {includesArr.push(false);}
    });
    includesArr.forEach((erase, i)=>{
        if(erase){
            comparison = comparison.replaceAll(canSpoke[i],"");
        }
    })
    if(comparison === ""){
        return true;
    }
});

 

근본적인 문제점으로는 문자열을 지워버리고 난 후의 문자열이 합쳐서 지워지지 않을 문자도 지우게 되는 문제이기 때문에 이번에는 replace를 처음부터 공백이 아닌 .으로 바꾸어 진행해보았다. 그렇게 하였더니 위의 반례도 .m.a가 남아 더는 지워지지 않았다. 최종으로 문제의 테스트 케이스를 100% 만족시킨 코드는 다음과 같았다. (오래 걸렸지만 발상의 전환 문제로 결국 간단한 문제였던 것 같다.)

 

function solution(babbling) {
    var answer = 0;
    const canSpoke = ["aya", "ye", "woo", "ma"];
    const result = babbling.filter((e)=>{
        let comparison = e;
        canSpoke.forEach((word)=>{
            if(e.includes(word) && !e.includes(word.repeat(2))){
                comparison = comparison.replaceAll(word,".");
            }
        });
        comparison = comparison.replaceAll(".", "");
        if(comparison === ""){
            return true;
        }
    });
    answer = result.length;
    return answer;
}

//aya/ma/yaa false
console.log(solution(["ayamayaa"]));