오픈채팅방
풀이
- filter를 한번 더 수행하는 것이 맘에 들지 않는다.
function solution(record){
const user = {}
record.forEach((interaction)=>{
const [action,id,name] = interaction.split(" ")
if(action === 'Enter' || action === 'Change'){
user[id] = name;
}
})
return record.map((interaction)=>{
const [action,id,name] = interaction.split(" ")
if(action === 'Enter'){
return `${user[id]}님이 들어왔습니다.`
}
if(action === 'Leave'){
return `${user[id]}님이 나갔습니다.`
}
return '$'
}).filter(item=>item !== '$')
}또다른 풀이
forEach로 돌면서 Change를 제외한 액션들은 -> id 값과 텍스트를 담아 저장한다.
다 저장되면 이를 map으로 정답 형식에 맞게 mutate하여 내보낸다.
function solution(record){
const user = {};
const answer = []
record.forEach(r=>{
const [action,id,name] = r.split(" ");
if(action === 'Enter'){
answer.push([id,'님이 들어왔습니다.']);
}
if(action === 'Leave'){
answer.push([id,'님이 나갔습니다.']);
}
if(name) user[id] = name;
})
return answer.map(([id,text])=>`${user[id]}${text}`)
}record -> 1~100000 이라는 점을 볼때, O(n^2)의 방법은 적합하지않다.
메뉴 리뉴얼
course -> 1~10 숫자배열
orders -> 2~20 문자열배열
order -> 2~10 문자열
풀이
8번 기준 22.73ms
function getCombination(array,r){
const combinations = []
function DFS(combination,idx,depth){
if(depth === r){
combinations.push(combination)
return;
}
for(let i=idx+1;i<array.length;i++){
DFS([...combination,array[i]],i,depth+1);
}
}
DFS([],-1,0);
return combinations;
}
function solution(orders,course){
let newAnswer = []
course.forEach(number=>{
// 코스요리 갯수
const answer = {}
let max = 0;
orders.forEach(order=>{
// 손님이 주문한 요리
const menuCombinations = getCombination(order.split(""),number);
for(const menus of menuCombinations){
const count = orders.filter(order=>{
// 메뉴의 모든 원소가 order에 들어있는 것들만 살리기
return menus.every((menu)=>order.includes(menu))
}).length;
if(count>=2){
answer[count] = answer[count] ? [...answer[count],menus.sort().join("")] : [menus.sort().join("")]
if(max < count){
max = count;
}
}
}
})
if(answer[max]){
newAnswer = newAnswer.concat([...new Set(answer[max])])
}
})
return newAnswer.sort();
}리팩토링
- 캐시 기능을 추가해서, 이미 계산했던 조합의 메뉴이면 넘어가도록 구현하였다. 8번 테스트케이스 기준 11ms 걸림
function getCombination(cache,array,r){
const combinations = []
function DFS(combination,idx,depth){
if(depth === r){
const key = combination.sort().join("");
if(!cache[key]){
cache[key] = true;
combinations.push(combination)
}
return;
}
for(let i=idx+1;i<array.length;i++){
DFS([...combination,array[i]],i,depth+1);
}
}
DFS([],-1,0);
return combinations;
}
function solution(orders,course){
let newAnswer = []
const cache = {};
course.forEach(number=>{
// 코스요리 갯수
const answer = {}
let max = 0;
orders.forEach(order=>{
// 손님이 주문한 요리
const menuCombinations = getCombination(cache,order.split(""),number);
for(const menus of menuCombinations){
// menu들이 모두 손님 주문에 포함된다면 살린다.
const menusString = menus.join("")
const count = orders.filter(order=> menus.every((menu)=>order.includes(menu))).length;
if(count>=2){
answer[count] = answer[count] ? [...answer[count],menusString] : [menusString] // 11ms
// answer[count] = answer[count] ? answer[count].concat(menusString) : [menusString] -> concat이 더 느리다. 13ms걸림
max = Math.max(max,count);
}
}
})
newAnswer = answer[max] ? newAnswer.concat(answer[max]) : newAnswer;
})
return newAnswer.sort();
}아래과정은 필요하지므로
// 아래 과정은 필요하지 않다. 손님들의 조합들 중 중복되는 메뉴들이 몇개인지를 보면된다.
orders.forEach(order=>{
// 손님이 주문한 요리
const menuCombinations = getCombination(cache,order.split(""),number);
for(const menus of menuCombinations){
// menu들이 모두 손님 주문에 포함된다면 살린다.
const menusString = menus.join("")
const count = orders.filter(order=> menus.every((menu)=>order.includes(menu))).length;
if(count>=2){
answer[count] = answer[count] ? [...answer[count],menusString] : [menusString] // 11ms
// answer[count] = answer[count] ? answer[count].concat(menusString) : [menusString] -> concat이 더 느리다. 13ms걸림
max = Math.max(max,count);
}
}
})다음 풀이로 수정!
다른 풀이
function getCombination(object,array,r){
const combinations = []
function DFS(combination,idx,depth){
if(depth === r){
// 조합을 key로 하고 몇번이나 등장하는지 확인한다.
const key = combination.sort().join("")
object[key] = object[key] ? object[key] + 1 : 1;
return;
}
for(let i=idx+1;i<array.length;i++){
DFS([...combination,array[i]],i,depth+1);
}
}
DFS([],-1,0);
}
function solution(orders,course){
let answer = [];
course.forEach(num=>{
const object = {}
orders.forEach(order=>{
getCombination(object,order.split(""),num);
})
const max = Math.max(...Object.values(object));
if(max >= 2){
answer = answer.concat(Object.keys(object).filter((key)=>object[key] === max))
}
})
return answer.sort();
}다음과 같이 수정한다.
올바른 괄호
그냥 시키는거만 하면된다.
스택 자료구조를 활용하여 올바른 괄호인지, 균형잡힌 괄호인지를 판별한다.
function getUV(p){
let stack = []
let index = 0;
let left = 0;
let right = 0;
for(;index<p.length;index++){
if(p[index] === '('){
stack.push('(')
left++;
}else{
stack.pop();
right++;
}
if(left === right){
break;
}
}
return [p.slice(0,index+1),p.slice(index+1),stack.length === 0];
}
function solution(p){
if(p === '') return p;
const [u,v,flag] = getUV(p);
if(flag){
return u + solution(v);
}else{
return `(${solution(v)})${u.slice(1,u.length-1).split("").map((c)=>c===')' ? '(' : ')').join("")}`
}
}Ref
- 자바스크립트 배열의 시간 복잡도 정리 https://kimyejin.tistory.com/m/62
Frontend Ninja