Array.prototype.indexOf() 에 대하여

코딩테스트를 대비해 프로그래머스에서 알고리즘 문제를 풀던 중 원인을 알 수 없는 에러를 맞닥뜨렸다.

 

'2021 Dev-Matching: 웹 백엔드 개발자(상반기)' 문제 중 '다단계 칫솔 판매'

 위 문제를 요약하면 트리구조를 가진 다단계 회사에서 구성원이 벌어들인 금액을 9:1의 비율로 나눠 9는 해당 구성원이 가지고 1은 추천인에게 상납이 되고, 그 추천인이 받은 상납금을 또 9:1로 나눠 9를 추천인 자신이, 1은 그 추천인을 추천한 추천인에게 상납이되며 더 이상 나눌 수 없을 때 까지 진행한다. 최종적으로 모두 벌어들인 금액이 분배 됐을 때의 상황을 배열로 만들어 반환하는 문제였다. https://programmers.co.kr/learn/courses/30/lessons/77486

function solution(enroll, referral, seller, amount) {
    let answer = new Array(enroll.length).fill(0);
    
    // 판매자 목록 전체를 체크한다.
    for (let i = 0; i < seller.length; i++) {
    
    	//총금액과 나눠지는 금액을 계산한다.
        let gross = amount[i]*100
        let balance = Math.floor(gross*0.1)
        let share = gross-balance
        
        //현재 판매자의 이름과 인덱스를 선언한다.
        let cur_enroll = seller[i]
        let enr_Idx = enroll.indexOf(cur_enroll)
       
       	//인덱스가 범위를 벗어나거나(존재하지않는 판매자) 
        //나눠져야할 총금액이 더 이상 나눌 수 없을때까지 while문을 반복한다.
        while (enr_Idx > -1 && gross > 0) {
        
        	//현재 판매자가 가져가야할 몫(9/10)을 할당한다.
            answer[enr_Idx] += share
   			
            //현재 판매자의 추천인을 찾고
            cur_enroll = referral[enr_Idx]
            //그 추천인의 인덱스를 찾는다.
            enr_Idx = enroll.indexOf(cur_enroll)
            
            //할당된 금액을 뺀 나머지를 총 금액으로 할당하고 다시 나눠지는 금액을 계산한다.
            gross = balance
            balance = Math.floor(gross*0.1)
            share = gross-balance
        }
    }

    return answer;
}

 위 처럼 문제를 풀고 테스트 케이스를 모두 통과하고 제출을 했는데 마지막 3가지의 케이스에서 시간 초과 에러가 나왔다. 코드를 여러번 다시 보고 여기저기 로그를 찍어보며 확인을 했지만 코드상에서 문제는 없었다. 보통 시간초과가 된다면 필요없는 반복문에 의해 시간복잡도가 최적화 되지 않았기 때문에 일어나는데, 처음에는 어디가 문제인지 찾을 수 가 없었다. 그러다가 indexOf()의 메서드가 눈에 띄었다. 해당 메서드가 인덱스를 찾기 위해 어떠한 로직을 가지고 있을까 생각을 해보니 해당 배열의 0번째 인덱스에 위치한 값부터 찾고자하는 값과 비교하여 같은 값 일 경우 해당 인덱스를 반환을 하는 로직일 것이라고 생각이 들었다. 그래서 MDN문서를 찾아보니 가장 첫 줄에 'indexOf() 메서드는 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환합니다.' 라고 적혀있었다. 해당 배열에 똑같은 값이 있다면 그 중 가장 첫번째 요소만 반환하는 것이기 때문에 앞에서부터 전체 배열을 확인하는 로직이라는 생각이 맞다는 것을 확인했다.

 

 그래서 모든 값을 확인해야하는 배열을 객체형태로 변환하면 바로 찾을 수 있겠다라고 생각이 들었다. 

 

function solution(enroll, referral, seller, amount) {
    var answer = new Array(enroll.length).fill(0);
    
    //enroll배열의 요소를 키, 인덱스를 값으로 하는 객체를 생성한다.
    //(이름을 통해 인덱스를 찾아야하기 때문에)
    let obj_enroll = enroll.reduce(function(target, key, index) {
      target[key] = index;
      return target;
    }, {})
    
    //referral의 경우 enroll에서 찾은 인덱스로 이름을 찾기 때문에 구조분해할당으로 객체를 생성한다.
    let obj_referral = {...referral}
    
    for (let i = 0; i < seller.length; i++) {
        let gross = amount[i]*100
        let balance = Math.floor(gross*0.1)
        let share = gross-balance   
        let cur_enroll = seller[i]
        let enr_Idx = obj_enroll[cur_enroll]
       
        while (enr_Idx > -1 && gross > 0) {
            answer[enr_Idx] += share
   
            cur_enroll = referral[enr_Idx]
            enr_Idx = obj_enroll[cur_enroll]
            gross = balance
            balance = Math.floor(gross*0.1)
            share = gross-balance

        }
        
    }

    return answer;
}

 위와 같이 코드를 변경하니 모두 잘 통과가 되었고, 2000ms가 넘게 걸리던 한 테스트도 100분의 1의 속도로 줄어 해결을 할 수 있었다. 이번문제를 계기로 내장 메서드들을 잘 쓰는 것도 중요하지만 편하다고 내장 메서드들을 쓰는 것은 비효율적일 수 있다는 것을 배웠다. 하나의 메서드를 쓰더라도 잘 알고 써야겠다.