essential
essential

23. Best Album

해시맵을 사용해 ID와 닉네임을 저장하고, 기록을 두 번 순회하는 방식으로 최적화된 출력을 생성

algorithm test

22. OpenChat

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.257.


Problem solving

문제 이해

1. 닉네임이 변경되는 경우 살펴보자

  • 기존 방에 있던 회원이 나갔다가 다시들어오거나
  • 닉네임이 변경

= O(N2

record의 개수가 최대 10만개 일 경우, 비효율적일 수 있다.

2. 변경되는 시점과 변경하는 것을 명확히 규정해야한다.

  • 문제에서 요구하는 것은 최종적인 메시지
  • 유저 아이디는 불변이다.
  • 닉네임은 유저의 상태가 Enter와 Change인 때에만 바뀔 수 있다.


algorithm solving strategy

HashMap Dictionary

Jay Tak


3. 문제를 구조화 시켜보자

3.1 최종적으로 구하고자 하는 것은 무엇인가 → 최종적으로 보는 메시지

3.2 입력값 중 수정되지 않는 건 무엇인가 → 유저 아이디

3.3 입력값 중 수정되는 것은 무엇인가 → 닉네임

  • 3.3.1 입력값이 수정될 때 어디가 영향 받는가 → 오픈 채팅방의 내용 변경
  • 3.3.2 입력값은 어느 조건에 수정되는가 → Enter와 Chane인 경우
function solution(record) {
  answer = [];
  uid = {};

  for (line of record) {
    cmd = record[line].split("");
    if (cmd[0] != "Leave") {
      uid[cmd[1]] = cmd[2];
    }
  }
  for (line of record) {
    cmd = record[line].split("");
    if(cmd[0] == "Enter") {
      answer.push(uid[cmd[1]] + "님이 들어왔습니다.");
    } else if(cmd[0] == "Leave") {
      answer.push(uid.[cmd[1]] + "님이 나갔습니다.");
    }
  }
  return answer
}


자료구조 사용 이유
해시맵 (딕셔너리) uid 객체를 활용해 유저 ID → 최신 닉네임을 저장
배열 (리스트) answer 배열을 활용해 순서를 유지하며 메시지 저장
문자열 처리 split(" ")을 이용해 명령어, ID, 닉네임을 분리




🧐 Q. 왜 해시맵을 사용했을까?

Answer)

  1. "Change" 시 uid[cmd[1]] = cmd[2] O(1) 연산으로 닉네임 변경 가능

  2. 최신 닉네임을 바로 가져올 수 있어(uid[cmd[1]]), answer에 추가하는 과정이 O(1)

  3. 유저 ID를 key로 사용하므로 중복 방지 & 최신 정보 유지 가능




Development
Algorithm