TIL (2022.02.22)
➕ 오늘 푼 문제
프로그래머스 - 프린터
➕ 아이디어
- 큐에 프린트 물의 인덱스와 우선순위를 함께 저장한다.
- 큐에 원소가 2개 이상인 동안,
- 큐에서 원소를 뽑는다.
- 남은 큐에서 우선순위가 최대인 값을 뽑는다.
- 최대 우선순위가 현재 원소의 우선순위보다 크다면, 다시 큐에 넣는다.
- 아니라면 인쇄하고(
answer += 1
), 현재 원소가 location
과 같은 지 확인한다.
- 큐에 원소가 남았다면, 그 원소가
location
일 것이므로 인쇄 횟수 + 1을 해준다.
➕ Java 코드
import java.util.*;
class Paper implements Comparable<Paper>{
private int location;
private int priority;
Paper(int location, int priority){
this.setLocation(location);
this.setPriority(priority);
}
public Integer getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public int getLocation() {
return location;
}
public void setLocation(int location) {
this.location = location;
}
@Override
public String toString() {
return "Paper [location=" + location + ", priority=" + priority + "]";
}
@Override
public int compareTo(Paper o) {
return getPriority().compareTo(o.getPriority());
}
}
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
Queue<Paper> q = new LinkedList<Paper>();
for(int i=0; i<priorities.length; i++){
q.offer(new Paper(i, priorities[i]));
}
while(q.size() > 1){
Paper p = q.poll();
Paper maxPriorityPaper = Collections.max(q);
if (p.getPriority() < maxPriorityPaper.getPriority()){
q.offer(p);
}else{
answer += 1;
if(location == p.getLocation()){
return answer;
}
}
}
if(!q.isEmpty()){
answer += 1;
}
return answer;
}
}
➕ Python 코드
from collections import deque
def solution(priorities, location):
answer = 0
q = deque([])
for i in range(len(priorities)):
q.append((i, priorities[i]))
while len(q) > 1:
n, p = q.popleft()
max_priority = max(q, key=lambda x:x[1])[1]
if max_priority > p:
q.append((n, p))
else:
answer += 1
if location == n:
return answer
if q:
answer += 1
return answer
➕ 궁금한 내용 및 소감
- 아이디어 그대로 구현하면 되는 문제였지만, 역시나 구현이 약간 까다로운 문제였다. 여러 방식으로 구현할 수 있는데, 이번에는 max 함수를 통해 큐에서 최대값을 뽑아낼 수 있게 하였다. 이게 아니라면 큐를 순회하면서 최대값을 뽑을 수도 있다. (시간복잡도를 비교해보지 않았지만, 아마 내장 함수를 사용하는 것이 효율이 더 좋았을 것 같다.)
- 이번에는 자바에서 정렬 뿐만 아니라 max/min을 구할 때도 Comparable/Comparator 가 사용될 수 있음을 알았다. 여러모로 활용도가 높은 인터페이스라서 빨리 사용에 익숙해졌으면 좋겠다!
➕ 참고 문헌
- Java - Collections.max / Collections.min
- Java - Comparable / Comparator