-
문제
https://www.acmicpc.net/problem/1713
How to Solve ?
1) N개의 사진을 걸 수 있는 자리가 존재한다.
2) 비어 있으면 사진에 추천인의 사진을 건다.
배열을 만들어, N보다 크면 업데이트를 하지 않았다.
3) 사진이 걸려 있을 때, 추천을 받으면 추천 수가 증가한다.
이미 배열 안에 있으면 당사자의 추천 수를 올려준다.
4) 추천 수가 더 높거나 같은 추천인이 오면 가장 오래된 사진을 떼고, 새로 올린다.
이 부분을 처리하는데 시간이 꽤 걸렸는데, 들어 오는 사람들의 추천수는 1이기에 모두 1로 설정 해주었고,
사진관에 올라간 모든 배열의 값도 [ idx, count ] 를 모두 담은 배열로 변경 해주었다.
5) 만약 새로운 추천인이 오더라도 추천수가 기존의 사진들보다 작으면 교체 X
배열의 1번째 자리를 비교하여 작으면 교체를 하지 않았다.
전체 코드
function solve() { const answer = []; // 사진이 걸릴 수 있는 공간 const photo_zone = []; // 기본 추천수가 1이기 때문에, 이를 기준으로 배열을 다시 만듬 const retouched = []; for (let i = 0; i < people_count; i++) { retouched.push([recommends[i], 1]); } for (let i = 0; i < people_count; i++) { // 포토존에 자리가 남아 있을 때 if (photo_zone.length <= n - 1) { photo_zone.push(retouched[i]); } // 포토존에 이미 사진이 꽉 찼을 때, else { // 포토존에 이미 추천자가 걸려있다면 if (photo_zone[0].indexOf(retouched[i][0]) !== -1) { const idx = photo_zone[0].indexOf(retouched[i][0]); photo_zone[idx][1] += 1; } // 포토존에 사진도 꽉 차있고, 추천자의 사진이 없다면 => 삭제를 해야한다. else { for (let j = 0; j < photo_zone.length; j++) { // 만약 포토존의 추천 수 중에서, 들어 오려는 사람의 추천수보다 낮은 경우가 있을 때 if (photo_zone[j][1] <= retouched[i][1]) { // 이미 사진이 걸려있다면, 패스 if ( photo_zone .map((each) => each[0] === retouched[i][0]) .includes(true) ) { continue; } // 그렇지 않으면 사진을 걸어준다. photo_zone.splice(j, 1); photo_zone.push(retouched[i]); break; } } } } } // 사진을 순서대로 정렬하고, 앞자리만 answer 배열에 보내고. photo_zone.sort((a, b) => a[0] - b[0]); photo_zone.forEach((each) => answer.push(each[0])); // 간격을 주어 출력한다. console.log(answer.join(" ")); } const n = 3; const people_count = 9; const recommends = [2, 1, 4, 3, 5, 6, 2, 7, 2]; solve();
'PS > 백준' 카테고리의 다른 글
[ 백준 - 2659 ] 십자카드 문제 ( 완전탐색 - 자바스크립트 ) (0) 2021.06.27 [ 백준_16953 ] A -> B ( d/bfs - 자바스크립트 ) (0) 2021.06.25 [백준_20365] 블로그2 ( 그리디 - 자바스크립트 ) (0) 2021.06.17 [백준_10971] 외판원 순회2 ( 브루트포스 - 완전탐색 ) (0) 2021.06.16 [백준-10819] 차이를 최대로 ( 브루트포스 - 자바스크립트 ) (0) 2021.06.16 댓글