2021 Dev-Matching: 웹 백엔드 개발 문제이며 1레벨로 구분되어있다

문제

로또를 샀는데 번호 몇개가 지워졌다고 한다.
당첨번호를 보고 가능한 최고등수와 최저등수를 리턴하면된다.

풀이과정

<입력>

1. 찍은 로또번호 "lottos"(Array) - 지워진 번호는 0으로 표시되어있다.
2. 당첨번호 "win_nums"(Array)

<핵심아이디어>

가능한 최고등수: 지워진 번호가 모두 맞았다고 가정
가능한 최저등수: 지워진 번호가 모두 틀렸다고 가정

<아이디어 1>

<--맞춘 번호 갯수는 구하기 쉬운데 맞춘 갯수에 따라 등수를 표현하는 것이 직관적이지는 않은 문제-->
미리 맞춘 번호 갯수에 따라 등수로 변환할 수 있도록 배열에 넣어두기

const rank = [6,6,5,4,3,2,1] // 맞춘갯수의 index에 해당하는 rank를 미리 넣어두었다.

<아이디어 2>

<--이제부터는 맞춘 번호갯수를 어떻게 구할것이냐의 문제-->

includes()

가장 직관적인 방법인데 lottos 배열을 돌면서 각 요소가 win_nums에 포함되어있는가(includes()) 확인하여 포함되어있으면 맞춘갯수를 올려준다.
최고등수 구할때는 지워진번호(0) 나올때 마다 다 맞았다고 해주고
최저등수 구할때는 지워진번호(0) 나올때 마다 다 틀렸다고 해주자

const rank = [6,6,5,4,3,2,1]

let max = 0;                         //최고등수 맞은갯수
let min = 0;                         //최저등수 맞은갯수
for(const num of lottos){            //찍은 번호 배열을 돌면서
   if(num === 0){                    //0이면 최고등수 맞은갯수만 ++
      max++
   } else if(win_nums.includes(num){ //숫자를 당첨번호배열이 포함하고있으면
      max++		                     //최고등수 최저등수 둘다 ++
      min++
   }
}
return [rank[max],rank[min]]         //랭크에서 맞은갯수를 index로 하여 리턴

결과는? 문제가 직관적이어서 쉽게 풀 수 있었다.
하지만 뭔가 더 이 문제에서 얻어갈 수 있는게 없을까

includes 쓰지 않고 풀어보기

해당 문제에서는 배열이 6자리밖에 되지 않지만 배열이 길어질수록 요소마다 일일이 includes를 실행하면 시간복잡도가 커질 수 있을 것 같다.
includes보다 시간복잡도를 줄여서 할 수 있는 방법이 있을까?

let winNumber = new Array(46).fill(false)    //로또번호 길이 배열을 만들어 false로 초기화
    for(const num of win_nums){              //당첨번호 index만 true로 변경
        winNumber[num]=true
    }

당첨번호를 value가 아닌 index로 하여 정보를 저장하면 index번호로 접근했을 때 더 빠르게 해당번호가 당첨번호인지 확인이 가능하다

    let max = 0;
    let min = 0;
    for(const num of lottos){
        if(num===0){
            max++
        } else if(winNumber[num]){ // 요소마다 includes로 전체 배열을 순회하지 않고 해당 num의 index만 조회
            min++
            max++
        }

    }
    return [rank[max],rank[min]]

다만 예상대로 includes 순회의 대상이 될 win_nums의 길이가 짧고 그에 비해 로또번호 정보를 담을 배열을 만드는게 너무 길어서 효율은 좋아지지 않은것같다..
그래도 문제에 대한 여러 풀이 가능성을 찾아본것에 보람을 느낀다.