μ½”λ”©ν…ŒμŠ€νŠΈ

[큐] 8. 응급싀

μ‹œνλ¦¬ν‹°μ§€ν˜Έ 2024. 1. 14. 16:38
8. 응급싀
 

μ„€λͺ…

메디컬 병원 μ‘κΈ‰μ‹€μ—λŠ” μ˜μ‚¬κ°€ ν•œ λͺ…밖에 μ—†μŠ΅λ‹ˆλ‹€.

응급싀은 ν™˜μžκ°€ λ„μ°©ν•œ μˆœμ„œλŒ€λ‘œ μ§„λ£Œλ₯Ό ν•©λ‹ˆλ‹€. ν•˜μ§€λ§Œ μœ„ν—˜λ„κ°€ 높은 ν™˜μžλŠ” 빨리 μ‘κΈ‰μ‘°μΉ˜λ₯Ό μ˜μ‚¬κ°€ ν•΄μ•Ό ν•©λ‹ˆλ‹€.

이런 문제λ₯Ό λ³΄μ™„ν•˜κΈ° μœ„ν•΄ 응급싀은 λ‹€μŒκ³Ό 같은 λ°©λ²•μœΌλ‘œ ν™˜μžμ˜ μ§„λ£Œμˆœμ„œλ₯Ό μ •ν•©λ‹ˆλ‹€.

• ν™˜μžκ°€ μ ‘μˆ˜ν•œ μˆœμ„œλŒ€λ‘œμ˜ λͺ©λ‘μ—μ„œ 제일 μ•žμ— μžˆλŠ” ν™˜μžλͺ©λ‘μ„ κΊΌλƒ…λ‹ˆλ‹€.

• λ‚˜λ¨Έμ§€ λŒ€κΈ° λͺ©λ‘μ—μ„œ κΊΌλ‚Έ ν™˜μž 보닀 μœ„ν—˜λ„κ°€ 높은 ν™˜μžκ°€ μ‘΄μž¬ν•˜λ©΄ λŒ€κΈ°λͺ©λ‘ 제일 λ’€λ‘œ λ‹€μ‹œ λ„£μŠ΅λ‹ˆλ‹€. κ·Έλ ‡μ§€ μ•ŠμœΌλ©΄ μ§„λ£Œλ₯Ό λ°›μŠ΅λ‹ˆλ‹€.

즉 λŒ€κΈ°λͺ©λ‘μ— 자기 보닀 μœ„ν—˜λ„κ°€ 높은 ν™˜μžκ°€ 없을 λ•Œ μžμ‹ μ΄ μ§„λ£Œλ₯Ό λ°›λŠ” κ΅¬μ‘°μž…λ‹ˆλ‹€.

ν˜„μž¬ Nλͺ…μ˜ ν™˜μžκ°€ λŒ€κΈ°λͺ©λ‘μ— μžˆμŠ΅λ‹ˆλ‹€.

Nλͺ…μ˜ λŒ€κΈ°λͺ©λ‘ μˆœμ„œμ˜ ν™˜μž μœ„ν—˜λ„κ°€ μ£Όμ–΄μ§€λ©΄, λŒ€κΈ°λͺ©λ‘μƒμ˜ M번째 ν™˜μžλŠ” λͺ‡ 번째둜 μ§„λ£Œλ₯Ό λ°›λŠ”μ§€ 좜λ ₯ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ„Έμš”.

λŒ€κΈ°λͺ©λ‘μƒμ˜ Mλ²ˆμ§ΈλŠ” λŒ€κΈ°λͺ©λ‘μ˜ 제일 처음 ν™˜μžλ₯Ό 0번째둜 κ°„μ£Όν•˜μ—¬ ν‘œν˜„ν•œ κ²ƒμž…λ‹ˆλ‹€.

μž…λ ₯

첫 쀄에 μžμ—°μˆ˜ N(5<=N<=100)κ³Ό M(0<=M<N) μ£Όμ–΄μ§‘λ‹ˆλ‹€.

두 번째 쀄에 μ ‘μˆ˜ν•œ μˆœμ„œλŒ€λ‘œ ν™˜μžμ˜ μœ„ν—˜λ„(50<=μœ„ν—˜λ„<=100)κ°€ μ£Όμ–΄μ§‘λ‹ˆλ‹€.

