프로그래머스 : 로또의 최고 순위와 최저 순위 - javascript(이분탐색 활용)

문제 출처 

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

프로그래머스

문제 풀이 힌트 

 

나는 이분탐색을 활용했다. 

만약? lotto 배열 길이가 6으로 한정되지 않고, 정말 큰 수라면 ~ 을 가정했기 때문이다 ! 

 

correct = 같은 수가 몇개인지 

zero = 0이 몇개인지

 

7-correct를 하면 그 수가 최저 등수가 된다. 

근데 만약 7-correct가 7이상이된다면, 최저등수 즉, min 값을 6으로 설정한다. (그 값이 최저 등수임) 

 

min - zero(0이 몇개인지) 이 값이 최고등수가 된다. 즉 max ! 

근데 최고등수가 0이하로 나타나면 그 값을 1로 설정한다. (그 값이 최고등수임)

 

정답 풀이 코드 

function solution(lottos, win_nums) {
    let sorted = win_nums.sort((a,b) => a-b); //오름차순 정렬
    let zero = 0; //0이 몇개인지
    let correct = 0; //맞힌 숫자가 몇개인지
    for(let i=0; i<lottos.length; i++){ //자기가 쓴 lotto 반복문
        if(lottos[i] === 0) zero++; 
        else{
            let start = 0; //처음 idx
            let end = win_nums.length-1; //끝 idx
           let flag = binarySearch(start, end, lottos[i], sorted) //이분탐색
           if(flag === true) correct++; //true라면 correct+1
        }
    }
   function binarySearch(start, end, a, B){
       if(start > end) return false; //start > end 인 순간이 오면 false
       let mid = Math.floor((start+end)/2); // 중간idx
       if(a < B[mid]){ //a가 더 작으면
           return binarySearch(start, mid-1, a, B) //끝 idx를 중간 idx-1
       }else if(a > B[mid]){ //a가 더 크면
            return binarySearch(mid+1, end, a, B) //처음 idx를 중간 idx+1
       }else{
           return true; // 값이 같다면 true
       }
   }
       let min = 7-correct; 
       if(min >= 7) min = 6; 
       let max = min - zero; 
       if(max <= 0) max = 1; 
       return [max, min]
}

 

Only 풀이 코드 

function solution(lottos, win_nums) {
    let sorted = win_nums.sort((a,b) => a-b); 
    let zero = 0; 
    let correct = 0; 
    for(let i=0; i<lottos.length; i++){
        if(lottos[i] === 0) zero++; 
        else{
            let start = 0; 
            let end = win_nums.length-1;
           let flag = binarySearch(start, end, lottos[i], sorted)
           if(flag === true) correct++; 
        }
    }
   function binarySearch(start, end, a, B){
       if(start > end) return false; 
       let mid = Math.floor((start+end)/2); 
       if(a < B[mid]){
           return binarySearch(start, mid-1, a, B)
       }else if(a > B[mid]){
            return binarySearch(mid+1, end, a, B)
       }else{
           return true; 
       }
   }
       let min = 7-correct; 
       if(min >= 7) min = 6; 
       let max = min - zero; 
       if(max <= 0) max = 1; 
       return [max, min]
}

 

다른 사람 풀이 코드 

function solution(lottos, win_nums) {
    // 배열을 정렬시킨다.
    // 순서대로 값을 비교
    // 0인 경우 다 맞다는 가정
    // 0인 경우 다 틀리다는 가정
    let answer = [];
    const correct = lottos.filter(lotto => win_nums.includes(lotto)).length;
    const zerro = lottos.filter(lotto => lotto === 0).length;

    let min = 7-correct >= 6 ? 6 : 7-correct;
    let max = min - zerro <= 1 ? 1 : min - zerro;

    answer = [max, min]
    return answer
}