์ผ๋ฐ์ ์ธ ํ๋ฆฐํฐ๋ ์ธ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ์ธ์ํฉ๋๋ค. ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ์ค์ํ ๋ฌธ์๊ฐ ๋์ค์ ์ธ์๋ ์ ์์ต๋๋ค. ์ด๋ฐ ๋ฌธ์ ๋ฅผ ๋ณด์ํ๊ธฐ ์ํด ์ค์๋๊ฐ ๋์ ๋ฌธ์๋ฅผ ๋จผ์ ์ธ์ํ๋ ํ๋ฆฐํฐ๋ฅผ ๊ฐ๋ฐํ์ต๋๋ค. ์ด ์๋กญ๊ฒ ๊ฐ๋ฐํ ํ๋ฆฐํฐ๋ ์๋์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์ธ์ ์์ ์ ์ํํฉ๋๋ค.
1. ์ธ์ ๋๊ธฐ๋ชฉ๋ก์ ๊ฐ์ฅ ์์ ์๋ ๋ฌธ์(J)๋ฅผ ๋๊ธฐ๋ชฉ๋ก์์ ๊บผ๋ ๋๋ค.
2. ๋๋จธ์ง ์ธ์ ๋๊ธฐ๋ชฉ๋ก์์ J๋ณด๋ค ์ค์๋๊ฐ ๋์ ๋ฌธ์๊ฐ ํ ๊ฐ๋ผ๋ ์กด์ฌํ๋ฉด J๋ฅผ ๋๊ธฐ๋ชฉ๋ก์ ๊ฐ์ฅ ๋ง์ง๋ง์ ๋ฃ์ต๋๋ค.
3. ๊ทธ๋ ์ง ์์ผ๋ฉด J๋ฅผ ์ธ์ํฉ๋๋ค.
์๋ฅผ ๋ค์ด, 4๊ฐ์ ๋ฌธ์(A, B, C, D)๊ฐ ์์๋๋ก ์ธ์ ๋๊ธฐ๋ชฉ๋ก์ ์๊ณ ์ค์๋๊ฐ 2 1 3 2 ๋ผ๋ฉด C D A B ์์ผ๋ก ์ธ์ํ๊ฒ ๋ฉ๋๋ค.
๋ด๊ฐ ์ธ์๋ฅผ ์์ฒญํ ๋ฌธ์๊ฐ ๋ช ๋ฒ์งธ๋ก ์ธ์๋๋์ง ์๊ณ ์ถ์ต๋๋ค. ์์ ์์์ C๋ 1๋ฒ์งธ๋ก, A๋ 3๋ฒ์งธ๋ก ์ธ์๋ฉ๋๋ค.
ํ์ฌ ๋๊ธฐ๋ชฉ๋ก์ ์๋ ๋ฌธ์์ ์ค์๋๊ฐ ์์๋๋ก ๋ด๊ธด ๋ฐฐ์ด priorities์ ๋ด๊ฐ ์ธ์๋ฅผ ์์ฒญํ ๋ฌธ์๊ฐ ํ์ฌ ๋๊ธฐ๋ชฉ๋ก์ ์ด๋ค ์์น์ ์๋์ง๋ฅผ ์๋ ค์ฃผ๋ location์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ด๊ฐ ์ธ์๋ฅผ ์์ฒญํ ๋ฌธ์๊ฐ ๋ช ๋ฒ์งธ๋ก ์ธ์๋๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
ํ์ฌ ๋๊ธฐ๋ชฉ๋ก์๋ 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
๐ก queue ์ฌ์ฉ
๐ก queue ๋งจ ์์ ์๋ ๊ฒ์ ๊ฐ์ ธ์ ๋ค์ ํฐ ์๊ฐ ์๋ค๋ฉด flag = true
๐ก flag๊ฐ true๋ผ๋ฉด ์ด ์ซ์๋ฅผ ๋นผ์ ๋งจ ๋ค์ ๋ฃ์
๐ก ๋ด๊ฐ ๋นผ๋ด๋ ค๊ณ ํ๋ ๊ฒ์ด ์ ์ผ ํฌ๊ณ ๋งจ ์์ ์์ ๋, queue์ ๋จ์์๋ size ๋ฅผ ์ด์ฉํ์ฌ answer ๊ณ์ฐ
Queue<Integer> q = new LinkedList<Integer>();
int cur = q.peek().pri;
boolean flag = false;
for(Priority p : q){
if(cur < p.pri) flag = true;
}
if(flag) q.add(q.poll());
else {
if(q.poll().idx == location){
answer = priorities.length - q.size();
}
}
import java.util.*;
class Programmers2 {
public int solution(int[] priorities, int location) {
int answer = 0;
Queue<Priority> q = new LinkedList<>();
for(int i=0; i<priorities.length; i++){
q.add(new Priority(i, priorities[i]));
}
while(!q.isEmpty()){
int cur = q.peek().pri;
boolean flag = false;
for(Priority p : q){
if(cur < p.pri) flag = true;
}
if(flag) q.add(q.poll());
else {
if(q.poll().idx == location){
answer = priorities.length - q.size();
}
}
}
return answer;
}
public static class Priority {
int idx;
int pri;
Priority(int idx, int pri){
this.idx = idx;
this.pri = pri;
}
}
}
์ฑ๊ณตโจ