[ALGO] 프로그래머스 - 오픈채팅방(자바스크립트, javascript)

hj·2021년 6월 9일
0

알고리즘

목록 보기
18/35
post-thumbnail

프로그래머스 - 오픈채팅방

풀이

전체 로직

record 배열을 순회하면서 uid, nickname을 따로 저장해두고, answer 배열에는 uid나갔습니다. or 들어왔습니다.를 저장해둔다. 마지막으로 answer을 순회하면서 uidnickname으로 바꾼다.

내풀이 - 1차 (2/32) (2021.06.09)

테스트케이스 2개만 통과하고 나머지는 런타임 에러와 시간초과가 떴다.

uid와 nickname 객체를 dic 배열에 저장한다. 배열 안에 객체를 만들어서 이를 탐색?하는데 시간이 많이 소요되는 것 같은 느낌..?

uid와 nickname 따로 저장할 때

  • Enter인 경우: dic 배열에 uid가 존재하지 않으면 값을 push한다.
  • Leave인 경우(들어갔다 다시 들어오면 닉네임을 바꿀 수 있다.): dic 배열에서 해당 uid를 제거해준다. (틀림: 나갔다가 다시 들어온 경우는 nickname 존재하지만 다시 들어오지 않았다면 nickname 없음,,)
  • Change인 경우: dic 배열에서 해당 uid의 nickname 변경해준다.
function solution(record) {
    let answer = [];
    let dic = [];
    
    for (let i in record) {
        let temp = record[i].split(' ');
        
        if (temp[0] === 'Enter') {
            answer.push(temp[1] + ' 들어왔습니다.');
            
            let filtered = dic.filter(e => e.uid === temp[1]);
            
            if (filtered.length === 0) {
                dic.push({
                    uid: temp[1],
                    nickname: temp[2],
                });
            }
            
            
        } else if (temp[0] === 'Leave') {
            answer.push(temp[1] + ' 나갔습니다.');
            dic = dic.filter(e => e.uid !== temp[1]);
        } else {
            dic.map(e => {
                if (e.uid === temp[1]) {
                    return e.nickname = temp[2];
                }
            });
        }
    }
    
    for (let i in answer) {
        let tmp = answer[i].split(' ');
        let filtered = dic.filter(e => e.uid === tmp[0]);
        
        answer[i] = filtered[0].nickname  + '님이 ' + tmp[1];
    }
    return answer;
}

내풀이 - 2차 (24/32) (2021.06.09)

나머지는 시간초과

uidnickname을 따로 저장할 때

  • Enter인 경우: dic 배열에 uid가 존재하지 않으면 값을 push한다. 이미 존재한다면 바꾼다.
  • Leave인 경우
  • Change인 경우: dic 배열에서 해당 uidnickname을 변경해준다.
function solution(record) {
    let answer = [];
    let dic = [];
    
    for (let i in record) {
        let temp = record[i].split(' ');
        
        if (temp[0] === 'Enter') {
            answer.push(temp[1] + ' 들어왔습니다.');
            
            let filtered = dic.filter(e => e.uid === temp[1]);
            
            if (filtered.length === 0) {
                dic.push({
                    uid: temp[1],
                    nickname: temp[2],
                });
            }
            
            else {
                for (let i in dic) {
                    if (dic[i].uid === temp[1]) {
                        dic[i].nickname = temp[2];
                    }
                }
            }
            
        } else if (temp[0] === 'Leave') {
            answer.push(temp[1] + ' 나갔습니다.');
        } else {
            dic.map(e => {
                if (e.uid === temp[1]) {
                    return e.nickname = temp[2];
                }
            });
        }
    }
    
    for (let i in answer) {
        let tmp = answer[i].split(' ');
        let filtered = dic.filter(e => e.uid === tmp[0]);
        
        answer[i] = filtered[0].nickname  + '님이 ' + tmp[1];
    }
    return answer;
}
function solution(record) {
    let answer = [];
    let dic = [];
    
    let flag = 0;
    
    for (let i in record) {
        let temp = record[i].split(' ');
        
        if (temp[0][0] === 'E') {
            answer.push(temp[1] + ' 들어왔습니다.');
            
            let filtered = dic.filter(e => e.uid === temp[1]);
            
            if (filtered.length === 0) {
                dic.push({
                    uid: temp[1],
                    nickname: temp[2],
                });
            }
            
            else {
                for (let i in dic) {
                    if (dic[i].uid === temp[1]) {
                        dic[i].nickname = temp[2];
                    }
                }
            }
            
        } else if (temp[0][0] === 'L') {
            answer.push(temp[1] + ' 나갔습니다.');
        } else {
            for (let i in dic) {
                if (dic[i].uid === temp[1]) {
                    dic[i].nickname = temp[2];
                    break;
                }
            }
        }
    }
    
    for (let i in answer) {
        let tmp = answer[i].split(' ');
        for (let j in dic) {
            if (dic[j].uid === tmp[0]) {
                answer[i] = dic[j].nickname + '님이 ' + tmp[1];
                break;
            }
        }
    }
    return answer;
}

