프로그래머스 [오픈채팅방] - 해시 Lv.2

해시 테이블을 이용한 풀이

• 데이터를 key, value 형태로 보관할 수 있는 해시테이블 자료구조를 이용하여 풀이하였다.

로직

• 제시된 문제에서는 uid 별로 닉네임의 변경기록을 알 수 있다.
  • 들어오고 나가거나 닉네임을 변경한 기록이 record에 들어있다.
  • 하지만 uid는 고유한 값을 가진다. 따라서 uid 별로 최종적으로 정해진 닉네임을 먼저 key와 value 형태로 저장한다.
  • 그 다음, record 배열을 순회하며 들어온 경우와 나간 경우를 분기하여 최종적으로 정해진 닉네임을 이용하여 문장을 만들고, 차례대로 정답을 담을 배열에 담는다.
  • 정담을 담은 배열을 반환한다.

첫 풀이 때 시간 초과 다수

• 배열을 순회하며, 해시테이블에서 저장한 uid의 닉네임 값을 가져올 때, 해시테이블을 배열로 만들고, 여기서 filter와 flatMap을 이용하여 아예 해당 uid에 해당하는 정보만 남기고 모조리 필터링 했었다.
• 이 과정에서 시간복잡도 O(n^3)이 발생하여, 이미 1억 제곱을 넘어가기 때문에 시간 초과가 발생했을 것이다.

filter와 flatMap 대신 해시테이블에서 직접 값 가져오기

• 따라서 map에 저장된 정보를 get 함수를 이용하여 가져오는 것으로 해결하였다.

최종 코드

function solution(record) {
    
    record = record.map(item => item.split(' '))
    
    const idMap = new Map()
    const result = []
    
    record.forEach(item => {
        if(item.length >= 3) {
            idMap.set(item[1], item[2])
        }
    })
    
    for(let i = 0; i < record.length; i++) {
        // 유저가 방에 입장한 경우
        if(record[i][0] === 'Enter') {
            // record[i][1] 가 들어온 경우(유저 아이디)
            // 유저 아이디님이 들어왔습니다. 를 result에 push
            // 이때 가져오는건 [...idMap]에서 record[i][1]의 값에 일치하는 것
          const name = idMap.get(record[i][1])
          result.push(`${name}님이 들어왔습니다.`)
        }
        else if(record[i][0] === 'Leave') {
          const name = idMap.get(record[i][1])
          result.push(`${name}님이 나갔습니다.`)            
        }
    }
     return result
}

후기

• Map과 set, 그리고 get에 대한 글 하나를 작성할 계획이다.
• 대략적인 개념과 사용법을 알고 있지만, 추후에 정말 딥하게 사용할 때를 대비하여 제대로 파볼 계획이다.