[취업준비일지] - 116

서울에서 진행되는 면접 준비로
이것저것 확인할 것이 많아 알고리즘만 진행했다.

 

 

(1).백준 10816 숫자 카드 2는 상근이가 가지고 있는 카드(50만개 이하) 중
몇 개를 가지고 있는지 궁금한 숫자 배열(50만개 이하)을 넣어 
각각의 숫자의 보유 갯수를 확인하는 문제였다.

50만이나 되는 수치기 때문에 시간초과가 날 거라고 생각했지만
다행히도 바로 통과될 수 있었다.

아무래도 50만개나 되는 수치기 때문에 중복되는 값을 많이 담았던 것 같은데
만약 각기 다 다른 숫자 50만개였다면 object에 값이 담길 때 정렬되는 문제 때문에
유사한 처리를 했을 때 10초가 넘어서 중단된 기억이 있는데
만약 이번에 시간 부족이었다면 이분탐색을 사용해서 진행했을 것 같다.

이분탐색을 사용할 때는 중복되는 값들이 있기 때문에 2개의 이분탐색을 진행하는데
첫 번째 이분탐색은 해당 인덱스는 일치하고 다음 인덱스의  값이 일치하지 않는 것이며
두 번째 이분탐색은 해당 인덱스는 일치하고 이전 인덱스의 값이 일치하지 않는 것이다.

간단한 예시를 들자면 [0,0,0,1,2,2,2,2,3,4,5,8]이라는 배열이 있을 경우
우리는 2의 갯수를 찾아야 하는데 만약 첫 번째 이분탐색을 한다면 2,3의 위치에서 멈출 것이다.
또한 두 번째 이분탐색을 진행하면 1,2의 위치에서 멈출 것이고 두 인덱스의 차이를 통해
2의 갯수가 4개인 것을 파악할 수 있다.

또한 [2]하나만 존재한다고 하더라도 문제없이 진행할 수 있으며
(2의 다음 index와 이전 index의 값은 둘 다 undefined다)
[1,3,5,7,9]처럼 값이 없는 경우 첫 번째 시도에서 값이 없다면 두 번째 시도를 할 필요 없이
바로 중단시키고 0개를 출력하면 되는 방식이다.

하지만 내일 서울까지 가는 면접이 있기 때문에
이분탐색 방식은 수도코드로만 작성하고 
하단의 코드는 객체를 활용한 해결 방식이다.

const input = `10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10`.split('\n')

const sanggeunCard = input[1].split(' ').map(Number)
const needToCheck = input[3].split(' ').map(Number)
const hashObject = {}
const result = []

for(let i = 0 ; i < sanggeunCard.length ; i++){
    const hashingNow = sanggeunCard[i]
    if(hashObject[hashingNow]){
        hashObject[hashingNow]++
    }
    else hashObject[hashingNow] = 1
}

needToCheck.forEach(el => {
    if(hashObject[el]){
        result.push(hashObject[el])
    }
    else{
        result.push(0)
    }
})

console.log(result.join(' '))