문제
월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.
학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.
입력
첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.
사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.
예제 입력 1
3
9
2 1 4 3 5 6 2 7 2
출력
2 6 7
나의 풀이
무슨 말인지 다들 이해했으면 ... 좋..겠다!
코드
function solution(frame, n , arr){
let stack= []
let cnt = 0
let cursor = [] //체크배열
let count = parseInt(n/frame)
for ( let j = 0 ; j < count; j ++){
for ( let i = 0; i < n ; i ++){
let peo = Number(arr[i])
if( stack.length <3){
stack.push(peo)
cursor.push(cnt++) //액자 개수만큼 돌았다
}
else{ //똑같은게 있으면
if(stack.some(item => item === peo)){
stack[stack.indexOf(peo)] = peo //해당 아이템있는 자리에 덮어씌움
cursor[stack.indexOf(peo)] = cnt++ //cnt도 해당아이템이 있는 인덱스에 덮어씌움
}else{
//만약 똑같은게 없으면
let min = Math.min(...cursor) //cnt가 젤 작은 곳
stack[cursor.indexOf(min)] = peo //cnt가 젤 작은 곳에 추가함
cursor[cursor.indexOf(min)] =cnt++ //cnt도 같이 덮어씌움
}
}
}
}
console.log(stack.sort((a,b)=> a-b))
}
console.log(solution(frame, n , arr))
풀이
주석을 최대한 꼼꼼히 달아놨는데.. 이해가 쉬웠으면 좋겠다!
사람 수를 액자 수 만큼 자른다 (예시에서는 9/3씩 액자에 넣을 것임)
일단 stack 이라는 배열에 3개를 순서대로 다 넣는다
동시에 cnt 라는 카운트를 cursor 배열에 stack배열과 똑같은 순서로 넣는다
그러면 세번씩 넣는 과정중 첫번째를 넣은 거 겠죠??
그리고 두번째 넣는 과정을 들어가는데
만약 전에 똑같은 후보가 이미 액자에 있으면 덮어 씌우고
똑같은 사람이 없으면 그냥 제일 오래된 순(cnt가 적은쪽)으로 넣어주면 된다
여기서 some()함수를 사용했는데
stack.some(item => item === peo )
stack 배열안에 item 이 peo와 같을 경우 라고 조건을 걸어줄 수 있다
만약 참이라면 ( 이미 후보가 액자에 있을 경우 )
stack의 peo가 있는 인덱스에 그대로 덮어씌워서 저장해주고
하지만 cursor 에는 cnt를 +1 증가하여 똑같은 인덱스에 저장한다
(그래야 최신순이라는 걸 나타낼 수 있음 )
만약 똑같은 게 없다면
cursor안에 있는 cnt가 가장 작은 곳이 제일 예전 후보이기 때문에
cnt의 최소값을 구하고
그 최소값이 있는 인덱스에
peo와 cursor를 넣는다
시간 복잡도도 2초 안에 뜬다!
끝~~~
