[ν] 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));
}
}
μ΄λ κ² λ¬Έμ λ₯Ό νμ΄ λ³΄μλλ°, μ΄ λ¬Έμ λ λ λμ μκ°μ λ°κΏμ£Όλ κ³κΈ°κ° λ κ² κ°λ€.
μ€λλ μ λ°°μ°κ³ κ°λλΉ~~