오픈채팅방 - 프로그래머스 (Java, Level 2)

 

처음 풀이

 

닉네임이 변경될 때마다 이전 로그기록을 수정해야한다.

따라서 어떤 유저인지에 대한 메시지인지 1차로 기록하고, 기록이 다 끝난 후 최종 닉네임으로 바꿔준다.

1차 기록은 {유저 아이디, 입장/퇴장 메시지} 형태로 List<String[]>에 저장

닉네임 기록은 변경될 때마다 기존 값을 덮어써야 하니까 Map<String, String> (key : 유저아이디, value : 닉네임)에 저장

 

import java.util.*;

class Solution {
    final String ENTER_MSG = "님이 들어왔습니다.";
    final String LEAVE_MSG = "님이 나갔습니다.";

    //중간 결과물 담을 List ({유저아이디, ENTER_MSG or LEAVE_MSG})
    //순서대로 결과 출력해야하니까 Queue 자료구조
    List<String[]> list;
    //<key : 아이디, value : 닉네임> 담을 맵
    //바뀔 때마다 업데이트
    Map<String, String> userIdNicknameMap;

    public String[] solution(String[] record) {

        list = new LinkedList<>();
        userIdNicknameMap = new HashMap<>();

        //유저 아이디 + 메시지로 list에 담은 1차 결과
        //닉네임은 계속 바뀌니까 분리해서 따로 map에서 업데이트
        //마지막으로 list의 유저 아이디를 map의 닉네임으로 변경하여 출력
        
        StringTokenizer st;
        String type;
        String uId;
        for(String info : record) {
            st = new StringTokenizer(info);
            type = st.nextToken();
            uId = st.nextToken();
            if(type.equals("Enter")) {
                //Enter
                //1. MSG 생성
                //2. 닉네임 업데이트
                list.add(new String[]{uId, ENTER_MSG});
                userIdNicknameMap.put(uId, st.nextToken());
            } else if(type.equals("Leave")) {
                //Leave
                //MSG 생성
                list.add(new String[]{uId, LEAVE_MSG});
            } else {
                //Change
                //닉네임 업데이트
                userIdNicknameMap.put(uId, st.nextToken());
            }//if~else end
        }//for end

        //queue 사이즈 = 정답 배열 사이즈
        int msgSize = queue.size();
        String[] answer = new String[msgSize];

        String[] temp;
        String finalNickname;
        String finalMsg;
        //map을 이용해 list의 유저 아이디를 최종 nickname로 매핑
        for(int i=0; i<msgSize; i++) {
            temp = list.get(i);
            finalNickname = userIdNicknameMap.get(temp[0]);
            finalMsg = finalNickname+temp[1];
            answer[i] = finalMsg;
        }//for end
        
        return answer;
    }//solution() end
}

 

 

논리적인 흐름은 다 맞는 것 같은데 시간 초과가 났다.

 

개선된 풀이 1

 

1차 기록 List를 LinkedList가 아닌 ArrayList로 변경했다.

최종 nickname으로 매핑할 때 list.get(index)에서 ArrayList는 바로 접근이 가능하지만(random access),

LinkedList는 순차적인 접근(sequential access)만 가능하기 때문에 ArrayList의 속도가 더 빠르다.

LinkedList vs ArrayList

 

* 참고로 자바에서 LinkedList는 양방향 연결 리스트로 구현되어 있다.

 

list = new ArrayList<>();

 

 

테스트 25부터 시간이 오래 걸리고, ArrayList로 통과한 것을 보니,

아마도 메시지의 수가 급격하게 늘어 list의 사이즈가 커진 케이스가 아닌가 예상해본다.

 

 

개선된 풀이 2

 

List가 아닌 Queue에 1차 기록을 담았다.

기록된 순서대로 메시지가 출력되어야 하니까 FIFO인 Queue를 사용했다.

닉네임 매핑할 때 탐색할 필요없이 queue.poll() 하면 원하는 1차 기록을 얻을 수 있다.

 

Queue<String[]> queue;
    
public String[] solution(String[] record) {

    queue = new LinkedList<>();
   
   ...
 
    for(int i=0; i<msgSize; i++) {
        temp = queue.poll();
        
		...
        
    }//for end

    return answer;
}//solution() end