81.md

오픈채팅방

시간초과를 어떻게 해결해야할꼬?!

Try1

function solution(record) {
  const result = [];
  const already = new Map(); // 채팅방에 한 번이라도 와 본 유저의 id

  record.forEach((r) => {
    const [action, id, nickname] = r.split(' ');

    if (!already.has(id)) already.set(id, nickname);

    if (action === 'Enter') {
      const obj = {
        id,
        nickname,
        action: '님이 들어왔습니다.',
      };
      result.push(obj);

      if (already.has(id) && already.get(id) !== nickname) {
        already.set(id, nickname);
        result.forEach((user) => {
          if (user.id === id) user.nickname = nickname;
        });
      }
    } else if (action === 'Leave') {
      const nickname = result.filter((user) => user.id === id)[0].nickname;
      const obj = {
        id,
        nickname: '1',
        action: '님이 나갔습니다.',
      };
      result.push(obj);
    } else {
      result.forEach((user) => {
        if (user.id === id) user.nickname = nickname;
      });
    }
  });

  const messages = result.map((user) => user.nickname + user.action);
  return messages;
}

위의 코드는 로직상 문제가 없어보인다. 하지만 시간 초과가 생겼다. record의 제한 조건은 1 이상 100,000 이하이기 때문에 O(n^2)의 경우 100000 * 100000 의 복잡도가 생길수 있다. 그렇기 때문에 위 코드는 시간 초과가 나올수 밖에 없는 코드였다. 그래서 첫번째 for문 안에서 루프를 도는 코드들(forEach, filter 메소드)을 모두 주석 처리하고 다시 테스트를 돌려보았다. 문제는 당연히 틀렸지만 틀린 원인에서 시간 초과는 볼 수 없는 것을 확인하였기 때문에 시간 초과의 원인은 이중for문때문이라는 것을 확신할 수 있었다.

이중for문을 없애기위해서 result를 map으로 변경해보았다. 이 경우 result 요소의 key값을 action-id값으로 하였는데, 문제는 같은 아이디로 여러 번 방문하는 경우 이것이 추가될 수 없다는 것이였다. map에서는 키값은 유일하기 때문이다. 그렇다고 action-id-nickname 형식으로 하기엔 해당값을 특정짓기가 너무 복잡해질 수 있었다.

Try2

기능의 분리

어떻게 하면 for문을 없앨지 고민하던 중, 굳이 한 번에 닉네임까지 바꿀 필요가 없다는 생각을 하였다. 위에 기능의 분리라고 적었듯이, 첫번째 루프에서는 순서대로 id와 action에 대한 배열을 만들고 두번째 루프에서 만들어진 정보를 바탕으로 최종적인 유저정보를 맵핑해서 메세지를 보여주면 된다고 생각했다. 그리고 위 문제에서 요구사항이 최종적으로 변경된 닉네임으로 보여주는 것이기 때문에 이러한 로직이 좀 더 적합하다고 생각하였다. 닉네임을 찾는 과정은 map을 이용하여 O(1)의 복잡도를 갖도록 만들었다. 결국 아래 코드는 O(n^2)을 O(2n)으로 만들수 있게 되었다.(시간복잡도에서는 O(2n)은 O(n)과 동일하다.)

function solution(record) {
  const result = [];
  const nicknameMap = new Map(); // 채팅방에 한 번이라도 와 본 유저의 id

  record.forEach((r) => {
    const [action, id, nickname] = r.split(' ');
    nicknameMap.set(id, nickname || nicknameMap.get(id));
    if (action !== 'Change') {
      const obj = {
        id,
        action: action === 'Enter' ? '님이 들어왔습니다.' : '님이 나갔습니다.',
      };
      result.push(obj);
    }
  });

  const messages = result.map((user) => nicknameMap.get(user.id) + user.action);
  return messages;
}