99클럽 5일차 TIL (240726)

오늘의 문제 : 전화번호 목록

걸린시간 : 1시간

권장시간 : 30분

 

오늘의 회고

- 첫번째 시도 : 이중 for문 / phone_book의 길이가 1,000,000이기 때문에 시간초과 위험이 있다. 그러나 다른 방법이 생각나지 않아 문자열 비교를 위해 시도해보았다. => 역시나 실패, 해시로 접근해야하는 것을 알 수 있었음.

- 문제를 다시 읽어보았다. 접두사의 조건은 A문자열이 다른 B문자열의 앞에서 일정범위의 문자열과 일치한다면 A는 B의 접두사이다. 그래서 hash테이블을 만들고, 돌면서 해당 해쉬 키값의 길이를 자르며 자른 문자열이 존재하는지 확인한다.

 

✋ Hash

- key-value 쌍으로 이루워진 자료구조

- 이진탐색트리나 배열에 비해 원하는 키 값을 검색하는 속도가 빠름.

- 검색, 삽입, 삭제 시간복잡도 : O(1)

 

문제 풀이

1. javascript

function solution(phone_book) {
    var answer = true;
    
    let hashTable = {}
    phone_book.forEach(i=>hashTable[i] = true)
    
    Object.keys(hashTable).forEach((item,idx)=>{
        for( let i=1; i<item.length; i++) {
            if(hashTable[item.substring(0, i)]) answer = false;
        }
    })
    
    return answer;
}

 

2.pyhton

def solution(phone_book):
    answer = True
    hash = { phone_book[i]:True for i in range(len(phone_book))}
    
    for item in hash :
        for i in range(1, len(item)) :
            if hash.get(item[:i]) : answer = False
    
    return answer

 

---

 

챌린저문제 : 베스트앨범

 

걸린시간 : 1시간 10분

권장시간 : 1시간

 

문제 회고

- 같은 장르로 hash 테이블 생성 후, 앨범의 고유번호를 저장했다. 그리고 해시테이블을 돌면서 원하는 조건대로 정렬했다. 가장 많이 재생된 노래를 두개씩 리턴했다.

- 문제 조건 중, 장르에 속한 곡이 하나라면 하나의 곡만 선택한다는 조건을 충족해야 한다! (중요)

 

문제 풀이

1. javascript

function solution(genres, plays) {
    var answer = [];
    let hash = {};
    genres.forEach(i=>hash[i]=[])
    
    for(let i=0; i<genres.length; i++){
        hash[genres[i]].push(i)
    }
    
    // 1 sum정렬
    let arr = Object.entries(hash).sort((a,b)=> {
        let sumA = 0;
        let sumB = 0;
        a[1].forEach(i=>sumA += plays[i])
        b[1].forEach(i=>sumB += plays[i])
        
        return sumB - sumA
    });
    
    // 2. 재생횟수가 많은 > 고유번호가 낮은
    for(const num in arr) {
        arr[num][1] = arr[num][1].sort((a,b)=>plays[b] - plays[a])
        
        if(arr[num][1].length < 2) answer.push(arr[num][1][0])
        else {
            for(let i=0; i<2; i++){
                answer.push(arr[num][1][i])
            }
        }
    }
    
    return answer;
}

 

2.python

def solution(genres, plays):
    answer = []
    hash = {i:[] for i in genres}
    
    # 장르를 key 값으로 hash table을 생성한다.value는 장르의 재생된 횟수를 배열로 해서 넣는다.
    
    for i in range(len(genres)) :
        hash[genres[i]].append(i)
    
    hash = sorted(hash.items(), key=lambda x: sum([ plays[i] for i in x[1]]), reverse=True)
    
    for item in hash :
        arr = sorted(list(item[1]), key=lambda x : plays[x], reverse=True)
        
        if len(arr) < 2 :
            answer.append(arr[0])
        else :
            for i in range(2) :
                answer.append(arr[i])
    
    return answer

 

느낀점

- 해시테이블을 이용한 빠른 검색 속도, 효율적인 정렬을 자유자재로 할 수 있도록 연습해야겠다.