[Javascript(NodeJS)/Softeer] Lv3. 자동차 테스트 (HSAT 3회 정기 코딩 인증평가 기출)

 

https://softeer.ai/practice/6247

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

(답안 코드는 포스팅 맨 아래에 있습니다)

 

풀어서 제출해봤더니 0점 ㅋㅋ 시간초과 + 오답 대환장

---

try 1 : input 뿐만아니라 carList에 trim() 적용해주기

ㅋㅋㅋㅋ 어떤 분이 올려주신 글을 참고했다. 감사드립니다.

const carList = input[1].trim().split(' ').map(Number).sort((a, b) => a - b);

 

-> 시간초과 발생

---

try 2 : indexOf -> 이진탐색

테케 20번까지는 통과했는데, 21번부터 계속 시간초과남 ㅜㅡㅜ

 

 

---

try 3 : slice 대신 숫자 갯수만 구하기

slice로 부분배열을 구한 후, 두 배열의 length를 구해 곱했었는데

이 부분을 바로 '숫자 갯수'만 구하도록 효율적으로 변경했다

 

slice() 제거 → smallerCount, biggerCount만 계산

→ O(n) 연산을 O(1)로 최적화!

 

4트만에 성공

 

나의 풀이

const fs = require('fs');
const input = fs.readFileSync(0,'utf-8').trim().split('\n');

const [n,q] = input[0].split(' ');
const carList = input[1].trim().split(' ').map(Number).sort((a, b) => a - b);
let answer = 0;

const binarySearch=(m)=>{
    let left = 0; let right = n-1; let mid = 0;
    m = Number(m);
    
    while(left <= right){
        mid = Math.floor((left+right)/2);
        if(Number(carList[mid])===m) return mid;
        if(Number(carList[mid])<m) left = mid+1;
        else right = mid-1;
    }
    return -1;
}

const findGroup=(m)=>{
    // 중앙값이 m이 되려면, m보다 큰 수 하나 & 작은 수 하나 조합
    if(m <= carList[0] || m >= carList[n-1]) return 0;
    let idx = Number(binarySearch(m));
    if(idx<0) return 0;
    let smaller = idx;
    let bigger = n-idx-1;

    return smaller*bigger;
}

for(let inputIdx=2; inputIdx<input.length; ++inputIdx){
    console.log(findGroup(input[inputIdx]));
}