[알고리즘] 백준 1700번: BufferedReader, StringTokenizer

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

1700번: 멀티탭 스케줄링

 

1700번은 그리디 알고리즘을 이용하는 문제인데, 그리디가 문제가 아니라 코테에 쓰이는 기본 개념들을 잘 모르겠어서 정리하면서 풀어보았다. 

 

 

- Scanner는 느려서 보통 BufferReader 을 쓰는 듯

- 근데 BufferReader는 한 줄씩 밖에 못 읽어서 한 줄을 여러 단어로 나누기 위해 StringTokenizer을 같이 사용한다

 

[1] 첫 번째 답(틀림):

 

1) 꽂으려는 기기가 코드에 이미 꽂혀 있는 경우 -> continue

2) 꽂으려는 기기가 코드에 없는 경우

  2-1) 코드 구멍이 비어있을 경우 -> 넣는다

  2-2) 코드 구멍이 차 있을 경우 -> 코드에 꽂혀있는 기기들을 이후에 몇 번 더 쓰는지 세고, 그 중에 가장 적게 나오는 값을 반환하여 코드에서 제거

 

근데,

2 9
1 2 3 1 2 3 1 2 3

답) 4 // 이 케이스에서 오류가 났다!

이유는 최솟값 나오는 값이 2개 이상인 경우에 어떻게 할지를 안 설정해줬다.

 

 

[2] 두 번째 답(틀림):

 

최솟값이 2개 이상인 경우 그 중에서 가장 나중에 써야 하는 기기를 빼주는 로직을 추가해줬다.

근데 왜 틀렸는지 모르겠다 ㅠㅠ

 

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int order[] = new int[k];
	
		for(int i=0; i<k; i++) {
			order[i] = Integer.parseInt(st.nextToken());
		}
		
		int count = 0;
		ArrayList<Integer> code = new ArrayList();
		for(int i=0; i<k; i++) {
			if(code.contains(order[i])) {
				continue;
			}
			else { // 코드에 안 꽂혀있는 경우
				
				if(code.size()<n) { // 코드에 안 꽂혀있는데 빈 경우
					code.add(order[i]);
				}
				else { //코드에 다 꽂힌 경우
					HashMap<Integer, Integer> elecs = new HashMap<Integer, Integer>(); // 사용하는 전기용품들과 탐색 시 사용할 값
					for(int p=0; p<n; p++) {
						elecs.put(code.get(p), 0);
					}
					for(int j=i+1; j<k; j++) {
						if(elecs.containsKey(order[j])) {
								elecs.put(order[j], elecs.get(order[j])+1);
						}
					}
					//여기서부터 값이 최소인 것 골라서 key 반환
					
					int minValue = Collections.min(elecs.values());
					int minValue_key = 0;
					
					ArrayList<Integer> keys = new ArrayList();
					
					for(int key : elecs.keySet()) {
						if(elecs.get(key).equals(minValue)) {
							keys.add(key);
						}
					}
//					* 추가 ~
					if(keys.size()==1) {
						minValue_key=keys.get(0);
					}
					else {
						minValue_key=keys.get(keys.size()-1);
					}
//					~ 추가 *
					
					code.remove((Integer)minValue_key); 
					// 여기서 remove(3) 하면 index가 3인 값을 지워준다. 그래서 (Integer) 붙여줘야 값 3인 것이 삭제된다.
					code.add(order[i]);
					count++;
				}	
			}
		}
		System.out.println(count);
	}
}