2021 Dev-Matching: 웹 백엔드 개발 문제이며 1레벨로 구분되어있다
로또를 샀는데 번호 몇개가 지워졌다고 한다.
당첨번호를 보고 가능한 최고등수와 최저등수를 리턴하면된다.
가능한 최고등수: 지워진 번호가 모두 맞았다고 가정
가능한 최저등수: 지워진 번호가 모두 틀렸다고 가정
<--맞춘 번호 갯수는 구하기 쉬운데 맞춘 갯수에 따라 등수를 표현하는 것이 직관적이지는 않은 문제-->
미리 맞춘 번호 갯수에 따라 등수로 변환할 수 있도록 배열에 넣어두기
const rank = [6,6,5,4,3,2,1] // 맞춘갯수의 index에 해당하는 rank를 미리 넣어두었다.
<--이제부터는 맞춘 번호갯수를 어떻게 구할것이냐의 문제-->
가장 직관적인 방법인데 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로 하여 리턴
결과는? 문제가 직관적이어서 쉽게 풀 수 있었다.
하지만 뭔가 더 이 문제에서 얻어갈 수 있는게 없을까
해당 문제에서는 배열이 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의 길이가 짧고 그에 비해 로또번호 정보를 담을 배열을 만드는게 너무 길어서 효율은 좋아지지 않은것같다..
그래도 문제에 대한 여러 풀이 가능성을 찾아본것에 보람을 느낀다.