[백준/BOJ] 1700 멀티탭 스케줄링 - JAVA

2024. 5. 24. 15:52·알고리즘/문제풀이

[백준/BOJ] 1700 멀티탭 스케줄링 - JAVA - 골드1

문제

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

문제 분석

조건

  • N개의 플러그가 있고 K번의 전기 용품을 사용한다.
  • 전기 용품의 이름은 K이하의 자연수로 순서대로 주어진다.
  • 플러그를 가장 적게 뽑을 때 플러그를 뽑는 횟수를 출력한다.

풀이방법

그리디 방법으로 접근한다. 

  1. 이미 플러그에 꼽혀있는 물품일 경우 넘어간다.
  2. 플러그가 비어있으면 빈 곳을 사용한다.
  3. 플러그가 가득 차있으면
    1. 뒤에 사용하지 않는 용품이 있는지 검사하여 사용하지 않는 용품을 뽑는다.
    2. 전부 다시 사용되는 용품일 경우  가장 마지막에 사용되는 용품을 뽑는다.

골드1 치고는 간단한 문제이다.

코드

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

public class Main {
    static int maxPlug;
    static int K;

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

        st = new StringTokenizer(br.readLine());
        maxPlug = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int[] order = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            order[i] = Integer.parseInt(st.nextToken());
        }

        int[] plugs = new int[maxPlug];
        int answer = 0;

        for (int use = 0; use < K; use++) {
            int plugNum = 0;
            for (int inPlugMachine : plugs) {
                //이미 플러그에 있는지 확인
                if (inPlugMachine == order[use]) {
                    plugNum = -1;
                    break;
                }
            }
            if (plugNum == -1) {
                continue;
            }
            plugNum = getEmptyPlugNum(plugs);
            if (plugNum >= 0) {
                //플러그 꽂을 위치 있음
                plugs[plugNum] = order[use];
                //continue;
            } else {
                answer++;
                plugNum = getNotUse(use, order, plugs);
                if (plugNum >= 0) {
                    plugs[plugNum] = order[use];
                } else {
                    plugs[getLastUse(use, order, plugs)] = order[use];
                }
            }

        }
        System.out.println(answer);
    }

    //가장 마지막에 사용하는 플러그 반환
    private static int getLastUse(int use, int[] order, int[] plugs) {
        if (use == order.length - 1) {
            return 0;
        }
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int plug = 0; plug < plugs.length; plug++) {
            m.put(plugs[plug], plug);
        }

        for (int i = use + 1; i < order.length; i++) {
            m.remove(order[i]);
            if (m.size() == 1) {
                break;
            }
        }
        for (Integer machine : m.keySet()) {
            return m.get(machine);
        }
        return 0;
    }

    /**
     * 뒤에 사용하지 않는 플러그 찾아 반환
     */
    private static int getNotUse(int use, int[] order, int[] plugs) {
        if (use == order.length - 1) {
            return 0;
        }
        int[] machine = new int[K + 1];
        Arrays.fill(machine, -1);
        for (int i = 0; i < plugs.length; i++) {
            machine[plugs[i]] = i;
        }
        for (int i = use + 1; i < order.length; i++) {
            if (machine[order[i]] >= 0) {
                machine[order[i]] = -1;
            }
        }
        for (int i = 0; i < K + 1; i++) {
            if (machine[i] >= 0) {
                return machine[i];
            }
        }
        return -1;
    }

    /**
     * 플러그 꽂을 위치 반환
     *
     * @return 자리 없으면 -1
     */
    private static int getEmptyPlugNum(int[] plugs) {
        for (int i = 0; i < plugs.length; i++) {
            if (plugs[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

결과

728x90
저작자표시 비영리 변경금지 (새창열림)
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준/BOJ] 11053 가장 긴 증가하는 부분 수열 - JAVA
  • [백준/BOJ] 14939 불 끄기 - JAVA
  • [백준/BOJ] 1520 내리막 길 - JAVA - 골드3
  • [백준/BOJ] 1014 컨닝 - JAVA
LIRI
LIRI
  • LIRI
    기록
    LIRI
  • 전체
    오늘
    어제
    • 분류 전체보기 (73)
      • 블로그 꾸미기 (0)
      • Spring (6)
      • React (3)
      • CS (0)
      • 알고리즘 (57)
        • 개념 (2)
        • 문제풀이 (54)
      • Java (1)
      • DB (1)
      • log (4)
        • SSAFY (3)
        • 궁금 (1)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 공지사항

  • 인기 글

  • 태그

    싸피
    BOJ
    알고리즘
    백준
    JWT
    LIS
    ssafy 합격 후기
    리액트
    불 끄기
    dfs
    알고리즘 문제풀이
    그리디
    Springsecurity
    Spring
    Java
    BFS
    springboot
    최장증가부분수열
    lv3
    Security
    골드1
    LV2
    dp
    pccp모의고사
    너비우선탐색
    프로그래머스
    도대체왜
    비트마스킹
    SSAFY 9기
    SSAFY
  • 최근 댓글

  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
LIRI
[백준/BOJ] 1700 멀티탭 스케줄링 - JAVA
상단으로

티스토리툴바