[백준] 1700 - 멀티탭 스케줄링 (JAVA)

개츠비·2023년 3월 20일
0

백준

목록 보기
35/84
  1. 소요시간 : 30분
  2. 문제 사이트 : 백준
  3. 문제 수준 : 골드 1
  4. 문제 유형 : 그리디 알고리즘
  5. 다른 사람의 풀이를 참고 했는가 ? : X
  6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
  7. 문제 링크 : https://www.acmicpc.net/problem/1700
  8. 푼 날짜 : 2023.03.20

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘을 사용했다

2. 사고과정

그리디의 조건이 뭘까 ? 를 가장 오래 고민했다.

그리디의 조건은 나는 이렇게 생각했다.
1. 만약 이번 전기용품이 이미 멀티탭에서 사용중이라면 그냥 그대로 둔다.
2. 앞으로 다시는 쓰지 않는 전기용품이 있다면 그 전기용품을 멀티탭에서 제거하고 새로운 전기용품을 꽂는다.
3. 현재 멀티탭에서 사용하고 있는 것들 중 앞으로 다시는 쓰지 않는 전기용품이 없다면 ( 전부 최소한 앞으로 1번 이상 사용할 것이라면 ) 지금의 시점으로부터 가장 늦게 사용될 예정일 전기용품을 제거하고 새로운 전기용품을 꽂는다.

2-3번을 진행했다면 count 를 증가

3. 풀이과정

전체적으로 이전에 설명한 것과 같다.
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가지를 적용했다.

4. 소스코드

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);
		
		
		

	}
}

5. 결과

6. 회고

사실 예제 입력을 통과하고 코드를 제출할 때 별 기대 안했는데 맞아서 진짜 깜짝 놀랐다. 내가 생각하지 못한 예외가 분명히 있을거야 라고 생각했다.
처음으로 맞은 골드 1 문제였다.
뭔가 진짜 velog 블로그 포스팅을 시작한 이유로 실력이 더 느는 것 같다. 이전까지의 내 생각을 기록해 두니 문제를 다 푼후 한 번 더 생각해볼 수 있게 된다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212

profile
아이스 카라멜 마끼아또보단 뜨거운 아메리카노를, 맨투맨보단 니트를, 웹툰보단 책을 좋아하고 싶은 사람

0개의 댓글