[프로그래머스] 완전 탐색 _ 모의고사 (javascript)

2021_10_12_ 알고리즘 스터디 문제 풀이

모의고사 -> 문제 URL 

코딩테스트 연습 - 모의고사

문제

 

문제를 보자마자 반복되는 패턴을 먼저 확인했다.

dropper1 은 [1, 2, 3, 4, 5], dropper2는 [2, 1, 2, 3, 2, 4, 1, 5], dropper3은 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] 반복적으로 나와 이것을 이용해 answers의 길이만큼 각 수포자가 제출한 답안을 만든 뒤, 그 값으로 answers의 인자(답)과 비교하여 알맞은 것만 filter 메소드로 추출하여 score를 구한다.

그리고 그 score중에 최댓값을 구해 최댓값과 같은 것들의 수포자 번호를 배열의 형태로 담아 오름차순으로 리턴하는 것을 목표로 했다.

사실 이를 구현하기까지 삽질이 한 번 있었는데, 코드를 다시 보니 말도안되게 장황하고 불필요한 구현이 좀 있었다.

먼저 삽질한 코드를 먼저 보겠다.

삽질 수도코드

1번 : 1, 2, 3, 4, 5, ...
2번 : 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

answer배열을 가지고 가장 정답을 많이 맞춘 수포자의 번호를 리턴한다
동점이라면 오름차순 정렬해서 리턴한다

점수를 카운팅할 함수를 별도로 만든다
채점 함수 선언, 수포자의 답지형식을 받는다 ex) personalAnswer = [1, 2, 3, 4, 5]
    resolvedAnswer = [], 빈배열 선언
    answers의 길이만큼 수포자의 답을 추가해야한다.

	만약, answers의 길이가 personalAnswer.length 보다 크다면 
    	while 문을 돌며 resolvedAnswer.length가 Math.floor(answers.length / personalAnswer.length)일때까지 반복
            ResolvedAnswer.concat(answerForm)을 진행
    	answers의 길이를 personalAnswer.length로 나눴을 때 나머지를 구한다
    	나머지가 있는 경우 나머지만큼 resolvedAnswer에 이어 붙인다

	그렇지 않다면,
    	answers의 길이만큼 personalAnswer.slice를 이용, 잘라서 resolvedAnswer에 할당한다
        
    resolvedAnswer을 filter로 순회한다 (as, idx)
        순회 조건은 answers[idx]와 idx가 같고, as의 값이 같은 경우만 (답이 맞는 경우)
    resolvedAnswer의 길이를 리턴한다



수포자 1, 2, 3에 대한 점수를 먼저 받는다

dropper1 = getScore([1, 2, 3, 4, 5]) 
dropper2 = getScore([2, 1, 2, 3, 2, 4, 2, 5])
dropper3 = getScore([3, 3, 1, 1, 2, 2, 4, 4, 5, 5])

Math.max(dropper1, dropper2, dropper3) 최댓값을 뽑는다
scores 배열 선언
할당 [{id : 1, score : dropper1}, {id : 2, score : dropper2}, {id : 3, score : dropper3}]

scores를 filter로 순회한다 . item.score가 최댓값과 같은 것들만
그걸 map으로 id만 추출
그리고 그걸 sort로 오름차순한 후 리턴한다

 

코드

function solution(answers) {
    function getScore(personalAnswer) {
        let resolvedAnswer = [];
        const remainder = answers.length % personalAnswer.length;

        if (answers.length > personalAnswer.length) {
            while (resolvedAnswer.length < Math.floor(answers.length / personalAnswer.length)) {
            resolvedAnswer.push(...personalAnswer)
          }
            if (remainder > 0) {
                  resolvedAnswer.push(...personalAnswer.slice(0, remainder));
              }
        } else {
            resolvedAnswer.push(...personalAnswer.slice(0, answers.length))
        }

        return resolvedAnswer.filter((item, idx) => answers[idx] === item).length
    }
    
    const dropper1 = getScore([1, 2, 3, 4, 5]) 
    const dropper2 = getScore([2, 1, 2, 3, 2, 4, 2, 5])
    console.log(dropper2)
    const dropper3 = getScore([3, 3, 1, 1, 2, 2, 4, 4, 5, 5]);
    const highScore = Math.max(dropper1, dropper2, dropper3);
    
    const scores = [{id : 1, score : dropper1}, {id : 2, score : dropper2}, {id : 3, score : dropper3}];
    
    return scores.filter((item, idx) => item.score === highScore).map((item) => item.id).sort()
    
}

채점

무언가 심히 잘못되었음을 깨달았다.. getScore 함수에서 채점 결과가 명확하지 않은 것으로 나오는데, 테스트케이스에서는 문제없이 출력되는 걸 확인했다. 코드가 지저분하고 비효율적인 것 같아 디버깅을 계속하기보다는 쓸모없는 코드를 지우고 단순화에 집중을 해서 다시 작성해보았다.

코드

function solution(answers) {
    const pattern1 = [1, 2, 3, 4, 5]
    const pattern2 = [2, 1, 2, 3, 2, 4, 2, 5]
    const pattern3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    const dropper1 = answers.filter((item, idx) => item === pattern1[idx % pattern1.length]).length
    const dropper2 = answers.filter((item, idx) => item === pattern2[idx % pattern2.length]).length
    const dropper3 = answers.filter((item, idx) => item === pattern3[idx % pattern3.length]).length
    const highScore = Math.max(dropper1, dropper2, dropper3);
    
    const scores = [{id : 1, score : dropper1}, {id : 2, score : dropper2}, {id : 3, score : dropper3}];
    
    return scores.filter((item, idx) => item.score === highScore).map((item) => item.id).sort();
}

수포자들이 제출하는 답안에 대한 패턴을 별도 상수에 선언했다.

그리고 getScore함수에서 답안지의 길이만큼 유저의 답안지를 만들고 채점하는 로직을 간단하게 filter함수를 사용해서 별도의 배열을 생성하지 않고도 채점을 할 수 있도록 만들었다.

최댓값을 저장해놓은 뒤 scores배열에 객체 형태로 각 값을 담은 뒤 최댓값과 일치하는 요소를 찾아 id만을 뽑아 맵핑하고, sort로 최종 정렬하는 코드로 구현했다.

scores를 굳이 객체에 담아서 filter와 map까지 사용하는 게 맞을까하는 의심을 하긴 했다. 그냥 3명에 대해 모두 조건을 걸어 최종 결과 배열에 추가하는 코드로 할까 하다가 무엇인가 하드코딩적인 느낌이 날 찝찝하게 만들었다. 지금 코드도 맘에 안들긴 해서 조금 더 깔끔한 코드를 구현하는 방법에 대해서는 고민이 필요할 듯 하다.

시간복잡도는 O(n)이다.

채점

채점 결과