μœ„ν—˜λ„λŠ” 값이 높을 수둝 더 μœ„ν—˜ν•˜λ‹€λŠ” λœ»μž…λ‹ˆλ‹€. 같은 κ°’μ˜ μœ„ν—˜λ„κ°€ μ‘΄μž¬ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

좜λ ₯

M번째 ν™˜μžμ˜ λͺ‡ 번째둜 μ§„λ£Œλ°›λŠ”μ§€ 좜λ ₯ν•˜μ„Έμš”.

μ˜ˆμ‹œ μž…λ ₯ 1 

5 2
60 50 70 80 90

μ˜ˆμ‹œ 좜λ ₯ 1

3

μ˜ˆμ‹œ μž…λ ₯ 2 

6 3
70 60 90 60 60 60

μ˜ˆμ‹œ 좜λ ₯ 2

4

 

 

<<풀이>>

 

-λ‚˜μ˜ 풀이-

 

λ‚˜λŠ” λ‚˜λ¦„λŒ€λ‘œ μ˜μ‚¬μ½”λ“œλ₯Ό μž‘μ„±ν–ˆλŠ”λ° 과정은 쑰금 λ³΅μž‘ν•˜λ‹€. κ·Έλž˜λ„ μ–΄λŠμ •λ„ 논리적이라고 생각은 ν–ˆμ§€λ§Œ

κ°€μž₯ 큰값인지 μ•„λ‹Œμ§€ λ°˜ν™˜ν•˜λŠ” λ‹€λ₯Έ λ©”μ„œλ“œλ₯Ό λ§Œλ“œλŠ” κ³Όμ •μ—μ„œ νμ—λŠ” get() λ©”μ„œλ“œκ°€ μ—†μŒμ„ μ•Œκ²Œ λ˜μ—ˆλ‹€. 근데 μ§€κΈˆ 생각해보면 λ˜λŠ” κ²½μš°κ°€ μžˆμ„ μˆ˜λ„ μžˆκ² λ‹€.!!! 상ν–₯된 for문을 ν™œμš©ν•˜λŠ” 것이닀. 일단 λ‚˜μ€‘μ— λ‹€μ‹œ 해보겠닀.

import java.util.*;

class Main {
    private boolean isMax(int k, Queue<Integer> Q){
        for(int i = 0; i < Q.size(); i++) {
            Q.get(i) //μ—¬κΈ°μ„œ λ§‰νž˜ γ… γ…  stack은 κ°€μ§€κ³  μžˆμ§€λ§Œ νλŠ” 이 λ©”μ„œλ“œλ₯Ό μ‚¬μš©ν•  μˆ˜κ°€ μ—†λ‹€.
        }
    }


    private int solution(int n, int m, int[] arr) {
        Queue<Integer> Q = new LinkedList<>();
        int count = m, rank = 0;
        boolean run = true;

        while(run) {
            if(!isMax(Q.peek(), Q)) Q.offer(Q.poll());
            else {
                Q.poll();
                rank++;
                count--;
            }

            if(count == 0 && isMax(Q.peek(), Q)) {
                run = false;
            }

        }
        return rank;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m, arr));
    }
}

 

-κ°•μ‚¬λ‹˜ 풀이-

 

이번 ν’€μ΄λŠ” 쑰금 λ†€λžλ‹€. λ¬Όλ‘  λͺ¨λ₯΄λŠ” 것은 μ•„λ‹ˆμ§€λ§Œ, μ½”ν…Œμ—μ„œ λ³΄λ‹ˆκΉŒ 또 μƒ‰λ‹¬λžλ‹€. λ°”λ‘œ λ”°λ‘œ 클래슀λ₯Ό λ§Œλ“€μ–΄μ„œ κ΅¬ν–ˆλ‹€λŠ” 점이닀. λ‚˜λŠ” μ²˜μŒμ— μ–΄λ–»κ²Œ νŠΉμ •κ°’μ„ μ§€μ •ν• κΉŒ?? λΌλŠ” 생각을 κ°€μ‘Œμ§€λ§Œ λ„μ €νžˆ 생각이 λ‚˜μ§€κ°€ μ•Šμ•„ νŠΉλ‹¨μ˜ 쑰치둜 μ–΄λ–€ λ³€μˆ˜λ₯Ό μ§€μ •ν•΄μ„œ 그것에 μ˜μ‘΄ν•˜λ©΄μ„œ νŠΉμ •ν•œ 값을 κ΅¬ν•˜λ €κ³  ν–ˆλ‹€.(μœ„μ˜ 방식을 μ°Έκ³ ν•˜λ©΄ λœλ‹€.)

 

