[백준][JAVA] 1713 - 후보 추천하기 - 시뮬레이션

📌 문제

백준 | 후보 추천하기 | SILVER 1 | 시뮬레이션

https://www.acmicpc.net/problem/1713

 

 

📌 문제 탐색하기

• 학생회장 후보 = 일정기간동안 전체 학생의 추천 수
• 홈페이지 사진틀의 수 = 후보의 수
  • 모든 사진틀 empty
  • 어떤 학생 → 특정 학생 추천 : 추천받은 학생이 사진틀에 게시
  • 모두 full → 추천받은 횟수가 가장 적은 학생의 사진을 삭제 & 새롭게 추천받은 학생 게시 (OS 페이징 기법 중, LFU)
    • 만약, 2명 이상 = 게시된 지 가장 오래된 사진을 삭제(OS 페이징 기법중, LRU)
  • 게시된 학생이 다른 학생의 추천을 ‘또’ 받으면, 추천 횟수 +1
  • if 삭제되는 경우 = 추천횟수는 0으로 변경
• 출력 : 최종 후보 (제일 추천이 많은 후보)

example)

2 1 4 3 5 6 2 7 2

2 0 0

2 1 0

2 1 4

1 4 3

4 3 5

3 5 6

5 6 2

6 2 7

6 2 7 (받은 개수 : 1,2,1)

⇒ 출력 : 2, 6, 7 (오름차순으로 표현)

 

 

 

📌 알고리즘

• N ≤ 20
• 총 추천횟수 ≤1000
• 학생번호 ≤100

⇒ 20 * 1000 * 100 = 1초 이내로 가능할 듯!

• 객체를 먼저 만든다 (횟수 cnt, 사진에 등록된 시간(오래됨을 판별))
• 이를 바탕으로 PriorityQueue를 이용해서 매번 sorting을 진행해준다.

 

 

 

📌 시도 회차 수정 사항

🚀 1회차

• 런타임에러 발생
• 그도그럴것이… queue를 막상 사용해보니 너무 비효율적임
  • 매번 time을 +1해주는 것과 num을 찾아 돌리고 다시 넣어주는 것이 비효율적
  ⇒ cntPlus와 timePlus 메소드 변경 필요

import java.util.*;
import java.io.*;


public class q1713_silver1 {

    static PriorityQueue<Person> pq = new PriorityQueue<>((o1,o2) -> {
        if(o1.cnt != o2.cnt){
            return o1.cnt - o2.cnt;
        } else {
            return o2.time - o1.time;
        }
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int cnt = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<cnt; i++){
            int person = Integer.parseInt(st.nextToken());
            if(!cntPlus(person)) {
                if(pq.size() == n){
                    pq.poll();
                    pq.offer(new Person(person, 1, 0));
                } else {
                    pq.offer(new Person(person, 1, 0));
                }
            }
            timePlus();
        }


        List<Person> list = new ArrayList<>();
        while(!pq.isEmpty()){
            Person person = pq.poll();
            list.add(person);
        }

        Collections.sort(list, (o1, o2) -> o1.num - o2.num);

        for(Person p : list){
            System.out.print(p.num + " ");
        }
    }

    public static boolean cntPlus(int num){
        Queue<Person> queue = new LinkedList<>();
        boolean isCntChanged = false;
        while(!pq.isEmpty()){
            Person person = pq.poll();
            if(person.num == num){
                queue.offer(new Person(person.num, person.cnt+1, person.time));
                isCntChanged = true;
            } else {
                queue.offer(person);
            }
        }

        while(!queue.isEmpty()){
            pq.offer(queue.poll());
        }

        return isCntChanged;
    }

    public static void timePlus(){
        Queue<Person> queue = new LinkedList<>();
        while(!pq.isEmpty()){
            Person person = pq.poll();
            queue.offer(new Person(person.num, person.cnt, person.time+1));
        }

        while(!queue.isEmpty()){
            pq.offer(queue.poll());
        }
    }
}

class Person  {
    int num;
    int cnt;
    int time;

    public Person(int num, int cnt, int time){
        this.num = num;
        this.cnt = cnt;
        this.time = time;
    }
}

 

🚀 2회차 변경사항 

List<Person> tmpList = new ArrayList<>(pq);

=> PriorityQueue와 같은 Queue 구현체는 Collection 인터페이스를 상속하므로, 이를 ArrayList 같은 리스트로 변환 가능

public static boolean cntPlus(int num){
    boolean isCntChanged = false;
    List<Person> tmpList = new ArrayList<>(pq);
    pq.clear();
    for(Person person : tmpList){
        if(person.num == num){
            person.cnt +=1;
            isCntChanged = true;
        }
        pq.offer(person);
    }
    return isCntChanged;
}

public static void timePlus(){
    List<Person> tmpList = new ArrayList<>(pq);
    pq.clear();
    for(Person person : tmpList){
        person.time += 1;
        pq.offer(person);
    }
}

 

 

 

📌 정답 코드

import java.util.*;
import java.io.*;

public class Main{

    static PriorityQueue<Person> pq = new PriorityQueue<>((o1,o2) -> {
        if(o1.cnt != o2.cnt){
            return o1.cnt - o2.cnt; //추천횟수는 적을수록 삭제가능성 up
        } else { 
            return o2.time - o1.time; //시간은 오래될수록(클수록) 삭제가능성 up
        }
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int times = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<times; i++){
            int person = Integer.parseInt(st.nextToken());
            if(!cntPlus(person)) {
			            //number가 같은지 확인함 (같다면 시간만 +1, 다르다면 pq 크기에 따라 다르게)
                 if(pq.size() == n){
                     pq.poll();  
                 } 
                 pq.offer(new Person(person, 1, 0));
            }
            timePlus();
        }


        List<Person> list = new ArrayList<>(pq);

        Collections.sort(list, (o1, o2) -> o1.num - o2.num); //num 기준 오름차순으로 수행

        for(Person p : list){
            System.out.print(p.num + " ");
        }
    }

    public static boolean cntPlus(int num){
        boolean isCntChanged = false;
        List<Person> tmpList = new ArrayList<>(pq);
        pq.clear();
        for(Person person : tmpList){
            if(person.num == num){
                person.cnt +=1;
                isCntChanged = true;
            }
            pq.offer(person);
        }
        return isCntChanged;
    }

    public static void timePlus(){
        List<Person> tmpList = new ArrayList<>(pq);
        pq.clear();
        for(Person person : tmpList){
            person.time += 1;
            pq.offer(person);
        }
    }
}

class Person  {
    int num;
    int cnt;
    int time;

    public Person(int num, int cnt, int time){
        this.num = num;
        this.cnt = cnt;
        this.time = time;
    }
}

 

Silver1문제인데,, 생각보다 어렵게 푼 듯하다.

다른 분들 풀이 참고했을때는 LinkedHashMap으로 푸셨는데, 이부분도 추후 참고해서 다시 풀어봐야겠다.

또한, Queue를 바로 List로 변경할 수 있는지 알게되서 시간초과를 해결할 수 있었다. 앞으로도 차근차근 배워야지 ! 🍀