Zayson
A to Zayson!
Zayson
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (132)
    • Computer Science (20)
      • Network (4)
      • DB (12)
      • OS (4)
    • Algorithm (32)
      • ์™„์ „ํƒ์ƒ‰(Brute-Force) (3)
      • ๊ทธ๋ฆฌ๋””(Greedy) (6)
      • ํˆฌํฌ์ธํ„ฐ(Two-Pointer) (1)
      • ๊ทธ๋ž˜ํ”„(Graph) (5)
      • BFS & DFS (9)
      • ๊ตฌํ˜„, ์‹œ๋ฎฌ๋ ˆ์ด์…˜(Implementation) (5)
      • ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ(DP) (3)
    • Backend (51)
      • Spring Boot (19)
      • JPA (16)
      • Kafka (2)
      • Java (13)
      • Kotlin (1)
    • DevOps (1)
      • Jenkins (5)
      • Oracle Cloud Infrastructure (1)
      • Kubernetes & Docker (1)
    • Trouble Shooting (3)
      • JPA (1)
      • Spring Boot (2)
    • ํšŒ๊ณ  (5)
      • ์—”๋นต ํ”„๋กœ์ ํŠธ ํฌ์ŠคํŠธ ๋กœ๋“œ๋งต (1)
      • 2022๋…„ (4)
    • Kafka (7)
      • Kafka (5)
      • Kafka Connect (2)
    • ๊ธฐ์ˆ  ์„œ์  (6)
      • ๋ฐ์ดํ„ฐ ์ค‘์‹ฌ ์• ํ”Œ๋ฆฌ์ผ€์ด์…˜ ์„ค๊ณ„ (3)
      • ๊ฐœ๋ฐœ์ž๊ฐ€ ๋ฐ˜๋“œ์‹œ ์ •๋ณตํ•ด์•ผํ•  ๊ฐ์ฒด ์ง€ํ–ฅ๊ณผ ๋””์ž์ธ ํŒจํ„ด (2)
      • ๊ฐ€์ƒ ๋ฉด์ ‘ ์‚ฌ๋ก€๋กœ ๋ฐฐ์šฐ๋Š” ๋Œ€๊ทœ๋ชจ ์‹œ์Šคํ…œ ์„ค๊ณ„ ๊ธฐ์ดˆ (1)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
  • ๊ทธ๋ฆฌ๋””
  • spring boot
  • ๊ด€๊ณ„ํ˜• ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์‹ค์ „ ์ž…๋ฌธ
  • BFS
  • ๊ตฌํ˜„
  • Kafka Connect
  • kafka
  • Computer science
  • SpringBoot
  • ์™„์ „ํƒ์ƒ‰
  • ์—”๋นตํ”„๋กœ์ ํŠธ
  • Backend
  • JPA
  • ๋‚˜ ํ˜ผ์ž ์Šคํ”„๋ง๋ถ€ํŠธ!
  • Java
  • ๋ผ์ด๋ธŒ์Šคํ„ฐ๋””
  • dfs
  • CS
  • ๋ฐฑ์ค€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

hELLO ยท Designed By ์ •์ƒ์šฐ.
Zayson

A to Zayson!

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค, Java] ๋‹จ์†์นด๋ฉ”๋ผ
Algorithm/๊ทธ๋ฆฌ๋””(Greedy)

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค, Java] ๋‹จ์†์นด๋ฉ”๋ผ

2022. 4. 28. 00:04

๐Ÿ”— ๋ฌธ์ œ ๋งํฌ

https://programmers.co.kr/learn/courses/30/lessons/42884

๐Ÿค” ๋ฌธ์ œ

๊ณ ์†๋„๋กœ๋ฅผ ์ด๋™ํ•˜๋Š” ๋ชจ๋“  ์ฐจ๋Ÿ‰์ด ๊ณ ์†๋„๋กœ๋ฅผ ์ด์šฉํ•˜๋ฉด์„œ ๋‹จ์†์šฉ ์นด๋ฉ”๋ผ๋ฅผ ํ•œ ๋ฒˆ์€ ๋งŒ๋‚˜๋„๋ก ์นด๋ฉ”๋ผ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๊ณ ์†๋„๋กœ๋ฅผ ์ด๋™ํ•˜๋Š” ์ฐจ๋Ÿ‰์˜ ๊ฒฝ๋กœ routes๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์ฐจ๋Ÿ‰์ด ํ•œ ๋ฒˆ์€ ๋‹จ์†์šฉ ์นด๋ฉ”๋ผ๋ฅผ ๋งŒ๋‚˜๋„๋ก ํ•˜๋ ค๋ฉด ์ตœ์†Œ ๋ช‡ ๋Œ€์˜ ์นด๋ฉ”๋ผ๋ฅผ ์„ค์น˜ํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”.

