[원순열] 프로그래머스 '연속 부분 순열의 합의 개수' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/131701#qna

프로그래머스

2. 코드

처음 접근했던 방법은 실패였다. 왜냐?! '연속 부분' 수열의 합을 구하는 것을 간과했기 때문에... 서로 옆에 붙어있는 요소들끼리만 더할 수 있다는 것을 잊고 dfs로 구현을 했다 ㅠㅠ 그래도 안심되는 것은 이제 문제를 보고 dfs도 떠올릴 줄 알고,,, 코드도 직접 짤 줄도 알고,, 파라미터도 스스로 생각한다는 것이다. 많이 컸네? :)

function solution(elements) {
    let answer = [];
    
    const dfs = (length, sum, arr) => {
        if(length <= elements.length){
            if(elements.length - arr.length === length && !answer.includes(sum)){
                answer.push(sum);
                dfs(length + 1, 0, elements);
            }else{
                arr.map((el,idx) => {
                    let newSum = sum + el;
                    let newArr = arr.slice();
                    newArr.splice(idx,1);
                    dfs(length, newSum, newArr);
                })
            }
        }
    }
    
    dfs(1,0,elements)
    
    return answer.length;
}

정답 코드)

원순열에 관련된 문제는 처음 풀어보는데, 이때에는 concat을 사용하여 1개부터 elemets.length개를 더하는 경우를 처리해주는 것 같다.

원순열 문제가 나오면 해당 방식을 기억하여 이대로 접근해주면 좋을 것 같다!

원순열 => concat을 사용해 원하는 만큼의 요소를 뒤에 붙혀주기

function solution(elements) {
    let answer = new Set();
    
    for(let i=0;i<elements.length;i++){
        let els = elements.concat(elements.slice(0,i));
        
        for(let j=0;j<elements.length;j++){
            answer.add(els.slice(j,j+i+1).reduce((a,c) => a+=c),0);
        }
    }
    
    return answer.size;
}

 

비록 접근법은 틀렸지만 dfs를 혼자 구현해서 뿌듯한 삐약쓰

복기

5/25