๐ ๋ฌธ์
์ ์
์ฌ์ ๋ฌด์ง๋ ๊ฒ์ํ ๋ถ๋ ์ด์ฉ์๋ฅผ ์ ๊ณ ํ๊ณ ์ฒ๋ฆฌ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ์ผ๋ก ๋ฐ์กํ๋ ์์คํ
์ ๊ฐ๋ฐํ๋ ค ํฉ๋๋ค. ๋ฌด์ง๊ฐ ๊ฐ๋ฐํ๋ ค๋ ์์คํ
์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
๊ฐ ์ ์ ๋ ํ ๋ฒ์ ํ ๋ช
์ ์ ์ ๋ฅผ ์ ๊ณ ํ ์ ์์ต๋๋ค.
์ ๊ณ ํ์์ ์ ํ์ ์์ต๋๋ค. ์๋ก ๋ค๋ฅธ ์ ์ ๋ฅผ ๊ณ์ํด์ ์ ๊ณ ํ ์ ์์ต๋๋ค.
ํ ์ ์ ๋ฅผ ์ฌ๋ฌ ๋ฒ ์ ๊ณ ํ ์๋ ์์ง๋ง, ๋์ผํ ์ ์ ์ ๋ํ ์ ๊ณ ํ์๋ 1ํ๋ก ์ฒ๋ฆฌ๋ฉ๋๋ค.
k๋ฒ ์ด์ ์ ๊ณ ๋ ์ ์ ๋ ๊ฒ์ํ ์ด์ฉ์ด ์ ์ง๋๋ฉฐ, ํด๋น ์ ์ ๋ฅผ ์ ๊ณ ํ ๋ชจ๋ ์ ์ ์๊ฒ ์ ์ง ์ฌ์ค์ ๋ฉ์ผ๋ก ๋ฐ์กํฉ๋๋ค.
์ ์ ๊ฐ ์ ๊ณ ํ ๋ชจ๋ ๋ด์ฉ์ ์ทจํฉํ์ฌ ๋ง์ง๋ง์ ํ๊บผ๋ฒ์ ๊ฒ์ํ ์ด์ฉ ์ ์ง๋ฅผ ์ํค๋ฉด์ ์ ์ง ๋ฉ์ผ์ ๋ฐ์กํฉ๋๋ค.
๋ค์์ ์ ์ฒด ์ ์ ๋ชฉ๋ก์ด ["muzi", "frodo", "apeach", "neo"]์ด๊ณ , k = 2(์ฆ, 2๋ฒ ์ด์ ์ ๊ณ ๋นํ๋ฉด ์ด์ฉ ์ ์ง)์ธ ๊ฒฝ์ฐ์ ์์์
๋๋ค.
์ ์ ID ์ ์ ๊ฐ ์ ๊ณ ํ ID ์ค๋ช
"muzi" "frodo" "muzi"๊ฐ "frodo"๋ฅผ ์ ๊ณ ํ์ต๋๋ค.
"apeach" "frodo" "apeach"๊ฐ "frodo"๋ฅผ ์ ๊ณ ํ์ต๋๋ค.
"frodo" "neo" "frodo"๊ฐ "neo"๋ฅผ ์ ๊ณ ํ์ต๋๋ค.
"muzi" "neo" "muzi"๊ฐ "neo"๋ฅผ ์ ๊ณ ํ์ต๋๋ค.
"apeach" "muzi" "apeach"๊ฐ "muzi"๋ฅผ ์ ๊ณ ํ์ต๋๋ค.
๊ฐ ์ ์ ๋ณ๋ก ์ ๊ณ ๋นํ ํ์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ ์ ID ์ ๊ณ ๋นํ ํ์
"muzi" 1
"frodo" 2
"apeach" 0
"neo" 2
์ ์์์์๋ 2๋ฒ ์ด์ ์ ๊ณ ๋นํ "frodo"์ "neo"์ ๊ฒ์ํ ์ด์ฉ์ด ์ ์ง๋ฉ๋๋ค. ์ด๋, ๊ฐ ์ ์ ๋ณ๋ก ์ ๊ณ ํ ์์ด๋์ ์ ์ง๋ ์์ด๋๋ฅผ ์ ๋ฆฌํ๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ ์ ID ์ ์ ๊ฐ ์ ๊ณ ํ ID ์ ์ง๋ ID
"muzi" ["frodo", "neo"] ["frodo", "neo"]
"frodo" ["neo"] ["neo"]
"apeach" ["muzi", "frodo"] ["frodo"]
"neo" ์์ ์์
๋ฐ๋ผ์ "muzi"๋ ์ฒ๋ฆฌ ๊ฒฐ๊ณผ ๋ฉ์ผ์ 2ํ, "frodo"์ "apeach"๋ ๊ฐ๊ฐ ์ฒ๋ฆฌ ๊ฒฐ๊ณผ ๋ฉ์ผ์ 1ํ ๋ฐ๊ฒ ๋ฉ๋๋ค.
์ด์ฉ์์ ID๊ฐ ๋ด๊ธด ๋ฌธ์์ด ๋ฐฐ์ด id_list, ๊ฐ ์ด์ฉ์๊ฐ ์ ๊ณ ํ ์ด์ฉ์์ ID ์ ๋ณด๊ฐ ๋ด๊ธด ๋ฌธ์์ด ๋ฐฐ์ด report, ์ ์ง ๊ธฐ์ค์ด ๋๋ ์ ๊ณ ํ์ k๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๊ฐ ์ ์ ๋ณ๋ก ์ฒ๋ฆฌ ๊ฒฐ๊ณผ ๋ฉ์ผ์ ๋ฐ์ ํ์๋ฅผ ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๐ ์ ํ์ฌํญ
- 2 ≤ id_list์ ๊ธธ์ด ≤ 1,000
- 1 ≤ id_list์ ์์ ๊ธธ์ด ≤ 10
- id_list์ ์์๋ ์ด์ฉ์์ id๋ฅผ ๋ํ๋ด๋ ๋ฌธ์์ด์ด๋ฉฐ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- id_list์๋ ๊ฐ์ ์์ด๋๊ฐ ์ค๋ณตํด์ ๋ค์ด์์ง ์์ต๋๋ค.
- 1 ≤ report์ ๊ธธ์ด ≤ 200,000
- 3 ≤ report์ ์์ ๊ธธ์ด ≤ 21
- report์ ์์๋ "์ด์ฉ์id ์ ๊ณ ํid"ํํ์ ๋ฌธ์์ด์ ๋๋ค.
- ์๋ฅผ ๋ค์ด "muzi frodo"์ ๊ฒฝ์ฐ "muzi"๊ฐ "frodo"๋ฅผ ์ ๊ณ ํ๋ค๋ ์๋ฏธ์ ๋๋ค.
- id๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ์ด์ฉ์id์ ์ ๊ณ ํid๋ ๊ณต๋ฐฑ(์คํ์ด์ค)ํ๋๋ก ๊ตฌ๋ถ๋์ด ์์ต๋๋ค.
- ์๊ธฐ ์์ ์ ์ ๊ณ ํ๋ ๊ฒฝ์ฐ๋ ์์ต๋๋ค.
- 1 ≤ k ≤ 200, k๋ ์์ฐ์์ ๋๋ค.
- return ํ๋ ๋ฐฐ์ด์ id_list์ ๋ด๊ธด id ์์๋๋ก ๊ฐ ์ ์ ๊ฐ ๋ฐ์ ๊ฒฐ๊ณผ ๋ฉ์ผ ์๋ฅผ ๋ด์ผ๋ฉด ๋ฉ๋๋ค.
๐ ์ ์ถ๋ ฅ ์
id_list report k result
["muzi", "frodo", "apeach", "neo"] ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"] 2 [2,1,1,0]
["con", "ryan"] ["ryan con", "ryan con", "ryan con", "ryan con"] 3 [0,0]
๐ ์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์ ์ ์์์ ๊ฐ์ต๋๋ค.
์
์ถ๋ ฅ ์ #2
"ryan"์ด "con"์ 4๋ฒ ์ ๊ณ ํ์ผ๋, ์ฃผ์ด์ง ์กฐ๊ฑด์ ๋ฐ๋ผ ํ ์ ์ ๊ฐ ๊ฐ์ ์ ์ ๋ฅผ ์ฌ๋ฌ ๋ฒ ์ ๊ณ ํ ๊ฒฝ์ฐ๋ ์ ๊ณ ํ์ 1ํ๋ก ์ฒ๋ฆฌํฉ๋๋ค. ๋ฐ๋ผ์ "con"์ 1ํ ์ ๊ณ ๋นํ์ต๋๋ค. 3๋ฒ ์ด์ ์ ๊ณ ๋นํ ์ด์ฉ์๋ ์์ผ๋ฉฐ, "con"๊ณผ "ryan"์ ๊ฒฐ๊ณผ ๋ฉ์ผ์ ๋ฐ์ง ์์ต๋๋ค. ๋ฐ๋ผ์ [0, 0]์ return ํฉ๋๋ค.
๐ง ํ์ด
/*
[0, 1, 0, 1]
[0, 0, 0, 1]
[1, 1, 0, 0]
[0, 0, 0, 0]
*/
function solution(id_list, report, k) {
let id_object = {}
let counts = new Array(id_list.length).fill().map(() => new Array(id_list.length).fill(0));
let reported = [];
let answer = [];
id_list.forEach((el, i) => {
id_object[el] = i;
})
report.forEach((el) => {
let temp = el.split(" ");
if ( counts[id_object[temp[0]]][id_object[temp[1]]] == 0) {
counts[id_object[temp[0]]][id_object[temp[1]]] += 1;
}
})
for (let i = 0; i < id_list.length; i++) {
let temp_val = 0;
for (let j = 0; j < id_list.length; j++) {
temp_val += counts[j][i];
}
if (temp_val >= k) {
reported.push(i);
}
}
for (let k = 0; k < id_list.length; k++) {
let temp_answer = 0;
reported.forEach((e) => {
if (counts[k][e] == 1) {
temp_answer += 1;
}
})
answer.push(temp_answer);
}
return answer;
}
๐ก ์๊ฒ ๋ ์
- ์ค๋ณต์ ์ ๊ฑฐํ ๋, Set์ ํ์ฉํด์ ์ค๋ณต์ ์ ๊ฑฐํ ๊ฒ์ ๋ง์ด ํ์ธํ ์ ์์๋ค.
- ๋ณธ์ธ์ 0์ผ ๋๋ผ๋ ์กฐ๊ฑด์ ๋ฌ์, ์ต์ด ์ ๊ณ ๋ง ์ ์ํ ์ ์๋๋ก ํ๋ค.
- reported ๋ฐฐ์ด์ ์ ๊ณ ๋ ์ฌ๋๋ค์ ์ธ๋ฑ์ค๋ฅผ ๋ด์ ์ ์๊ฒ ํ๊ณ ,
- answer ๋ฐฐ์ด์ ๋ฉ์ผ์ ๋ฐ์ ์ฌ๋๋ค์ ์ธ๋ฑ์ค์ ๋ง๊ฒ ํ์๋ฅผ ๋ด์ ์ ์๋๋ก ํ๋ค.