23.11.07 TIL

알고리즘 풀이

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

1700번: 멀티탭 스케줄링

골드 문제!!

먼저 K개의 제품을 돌면서, 멀티탭을 모두 채워준다!
아직 남았다면, 뺄지 안뺄지를 정해줘야하는데

이미 끼워져 있다면 pass~
안 끼워져 있다면, 끼워져 있는 것들을 돌면서 뒤에 또 사용되는지를 확인한다!
만약 전부 쓴다면, 가장 마지막에 사용되는 것을 빼주는 방식으로 진행!!

테케가 다 통과해서 제출했더니 나에게 오는 것은

왜그런가 게시판에서 참고해봤더닝
K개의 기계들이 한 번도 안빠지고 진행되는 경우에서 발생했다
이를 해결하기 위해 초기에 모두 채워주는 부분에서 조건을 하나더 추가!
그 후 통과!

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

public class Main_BOJ_1700_멀티탭_스켐줄링 {
    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[] arr = new int[K];
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[] isUsed = new boolean[K + 1];
        int index = 0, count = 0;

        while (count < N && index < K) {
            if (!isUsed[arr[index]]) {
                isUsed[arr[index]] = true;
                count += 1;
            }
            index += 1;
        }

        int answer = 0;
        while (index < K) {
            if (!isUsed[arr[index]]) {
                List<Integer> list = new ArrayList<>();
                for (int i = index; i < K; i++) {
                    if (isUsed[arr[i]] && !list.contains(arr[i])) list.add(arr[i]);
                }

                if (list.size() == N) {
                    int remove = list.get(list.size() - 1);
                    isUsed[remove] = false;
                } else {
                    for (int j = 1; j <= K; j++) {
                        if (isUsed[j] && !list.contains(j)) {
                            isUsed[j] = false;
                            break;
                        }
                    }
                }

                isUsed[arr[index]] = true;
                answer += 1;
            }
            index += 1;
        }

        System.out.println(answer);
    }
}

내배캠 스프링 입문 강의 완독

Spring JPA를 마지막으로 1-2주차 강의를 전부 들었다!