π νλ‘κ·Έλλ¨Έμ€ / μ€ν&ν / Level2 / νλ¦°ν°
π λ¬Έμ
νλ‘κ·Έλλ¨Έμ€
μ½λ μ€μ¬μ κ°λ°μ μ±μ©. μ€ν κΈ°λ°μ ν¬μ§μ λ§€μΉ. νλ‘κ·Έλλ¨Έμ€μ κ°λ°μ λ§μΆ€ν νλ‘νμ λ±λ‘νκ³ , λμ κΈ°μ κΆν©μ΄ μ λ§λ κΈ°μ λ€μ λ§€μΉ λ°μΌμΈμ.
programmers.co.kr
π« μ ν μ¬ν
- νμ¬ λκΈ°λͺ©λ‘μλ 1κ° μ΄μ 100κ° μ΄νμ λ¬Έμκ° μμ΅λλ€.
- μΈμ μμ μ μ€μλλ 1~9λ‘ νννλ©° μ«μκ° ν΄μλ‘ μ€μνλ€λ λ»μ λλ€.
- locationμ 0 μ΄μ (νμ¬ λκΈ°λͺ©λ‘μ μλ μμ μ - 1) μ΄νμ κ°μ κ°μ§λ©° λκΈ°λͺ©λ‘μ κ°μ₯ μμ μμΌλ©΄ 0, λ λ²μ§Έμ μμΌλ©΄ 1λ‘ ννν©λλ€.
π μ μΆλ ₯ μ
| priorities | location | return |
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
π€ νμ΄ λ°©λ²
1οΈβ£ μλ£κ΅¬μ‘° μ¬μ©
β‘οΈ μμμ λΉΌκ³ , λ§μ½ μ°μ μμκ° λ λμ λ¬Έμκ° μλ€λ©΄ λ€λ‘ λμ΄κ°λ μ리μ΄λ―λ‘ Queue κ° μ ν©
2οΈβ£ κ°μ μ°μ μμ μΌ λ location κ°μ ꡬλΆνλ λ°©λ²
β‘οΈ κ°μ₯ μ€λ«λμ κ³ λ―Όν λΆλΆ μ€ νλμ΄λ€. νμ λ£κ³ λ리λ€λ³΄λ©΄ μΈλ±μ€λ₯Ό νλνλ μ κ²½μΈ μ μλ κ²μ΄ μλλ° μ΄λ»κ² κ°μ μ°μ μμλ₯Ό κ°μ§ μμ²λ€ μ¬μ΄μμ μΈλ±μ€λ₯Ό νμΈνλμ§κ° λ¬Έμ μλ€.
Map μ΄λ λ°°μ΄ νμ© λ±μ λ°©λ²μ μκ°ν΄λ³΄μμ§λ§ λΉν¨μ¨μ μΈ λΆλΆλ€λ λ§μκ³ , μνλ ννλ μλμλ€.
κ·Έλ¬λ μ€ κ³Όκ±° λΉμ·ν λ¬Έμ μμ ν΄λμ€λ₯Ό λ°λ‘ μμ±νμ¬ λ΄μλ κΈ°μ΅μ΄ μμ΄μ μλμ κ°μ ꡬ쑰λ₯Ό μκ°νλ©΄μ job ν΄λμ€λ₯Ό μμ±ν λ€ νμ λ£μ΄ μ£Όμλ€.
β job ν΄λμ€
class job {
int index; // λ°°μ΄μμμ index (= location)
int priority; // λ°°μ΄μμμ μμκ° (= μ°μ μμ)
public job (int index, int priority) {
this.index = index;
this.priority = priority;
}
}
β‘ Queue λ₯Ό μμ±νμ¬ λ£μ΄μ£Όλ κ³Όμ
class Solution {
// μ μλ³μλ‘ ν μμ±
public static Queue<job> q = new LinkedList<job>();
public int solution(int[] priorities, int location) {
// λ°λ³΅λ¬Έμ ν΅ν΄ μ°¨λ‘λλ‘ νμ λ£μ΄μ€
for (int i=0; i<priorities.length; i++) {
q.add(new job(i, priorities[i])); // job κ°μ²΄ μμ± ν μΆκ°
}
}
β’ μ΅μ’ ꡬ쑰
β‘οΈ μ£Όμ΄μ§ λ°°μ΄μ΄ [2, 1, 3, 2] λΌκ³ ν λ,

3οΈβ£ νμ κ³Όμ
β μΌλ¨ μ£Όμ΄μ§ λ°°μ΄μ μ λ ¬νμ¬ μ°μ μμλ₯Ό μ€λ¦μ°¨μ μ λ ¬ νμλ€.
// κΈ°μ‘΄ λ°°μ΄ : int[] arr -> [2, 1, 3, 2]
Arrays.sort(arr);
// μ λ ¬ ν : [1, 2, 2, 3]
β‘οΈ λ€μμλΆν° νλμ© μμΌλ‘ κ°λ©΄ μΆλ ₯ν΄μΌν μ°μ μμ λ²νΈλ₯Ό μ μ μλ€.
β‘ printer() ν¨μλ₯Ό ꡬννμ¬ μΆλ ₯λλ job κ°μ²΄λ₯Ό λ°ννλλ‘ νμλ€.
/*
리ν΄κ° : μΆλ ₯λλ job κ°μ²΄
νλΌλ―Έν° : μΆλ ₯λμ΄μΌνλ μ°μ μμ κ°
*/
public static job printer(int max) {
job j;
while (true) { // μΆλ ₯λμ΄μΌν job μ μ°Ύμ λ κΉμ§ λ°λ³΅
j = q.remove(); // νμμ 첫λ²μ§Έ job μ μ κ±°
if (j.priority == max) { // ν΄λΉ job μ μ°μ μμκ° λ겨λ°μ μΈμκ°κ³Ό λμΌνμ§ νμΈ
return j; // λμΌνλ©΄ ν΄λΉ job μ 리ν΄
}
q.add(j); // μΌμΉνμ§ μλλ€λ©΄ 맨 λ€λ‘ 보λ΄κ³ λ€μ λ°λ³΅
}
}
β’ printer() ν¨μλ‘ λΆν° λ°ν λ job μ index κ°μ΄ location κ³Ό κ°λ€λ©΄ answer κ°μ 리ν΄
while (j.index != location) {
// μ°μ μμκ° κ°μ job μ΄λΌλ μ°Ύλ location κ°μ κ°μ§ job μ΄ μλλΌλ©΄ κ³μ μ§ν
answer++;
prior = priorities[priorities.length-answer];
j = printer(prior);
}
π» νμ΄ μ½λ
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
// job class μμ±
class job {
int index; // λ³μβ : priorities λ°°μ΄μμμ index κ°
int priority; // λ³μβ‘ : priorities λ°°μ΄μμμ μμ κ°
public job (int index, int priority) { // μμ±μ
this.index = index;
this.priority = priority;
}
}
class Solution {
// μ μλ³μλ‘ Queue μμ±
public static Queue<job> q = new LinkedList<job>();
public int solution(int[] priorities, int location) {
int answer = 0;
// κΈ°μ‘΄ priorities λ°°μ΄μ κ°λ€μ job κ°μ²΄λ‘ μμ±νμ¬ νμ λ£μ΄μ€
for (int i=0; i<priorities.length; i++) {
q.add(new job(i, priorities[i]));
}
job j = new job(-1, -1); // λ°λ³΅λ¬Έμ μν job κ°μ²΄ μμ±
int prior = 0; // λ³μ : μ°μ μμ λ²νΈ
Arrays.sort(priorities); // μ°μ μμ νμΈμ μν λ°°μ΄ μ λ ¬
while (j.index != location) {
// μμ
ν΄μΌν job μ index κ° location κ³Ό κ°μμ§ λκΉμ§ λ°λ³΅
// λ§μ½ κ°μ μ°μ μμμ μμ
λ¬Όμ΄ μΆλ ₯λμλλΌλ index κ° λ§μ§ μμΌλ©΄ λ©μΆμ§ μμ
answer++;
// λ°°μ΄μ λ§μ§λ§ (μ μΌ ν°κ°) -> λ°°μ΄μ 첫λ²μ§Έ (μ μΌ μμκ°) μμλ‘ νμ
prior = priorities[priorities.length-answer];
// μΆλ ₯ν job μ
λ ₯λ°μ
j = printer(prior);
}
return answer;
}
/*
νλΌλ―Έν°
β max : μΆλ ₯ν΄μΌν μ°μ μμ κ°
리ν΄κ°
β‘οΈ μΆλ ₯λμΌν job
*/
public static job printer(int max) {
job j; // λ°λ³΅λ¬Όμ μν job κ°μ²΄ μμ±
while (true) { // job μ μ°Ύμ λκΉμ§ λ°λ³΅λ¨
j = q.remove(); // Queue μμ head μ μλ 첫λ²μ§Έ job μ κ±°
if (j.priority == max) { // ν΄λΉ job μ μ°μ μμκ° νμΈ
return j; // λμΌνλ©΄ ν΄λΉ job 리ν΄
}
q.add(j); // μλ κ²½μ° Queue μ 맨 λ€μ λ£μ΄μ£Όκ³ λ°λ³΅λ¬Έ κ³μ μ§ν
}
}
}
[level 2] Title: νλ¦°ν°, Time: 1.24 ms, Memory: 73.7 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@426b0d8
Show file tree Showing 2 changed files with 153 additions and 0 deletions.
github.com