-
프린터프로그래머스/스택, 큐 2022. 2. 4. 22:01
<최종 코드>
import java.util.*; class Solution { public int solution(int[] priorities, int location) { int N = priorities.length; List<Integer> importance = new ArrayList<>(); for(int i = 0; i<N; i++) { importance.add(priorities[i]); } Queue<Integer> papers = new LinkedList<>(); for(int i=0; i<N; i++) { papers.add(i); } int count = 1; while(!papers.isEmpty()) { int number=0; int size = importance.size(); int max = -1; for(int i=0; i<size; i++) { max = Math.max(max,importance.get(i)); } for(int i=0; i<size; i++) { if(importance.get(i) < max) { number++; }else { break; } } if(number != 0) { while(number -- > 0){ int M = importance.get(0); importance.remove(0); importance.add(M); int K = papers.poll(); papers.add(K); } } if(papers.peek() == location) { break; }else { importance.remove(0); papers.remove(); count++; } } return count; } }되게 복잡해 보인다.
다음에는 더 간단하게 코드를 완성할 수 있는 능력이 생겼으면!!
일단 예시에 나와있는,
priorities = [2,1,3,2]
location = 2
이 부분을 가지고 설명하겠다.
1. 초기화
위의 예시는, 중요도가 4개 나와 있으므로,
총 준비된 문서가 4개라는 뜻이다.
그래서 papers라는 큐를 만들어서, 여기에 4개의 문서, 즉 0 1 2 3 을 집어넣었다.
0은 첫번째 문서이다
나는 이때, 배열 priorities 값을 importance 라는 리스트에 옮겨 담았다.
그 이유는 리스트 크기를 동적으로 변경시킬 수 있기 때문이다.
이때 importance와 papers는 움직임이 같아야 한다.
예시의
priorities = [2,1,3,2] 에서 설명하자면,
중요도는 3이 제일 크다.
그렇다 함은, 세번째 문서가 제일 먼저 출력된다는 뜻이다.
그래서, 앞의 2 1 문서는 뒤로 밀리고 세번째 문서가 제일 먼저 출력된다.
importance : 2 1 3 2 -> 1 3 2 2 -> 3 2 2 1 -> 3 삭제됨.
이때,
papers 도 같은 움직임을 보인다.
0 1 2 3 -> 1 2 3 0 -> 2 3 0 1 -> 2삭제
더보기그런데 여기서 importance 는 리스트로, papers는 스택으로 사용하는 이유는,
importance 에서 제일 큰 값 3을 찾을 때, 인덱스를 활용해서 2 1 3 2 값들을 서로 비교할 것인데,
이때 스택에는 인덱스를 활용할 방법이 없다.
그래서 리스트를 사용해서 비교하도록 했다.
그래서 위의 코드에서 아래와 같이 importance 와 papers 초기화를 진행했다.
int N = priorities.length; List<Integer> importance = new ArrayList<>(); for(int i = 0; i<N; i++) { importance.add(priorities[i]); } Queue<Integer> papers = new LinkedList<>(); for(int i=0; i<N; i++) { papers.add(i); }2. 제일 큰 중요도 찾기(max 변수)
for(int i=0; i<size; i++) { max = Math.max(max,importance.get(i)); }이 코드에서 중요도 2 1 3 2 중 가장 큰 값인 3을 max로 지정했다.
3. number 변수
2 1 3 2 예에서 보면,
max 값인 3보다 작은 2 1 이 앞에 있다.
즉 2개가 있다.
이 경우 number 라는 변수에 2가 입력되도록 한다.
for(int i=0; i<size; i++) { if(importance.get(i) < max) { number++; }else { break; } }4. importance, papers 변경
위에서 number 값을 2로 했다.
importance, papers에서 값을 꺼내서 다시 넣어주는 것을 2회 진행한다.
importance : 2 1 3 2 -> 1 3 2 2 -> 3 2 2 1
papers : 0 1 2 3 -> 1 2 3 0 -> 2 3 0 1
if(number != 0) { while(number -- > 0){ int M = importance.get(0); importance.remove(0); importance.add(M); int K = papers.poll(); papers.add(K); } }5. count 세기
if(papers.peek() == location) { break; }else { importance.remove(0); papers.remove(); count++; }위의 4번 코드로 아래와 같은 상태가 됐다.
importance : 2 1 3 2 -> 1 3 2 2 -> 3 2 2 1
papers : 0 1 2 3 -> 1 2 3 0 -> 2 3 0 1
이때, papers의 맨 앞에 있는 값은 2 이다.
그리고 문제에서 location 으로 준 값도 2이다.
(즉, 세번째 문서가 언제 인쇄될지 리턴)
그러면 papers.peek() == location 을 만족하기 때문에,
break 로 while 문이 종료 되고
count 가 리턴된다.
count 값은 처음에 1로 초기화 되었기 때문에,
결국 1이 리턴된다.
즉, 우리가 찾고자 했던 세번째 문서는 맨 처음 출력되기 때문에 1이 리턴되는 것이다.
---
하지만 이 예시 말고 두 번째 예시는
importance : 1 1 9 1 1 1
location : 0
이다.
이 경우는,
importance : 1 1 9 1 1 1 -> 1 9 1 1 1 1 -> 9 1 1 1 1 1
papers : 0 1 2 3 4 5 -> 1 2 3 4 5 0 -> 2 3 4 5 0 1
이렇게 되는데, papers.peek() = 2, location = 0 이기 때문에
papers.peek() 와 location 값이 다르다.
그래서 importance 와 papers 에서 맨 앞 값을 삭제한 뒤,
importance : 1 1 1 1 1
papers : 3 4 5 0 1
count 값을 올려주고, 다시 while 문을 돈다.
계속 돌다가, papers.peek() 와 location 이 같을 때 멈춘뒤 count 값을 리턴한다.
그리고 끝난다.
----------------
# 유의점
이 문제를 풀면서 제일 유의해야 했던 점은, 아래 코드이다.
while(number -- > 0){ int M = importance.get(0); importance.remove(0); importance.add(M); int K = papers.poll(); papers.add(K); }나는 처음에 while 문이 아니라 for문을 사용해서,
for(int i=0; i<number ; i++)
이런 식으로 importance와 papers 에서 맨 앞에 있는 값을 제거하고, 다시 넣어주도록 했다.
그런데 문제가 있었다.
예를들어 위의 예시
importance : 2 1 3 2 를 보자.
i=0 일때
importance.remove(0) 으로
제일 먼저 2를 빼낸다.
그리고 다시 넣는다.
그러면 1 3 2 2 가 된다.
그리고 나면 i=1 이 된다.
그런데 보자.
우리는 지금 1을 빼서 다시 넣어줘야 하는데,
i=1 은 1이 아니라 3이다.
(즉 리스트는 맨 앞의 값을 빼내면 뒤의 값이 앞으로 채워진다.)
그래서 importance.remove(1) 을 하면 1을 빼내는 게 아니라, 3이 빼져서, 오류가 생기게 된다.
따라서 이런 부분은 유의를 해줘야 한다!!