[Programmers] 오픈채팅방

1. 문제

코딩테스트 연습 - 오픈채팅방

⭐ 카카오 2019 블라인드 공개채용 기출문제

2. 실수

loop을 2번 중첩했다가 시간초과로 75점을 맞았다.

 

loop 2중첩 시나리오는 다음과 같았다.

아이디 - 닉네임이 매핑되어야 한다는 사실로부터

(1)  중복을 제거한 아이디 목록 Set (집합)

(2) Set element 수 == 회원수 만큼 loop 

(3) (2) loop 안에서 record 로그 수만큼 또 loop

 

(2) + (3) => Time Complexity O(N^2) => 시간 초과

// 중복제거한 아이디 목록
val userIdSet = record.map{it.split(" ")[1]}.toSet()


// 아이디 '갯수' == 유저수 만큼 loop을 돌며 마지막 로그를 검사하는 loop
// Time Complexity O(N^2).. fucking
userIdSet.forEach{
	for(index in record.indices.reversed()){
    // do something
    }
}

 

3. 시나리오

(1) 회원 아이디와 닉네임을 key-value로 같는 Map 자료구조를 사용한다.

(2) 💡 채팅 로그는 '역순으로' 검사한다.  (최종 닉네임은 마지막에 반영) // O(N)

(3) 행위 (Enter, Leave, Change) 중 Enter, Change 로 끝나는 시점의 닉네임이 최종 반영 닉네임

   Leave는 이전 행위 (Enter, Change) 를 만날 때 까지 추가 검사

(4) 채팅 로그 배열 ArrayList // O(N)

   * Change는 로그를 남기지 않음 

(5) Return ArrayList to Array

 

선형 시간복잡도 O(N)를 가지고 풀이에 성공!

 

4. 풀이 (Kotlin)