๐Ÿ“Œ ์ œํ•œ์‚ฌํ•ญ

  • ์ฐจ๋Ÿ‰์˜ ๋Œ€์ˆ˜๋Š” 1๋Œ€ ์ด์ƒ 10,000๋Œ€ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • routes์—๋Š” ์ฐจ๋Ÿ‰์˜ ์ด๋™ ๊ฒฝ๋กœ๊ฐ€ ํฌํ•จ๋˜์–ด ์žˆ์œผ๋ฉฐ routes[i][0]์—๋Š” i๋ฒˆ์งธ ์ฐจ๋Ÿ‰์ด ๊ณ ์†๋„๋กœ์— ์ง„์ž…ํ•œ ์ง€์ , routes[i][1]์—๋Š” i๋ฒˆ์งธ ์ฐจ๋Ÿ‰์ด ๊ณ ์†๋„๋กœ์—์„œ ๋‚˜๊ฐ„ ์ง€์ ์ด ์ ํ˜€ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ฐจ๋Ÿ‰์˜ ์ง„์ž…/์ง„์ถœ ์ง€์ ์— ์นด๋ฉ”๋ผ๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ์–ด๋„ ์นด๋ฉ”๋ผ๋ฅผ ๋งŒ๋‚œ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•ฉ๋‹ˆ๋‹ค.
  • ์ฐจ๋Ÿ‰์˜ ์ง„์ž… ์ง€์ , ์ง„์ถœ ์ง€์ ์€ -30,000 ์ด์ƒ 30,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.

๐Ÿ˜ฎ ๋ฌธ์ œ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

์ฐจ๋Ÿ‰์ด ์ง€๋‚˜๊ฐ€๋ฉด์„œ ๊ฒน์น˜๋Š” ์ง€์ ์„ ์ง€์ •ํ•œ ํ›„ ๊ฒน์น˜๋Š” ๋ถ€๋ถ„์ด ์—†๋‹ค๋ฉด ์นด๋ฉ”๋ผ๋ฅผ ํ•œ๋Œ€ ๋” ์„ค์น˜ํ•˜๋Š” ํ๋ฆ„์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ๋‹ค.

๋”ฐ๋ผ์„œ, ๋ฐฐ์—ด์„ โ€œ๋‚˜๊ฐ„ ์ง€์ โ€์œผ๋กœ ์ •๋ ฌํ•ด ์ค€๋‹ค. ๋‚˜๋Š” ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์˜€๋‹ค.

๋ฐฐ์—ด์„ ๋‚˜๊ฐ„ ์ง€์ ์œผ๋กœ ์ •๋ ฌ์„ ํ•˜๋ฉด ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์€ 7๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋‚˜์˜จ๋‹ค.

1,2,3์˜ ๊ฒฝ์šฐ ๋‹ค์Œ ์ฐจ๋Ÿ‰์˜ ์ง„์ž… ์ง€์ ์ด ๋ฒ”์œ„๋กœ ์ง€์ •ํ•œ ๋ถ€๋ถ„ ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฒฝ์šฐ (curIn โ‰ค rangeIn) โ†’ ์ด์ „ ์ฐจ๋Ÿ‰๊ณผ ๊ฒน์น˜๋Š” ๋ฒ”์œ„๊ฐ€ ๊ฐฑ์‹ ์„ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค.

4,5,6์˜ ๊ฒฝ์šฐ ๋‹ค์Œ ์ฐจ๋Ÿ‰์˜ ์ง„์ž… ์ง€์ ์ด ์นด๋ฉ”๋ผ ์„ค์น˜ ๋ฒ”์œ„ ์ง„์ž… ์ง€์  ๋ณด๋‹ค ํฌ๊ณ  ๋ฒ”์œ„ ์ง„์ถœ ์ง€์  ๋ณด๋‹ค ์ž‘์€ ๊ฒฝ์šฐ (rangeIn < curIn < rangeOut) โ†’ ๋ฒ”์œ„ ์ง„์ž… ์ง€์ ์„ ๋‹ค์Œ ์ฐจ๋Ÿ‰ ์ง„์ž…์ง€์ ์œผ๋กœ ๊ฐฑ์‹ ํ•ด์ค€๋‹ค.

7์˜ ๊ฒฝ์šฐ ์นด๋ฉ”๋ผ ์„ค์น˜ ๋ฒ”์œ„ ์ง„์ถœ ์ง€์  ๋ณด๋‹ค ๋‹ค์Œ ์ฐจ๋Ÿ‰์˜ ์ง„์ž…์ง€์ ์ด ๋” ํฌ๊ธฐ ๋•Œ๋ฌธ์— ์นด๋ฉ”๋ผ๋ฅผ ๋™์‹œ์— ์„ค์น˜ํ•  ์ˆ˜ ์—†๋‹ค. ๋”ฐ๋ผ์„œ, ์นด๋ฉ”๋ผ์˜ ์ˆ˜๋ฅผ ํ•œ๋Œ€ ์ฆ๊ฐ€ํ•œ ํ›„ ๋ฒ”์œ„๋ฅผ ์ƒˆ๋กœ ๋“ค์–ด์˜ค๋Š” ์ฐจ๋Ÿ‰์˜ ์ง„์ž…์ง€์ ๊ณผ ์ง„์ถœ์ง€์ ์œผ๋กœ ๊ฐฑ์‹ ํ•ด์ค€๋‹ค.

