그리디 알고리즘을 사용했다
그리디의 조건이 뭘까 ? 를 가장 오래 고민했다.
그리디의 조건은 나는 이렇게 생각했다.
1. 만약 이번 전기용품이 이미 멀티탭에서 사용중이라면 그냥 그대로 둔다.
2. 앞으로 다시는 쓰지 않는 전기용품이 있다면 그 전기용품을 멀티탭에서 제거하고 새로운 전기용품을 꽂는다.
3. 현재 멀티탭에서 사용하고 있는 것들 중 앞으로 다시는 쓰지 않는 전기용품이 없다면 ( 전부 최소한 앞으로 1번 이상 사용할 것이라면 ) 지금의 시점으로부터 가장 늦게 사용될 예정일 전기용품을 제거하고 새로운 전기용품을 꽂는다.
2-3번을 진행했다면 count 를 증가
전체적으로 이전에 설명한 것과 같다.
1. 1~100까지의 전기용품이 등장하는 index를 알아야 한다. 예를 들어 예제입력처럼 2 3 2 3 1 2 7 이 들어왔다면 2는 0번째 인덱스, 2번째 인덱스, 5번째 인덱스에 등장한다. 이를 저장할 queue다.
2. 처음으로 멀티탭 구멍을 다 꽂아야 한다. 여기서 구멍의 개수 N개만큼 반복해주지 않는 이유가 있는데, 만약 입력이 최대 2개 까지 꽂을 수 있고 2 2 2 2 7 6 이라면 ? 그렇다면 앞의 2번을 2개 멀티탭에 꽂는게 되고 최종적으로 1개만 꽂는게 된다. 최대 갯수를 꽂아야 한다. 그렇기에 hashset의 size가 n개가 될 때 까지 멀티탭 구멍을 꽂아야 한다. 그렇게 해야 2 2 2 2 7 까지 했을 때 hashset의 size가 2가 된다. 이제 기본 셋팅이 끝난 것이다.
3. 그렇다면 그 다음 index 부터 탐색해야한다. 그래서 i를 한 번 ++ 시켜 주었다. 이제 그 다음에는 이전에 말한 그리디의 조건 3가지를 적용했다.
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int K=Integer.parseInt(st.nextToken());
// 1~100까지의 전기용품이 등장한 index를 저장할 queue.
Queue<Integer> [] queue=new LinkedList[101];
for(int i=1;i<=100;i++)
queue[i]=new LinkedList<>();
// 현재 작동하고 있는 전기용품의 번호를 나타낼 해시셋
HashSet<Integer> isMoving=new HashSet<>();
st=new StringTokenizer(br.readLine());
int arr[]=new int[K];
for(int i=0;i<K;i++) {
// 3번째 순서에 전기용품 7이 들어왔다면 queue[7].add(3) 을 한다.
arr[i]=Integer.parseInt(st.nextToken());
queue[arr[i]].add(i);
}
int i=0;
for(i=0;i<K;i++) { //처음으로 멀티탭 구멍을 다 채울 때 까지 i를 증가.
isMoving.add(arr[i]);
queue[arr[i]].poll();
if(isMoving.size()==N) {
i++;
break;
}
}
int count=0;
//이전에 멀티탭 구멍을 처음으로 다 채운 숫자를 알았으니 그 다음부터 탐색한다.
//그렇기에 for 문에서 i를 끌어와서 쓴다.
for(;i<K;i++) {
int num=arr[i];
queue[num].poll();
int index= -1;
int max=0;
if(isMoving.contains(num)) // 현재 전기용품이 이미 멀티탭에 꽂혀있다면 continue
continue;
for(int val:isMoving) {
if(queue[val].isEmpty()) {
//만약 앞으로 다시는 다시 쓰지 않는 전기용품이 있다면 index는 그 용품이 된다.
index=val;
break;
}
if(queue[val].peek()>max) { // 앞으로 다시 등장하는 데에 가장 오랜 시간이 걸리는 것을 찾음.
max=queue[val].peek();
index=val;
}
}
isMoving.remove(index); // 현재 멀티탭에서 제거함
isMoving.add(num); // 새로 추가하는 것을 멀티탭에 추가함
count++; //카운트 증가
}
System.out.println(count);
}
}
사실 예제 입력을 통과하고 코드를 제출할 때 별 기대 안했는데 맞아서 진짜 깜짝 놀랐다. 내가 생각하지 못한 예외가 분명히 있을거야 라고 생각했다.
처음으로 맞은 골드 1 문제였다.
뭔가 진짜 velog 블로그 포스팅을 시작한 이유로 실력이 더 느는 것 같다. 이전까지의 내 생각을 기록해 두니 문제를 다 푼후 한 번 더 생각해볼 수 있게 된다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212