문제
input & output
| record | result |
|---|---|
| ["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"] | ["Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."] |
Approach #1
// 5:27~
/*
Muzi in v
Prodo in
Muzi out v
---> Muzi 다시 들어오는데, Prodo로 이름 바꾸고 다시 들어옴
--->
Prodo in
Prodo in v
Prodo out
Prodo in
----> 두번째 prodo가 현재 채팅방에서 이름 Ryan으로 변경
Prodo in
Ryan in v
Prodo out
Prodo in
3)constraints
- 모든 유저는 [유저아이디] 로 구분
- Enter [유저아이디] [닉네임]
- Leave [유저아이디] [닉네임]
- Change [유저아이디] [닉네임]
["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"]
Prodo 들어옴(1234)
Ryan 들어옴(4567)
Prodo 나감(1234)
Prodo 들어옴(1234)
4. edge
*솔루션
1. record[i]를 받아서 공백기준으로 쪼갠 배열 만듬.
curRecord = record[i];
[action, user_id, nickname] = curRecord.split(" ");
newRecord = [[Enter, uid1234, Muzi], ...]
2. newRecord의 user_id, nickname 보면서 map 만든다.
uid1234: Muzi
uid4567: Prodo
...
3. 다음 record를 받아서 공백기준으로 쪼갤때는, result에 넣을때 action을 확인하고 넣는다.
if(action === "Enter"){
//나갔다 들어온 사용자인지 확인한다.
//나갔다 들어온 사용자면 기존 record의 기록을 바꿔준다.
if(record[i][1]===user_id) record[i][2]=nickname;
//새로운 사용자면 그냥 push
}
//Leave일때
그냥 푸시.
//change일때
푸시하지 않고 if(record[i][1]===user_id) record[i][2]=nickname;
result = [["Enter", "uid1234", "Muzi"], [Enter, uid4567, Prodo], [Leave uid1234 prodo]]
*/Solution #1
function solution(record) {
var answer = [];
let newRecord = [];
let action, user_id, nickname;
for(let i=0; i<record.length; i++){
let recordArr = record[i].split(" ");
newRecord.push(recordArr);
}
// id : nickmane 맵 구성
const id_map = new Map();
for(let i=0; i<newRecord.length; i++){
if(newRecord[i][0]==="Leave") continue;
user_id = newRecord[i][1];
nickname = newRecord[i][2];
id_map.set(user_id, nickname);
}
for(let i=0; i<newRecord.length; i++){
action = newRecord[i][0];
user_id = newRecord[i][1];
if(newRecord[i][2]) nickname = newRecord[i][2];
if(action === "Enter" || action === "Change"){
newRecord[i][2] = id_map.get(newRecord[i][1]);
}
else if(action === "Leave"){
newRecord[i].push(id_map.get(newRecord[i][1]));
}
}
//console.log(newRecord)
for(let i=0; i<newRecord.length; i++){
let action = newRecord[i][0];
let user_id = newRecord[i][1];
let nickname = newRecord[i][2];
if(action === "Enter") answer.push(nickname + "님이 들어왔습니다.");
else if(action === "Leave") answer.push(nickname + "님이 나갔습니다.");
else if(action === "Change") continue;
}
return answer;
}N: record.length
M: id_map.size
Time Complexity
O(N) + O(N)
newRecord 만드는 for문: O(N)
- record 길이만큼 반복하니까 N, split할때 record[i] 스트링 길이만큼 반복될것.
- 문제에서 명령어(Enter,Leave,Change)+유저아이디(최대길이 10)+닉네임(최대길이 10) 이므로 record[i] 스트링은 아무리 길어봐야 28(Change 길이 6+공백+유저아이디 길이 10+공백+닉네임 길이 10)일것이다. 따라서 상수값.
id_map 만드는 for문: O(N)
- newRecord 길이만큼 for문 돌며 map에 셋해주기 때문.
map의 key,value 확인하며 nickname 갱신해주는 for문: O(N)
- newRecord 길이만큼 for문 돌며 바뀐 nickname 갱신해주기 때문.
최종 answer배열 만드는 for문: O(N)
- newRecord 길이만큼 for문 돌며 answer 배열에 push 해주기 때문.
=> O(N)+O(N)+O(N)+O(N) = O(4N)
=> O(N)
Space Complexity
O(N) + O(M)
answer 배열: O(N)
- worst case여도 N보다는 작을 것.
newRecord 배열: O(N)
- record 배열의 길이와 같음.
id_map 맵: O(M)
- key값은 record 배열에 있는 nickname의 수. N보다는 작을것이다. (M으로 표현하였음)
=> O(2N) + O(M)
=> O(N) + O(M)
Review
-
처음 코드 완성까지는 30분정도 걸렸으나.... 테스트케이스 통과를 못해서 이것저것 수정하고... 결국 원인을 모르겠어서 질문하기 들어가서 살짝 참고했다. (이유는 타임리밋..) 그래서 찐 통과까지는 1시간 10분정도 걸림. 아이고오....
-
처음 approach 에서는 nickname을 갱신해줄때 맵을 만들지않고 이전 기록들을 for문으로 전부 조회하며 바꿔줬었는데, 이 부분에서 시간제한이 생긴것 같다.
시간 제한 해결: id_map 만들어줌.
- [key: 유저아이디 value: 닉네임]인 맵을 만들때, 이미 있는 key값에 또 set을 해줄경우 마지막으로 set한 value로 설정되기 때문에 최종맵이 우리가 원하는 유저아이디-닉네임 맵일 것이다.
- newRecord에 nickname을 갱신해줄때 해당 유저아이디를 key로 갖는 value값으로 갱신해주면 되기 때문에 이전보다 시간복잡도가 훨씬 단축됨.(N^2에서 N*M으로)
- input으로 들어오는 record가 Leave일때는 nickname이 없고 user_id만 있어서, 위의 로직대로라면 이전 nickname을 참조하기 때문에 nickname 갱신해줄때 명령이 Leave이면 nickname을 push해주어 해결했다.
TIL
- 공백 기준으로 자르기 => split 함수 이용할것.
- 시간복잡도 줄이기 위해 map 사용한점.
- 산발적 for문 사용 자제하자....
성장하는 developer