image

๐Ÿšฉ Java ์ฝ”๋“œ

package com.algorithm.Programmers.Lv3;

import java.util.PriorityQueue;

public class Solution_42884_๋‹จ์†์นด๋ฉ”๋ผ {
    public static void main(String[] args) {
        int[][] routes = {{-20,-15}, {-14,-5}, {-18,-13}, {-5,-3}};
        int solution = solution(routes);
        System.out.println("solution = " + solution);
    }

    private static int solution(int[][] routes) {
        int count = 1;
        PriorityQueue<Camera> pq = new PriorityQueue<>();
        for(int[] route : routes) {
            pq.offer(new Camera(route[0], route[1]));
        }

        int rangeIn = pq.peek().getIn();
        int rangeOut = pq.peek().getOut();
        while(!pq.isEmpty()) {
            Camera camera = pq.poll();
            int curIn = camera.getIn();
            int curOut = camera.getOut();

                        // ์ง„์ž… ์ง€์ ์ด ์ด์ „ ์ฐจ๋Ÿ‰์ด ์ฐํž ์ˆ˜ ์žˆ๋Š” ์นด๋ฉ”๋ผ ๋ฒ”์œ„์— ๋“ค์–ด๊ฐ€๋Š” ๊ฒฝ์šฐ (์‚ฌ์ง„์˜ 4,5,6๋ฒˆ)
            if(rangeIn < curIn && curIn < rangeOut) {
                rangeIn = curIn;
            }
                        // ์ง„์ž… ์ง€์ ์ด ์ด์ „ ์ฐจ๋Ÿ‰์ด ์ฐํž ์ˆ˜ ์žˆ๋Š” ์นด๋ฉ”๋ผ ๋ฒ”์œ„๋ณด๋‹ค ๋’ค์— ์žˆ๋Š” ๊ฒฝ์šฐ = ๊ฐฑ์‹  (์‚ฌ์ง„์˜ 7๋ฒˆ)
            else if(rangeOut < curIn){
                rangeIn = curIn;
                rangeOut = curOut;
                count++;
            }
                        // ์ด์™ธ์˜ ๊ฒฝ์šฐ ๋ฒ”์œ„๋ฅผ ๊ฐฑ์‹ ์„ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค. (์‚ฌ์ง„์˜ 1,2,3๋ฒˆ)
        }
        return count;
    }

    static class Camera implements Comparable<Camera> {
        private int in;
        private int out;

        public Camera(int in, int out) {
            this.in = in;
            this.out = out;
        }

        public int getIn() {
            return in;
        }

        public int getOut() {
            return out;
        }

        @Override
        public int compareTo(Camera o) {
            return Integer.compare(this.out, o.out);
        }
    }
}
๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm > ๊ทธ๋ฆฌ๋””(Greedy)' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€, Java] 5186๋ฒˆ : ํŒŒํ‹ฐ๋ฅผ ์—ด์–ด๋ผ!!!  (0) 2022.07.06
[๋ฐฑ์ค€, Java] 10775๋ฒˆ : ๊ณตํ•ญ  (0) 2022.06.21
[๋ฐฑ์ค€, Java] 1052๋ฒˆ : ๋ฌผ๋ณ‘  (0) 2022.05.17
[ย ๋ฐฑ์ค€, Java] 1339๋ฒˆ : ๋‹จ์–ด ์ˆ˜ํ•™  (0) 2022.04.27
[๋ฐฑ์ค€, Java] 16120๋ฒˆ : PPAP  (0) 2022.04.26
    'Algorithm/๊ทธ๋ฆฌ๋””(Greedy)' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [๋ฐฑ์ค€, Java] 10775๋ฒˆ : ๊ณตํ•ญ
    • [๋ฐฑ์ค€, Java] 1052๋ฒˆ : ๋ฌผ๋ณ‘
    • [ ๋ฐฑ์ค€, Java] 1339๋ฒˆ : ๋‹จ์–ด ์ˆ˜ํ•™
    • [๋ฐฑ์ค€, Java] 16120๋ฒˆ : PPAP
    Zayson
    Zayson
    ๊ณต๋ถ€ํ•œ ๋‚ด์šฉ์„ ์ •๋ฆฌํ•˜๋Š” ๊ณต๊ฐ„

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”