시간초과가 나는 이유

찾아보니 25~30번에서 시간초과가 나는 이유는 nickname을 변경할 때(나갔다가 다시 들어올 때, change할 때) 모든 record를 순회하면서 해당 uidnickname을 바꿔서 시간 복잡도 O(n)이 추가로 들게 되어서이다. 총 O(n^2)이 되어서 시간 초과가 난다. 이를 해결하기 위해서 자바스크립트의 Map 자료구조를 이용했다.

문법

Map

  • 객체: 키가 있는 컬렉션을 저장한다.
  • 배열: 순서가 있는 컬렉션을 저장한다.

맵(Map): 키가 있는 데이터를 저장한다는 점에서 객체와 유사하다. Map은 키에 다양한 자료형을 허용한다. (객체를 키로 사용할 수 있다.)

  • new Map() – 맵을 만든다.
  • map.set(key, value) – key를 이용해 value를 저장한다.
  • map.get(key) – key에 해당하는 값을 반환한다. key가 존재하지 않으면 undefined를 반환한다.
  • map.has(key) – key가 존재하면 true, 존재하지 않으면 false를 반환한다.
  • map.delete(key) – key에 해당하는 값을 삭제한다.
  • map.clear() – 맵 안의 모든 요소를 제거한다.
  • map.size – 요소의 개수를 반환한다.

map[key]는 Map을 쓰는 올바른 방법이 아니다. 이렇게 사용할 수 있긴 하지만 이 방법은 map을 일반 객체처럼 취급하게 되고, 여러 제약이 생기게 된다. map을 사용할 땐 map 전용 메서드 set, get등을 사용하자.

맵의 요소에 반복 작업할 때 사용할 수 있는 메서드

  • map.keys() – 각 요소의 키를 모은 반복 가능한(iterable, 이터러블) 객체를 반환한다.
  • map.values() – 각 요소의 값을 모은 이터러블 객체를 반환한다.
  • map.entries() – 요소의 [키, 값]을 한 쌍으로 하는 이터러블 객체를 반환합니다. 이 이터러블 객체는 for..of반복문의 기초로 쓰인다.

내풀이 - 3차 (성공) (2021.06.09)

function solution(record) {
    let answer = [];
    let dic = [];
    
    let map = new Map();
    
    for (let i in record) {
        let temp = record[i].split(' ');
        
        if (temp[0][0] === 'E') {
            answer.push(temp[1] + ' 들어왔습니다.');
            
            map.set(temp[1], temp[2]);
            
        } else if (temp[0][0] === 'L') {
            answer.push(temp[1] + ' 나갔습니다.');
        } else {
            
            map.set(temp[1], temp[2]);
        }
    }
    
    for (let i in answer) {
        let tmp = answer[i].split(' ');
        answer[i] = map.get(tmp[0]) + '님이 ' + tmp[1];
    }
    return answer;
}

풀이 업데이트 (2021.07.02)

function solution(record) {
    let answer = [];
    let people = {};
    
    record.map((item, i) => {
        let tmp = item.split(' ');
        
        if (tmp[0] === 'Enter') {
            answer.push(tmp[1] + '  님이 들어왔습니다.');
            people[tmp[1]] = tmp[2];
            
        } else if (tmp[0] === 'Leave') {
            answer.push(tmp[1] + '  님이 나갔습니다.');
        } else {
            people[tmp[1]] = tmp[2];
        }
        
    });
    
    let result = [];
    answer.map(item => {
        let tmp = item.split('  ');
        result.push(people[tmp[0]] + tmp[1]);
    });
    
    return result;
}

풀이 업데이트 (2021.10.23)

function solution(record) {
    let nicknames = new Map();
    let result = [];
    
    record.map(rec => {
        const [command, uid, nickname] = rec.split(' ');
        
        if (command !== 'Leave') nicknames.set(uid, nickname);
            
        if (command === 'Enter') {
            result.push(`${uid} 님이 들어왔습니다.`);
        } else if (command === 'Leave') result.push(`${uid} 님이 나갔습니다.`);
    });
    
    return result.map(res => {
        const uid = res.split(' ')[0];
        const nickname = nicknames.get(uid);
        
        return res.replace(`${uid} `, nickname);
    });
    
}

reference

25~30번 시간초과 이유
Map 자료구조

0개의 댓글