ν•˜μ§€λ§Œ κ°•μ‚¬λ‹˜μ€ κΉ”λ”ν•˜κ²Œ 클래슀 Person으둜 지정해두고 κ·Έ Queue의 μ œλ„€λ¦­μ„ Person으둜 λ‘μ–΄μ„œ 객체λ₯Ό λ„£μ–΄μ£Όμ—ˆλ‹€. γ…‹γ…‹

 

λ‚˜λ¦„ μ„Όμ„Έμ΄μ…˜μ΄μ—ˆλ‹€ γ…‹γ…‹

 

그리고, ν—·κ°ˆλ¦΄ μˆ˜κ°€ μžˆλŠ”κ²Œ, Q.offer(new Person(i, arr[i])) 이 뢀뢄이닀.

 

ν•˜μ§€λ§Œ μš°λ¦¬λŠ” λ³€μˆ˜κ°€ λ“€μ–΄κ°€μ•Ό ν•œλ‹€κ³  μƒκ°ν•˜μ§€λ§Œ, λ³€μˆ˜κ°€ λ°”λ‘œ new Person(i, arr[i]) 이것을 μ°Έμ‘°ν•˜κΈ° λ•Œλ¬Έμ— 같은 것이라고 해도 λ¬΄λ°©ν•˜λ‹€. κ·Έλ ‡κΈ° λ•Œλ¬Έμ— ꡳ이 λ³€μˆ˜λ₯Ό λ§Œλ“€μ–΄μ„œ 넣을 ν•„μš”κ°€ μ—†κ³  μ΄λ ‡κ²Œ λ°”λ‘œ 넣어도 λ˜λŠ” 것이닀. 

 

κ·Έλ ‡κ²Œ ν•΄μ„œ 객체λ₯Ό λ„£μ–΄μ£Όκ³  λΉ„κ΅ν•˜κΈ° μ‹œμž‘ν•œλ‹€.

 

그리고 μ—¬κΈ°μ„œ 또 쒋은 μ•„μ΄λ””μ–΄λŠ” tmpλ₯Ό μ‚¬μš©ν•œ 것이닀. 

μΌμ‹œμ μœΌλ‘œ pollν•œ 값을 κ°€μ§€κ³  μžˆλ‹€κ°€ λ‹€μ‹œ λ„£μ–΄μ•Ό ν•  λ•Œ offer(tmp)λ₯Ό ν•΄μ£Όλ©΄ λœλ‹€. μ΄λ ‡κ²Œ ν•˜λ©΄

μ΅œμ’…μ μœΌλ‘œ tmp의 μˆœμ„œ 값이 μš°λ¦¬κ°€ κ΅¬ν•˜κ³ μžν•˜λŠ” μˆœμ„œκ°’κ³Ό 비ꡐλ₯Ό μ’€ 더 효율적으둜 ν•  수 μžˆλ‹€.

 

단지 poll만 ν•˜λ©΄ 끝날거 κ°™μ•˜λ˜ λ‚˜μ˜ 생각을 바꿔쀬닀 γ…‹γ…‹ 

 

import java.util.*;

class Person {
    int id;
    int priority;
    public Person(int id, int priority) {
        this.id = id;
        this.priority = priority;
    }
}

class Main {
    private int solution(int n, int m, int[] arr) {
         int answer = 0;
         Queue<Person> Q = new LinkedList<>();
         for(int i = 0; i < n; i++) {
             Q.offer(new Person(i, arr[i]));
         }
         
         while(!Q.isEmpty()) {
             Person tmp = Q.poll();
             for(Person x : Q) {
                 if(x.priority > tmp.priority) {
                     Q.offer(tmp);
                     tmp = null;
                     break;
                 }
             }
             if(tmp != null) {
                 answer++;
                 if(tmp.id == m) return answer;
             }
         }
         return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m, arr));
    }
}

 

μ΄λ ‡κ²Œ 문제λ₯Ό ν’€μ–΄ λ³΄μ•˜λŠ”λ°, 이 λ¬Έμ œλŠ” 또 λ‚˜μ˜ 생각을 λ°”κΏ”μ£ΌλŠ” 계기가 된 것 κ°™λ‹€. 

 

μ˜€λŠ˜λ„ 잘 배우고 κ°‘λ‹ˆλ‹Ή~~