자바에 큐라는 자료구조가 있나 ? 있네
Queue <Integer> queue = new LinkedList<>(); //인터페이스이기 때문에 큐 인터페이스를 상속받아 구현한 LinkedList클래스를 사용
근데 이건 큐보다는 해시맵을 이용해서
각 문서의 갯수(정수값key)에 중요도를 value로 해서 넣어주면 될 듯. 중요도는 중복이 된다고 했으니 가능
그런데 HashMap 자체가 입력순서를 유지하는 컬렉션이 아니래 ,.,,,,,,,,,,,,,,ㅠ
그냥 ArrayList로 하는 것도 괜찮을 것 같다. -> 음 제일 앞에 있는 list.get(0) 이 중요도가 높고 그 값이 내가 원한 index값의 중요도랑 같은 값이라면,, 으로 했는데 중요도는 중복이 가능하니까 그걸 구분할수가 없다.
결국은 자료구조 Queue를 사용해야한다고 한다. 그런데 일반적인 큐가 아닌
Priority Queue
를 써야한다. PriorityQueue란 우선순위 큐로써 일반적인 큐의 FIFO구조를 가지면서 데이터 들어온 순서대로가 아니라 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나감. 완전 문제에 적합하자나 !
흠 근데 이걸로 안 하고 Queue로 해봤다.
정말 이해하기가 어려웠다.
내일 다시 공부해야할 듯
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = Integer.parseInt(br.readLine());
while( num-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int count = Integer.parseInt(st.nextToken()); //문서의 갯수
int index = Integer.parseInt(st.nextToken()); //몇 번째로 인쇄되었는지 궁금한 문서가 큐에서 몇 번째에 있는지 나타내는 정수
LinkedList <int[]> q = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for(int i=0;i<count;i++) { //문서의 갯수만큼 큐에 인덱스와 중요도를 배열로 함께 넣음
q.offer(new int[]{i,Integer.parseInt(st.nextToken())});
}
int check = 0;
while(!q.isEmpty()) { //한 케이스에 대한 반복문
int []first = q.poll(); //제일 앞에있는 값을 뽑아서 first 배열에 인덱스, 중요도 순으로 넣음.
boolean isMax = true;
for(int i=0;i<q.size();i++) {
if(first[1] < q.get(i)[1]) {
q.offer(first);
for(int j=0;j<i ;j++) {
q.offer(q.poll());
}
isMax = false; // 가장 처음 뽑은 front원소가 가장 큰 중요도를 가지지 않았음.
break;
}
}
if( isMax == false) {
continue;
}
check++;
if(first[0] ==index)
break;
}
sb.append(check).append("\n");
}
System.out.println(sb);
}
}
다른 블로그 참고해서 겨우겨우 완성....
다시 이해하고 다시 풀어보자
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = Integer.parseInt(br.readLine());
while(num-- >0) { //num만큼 테스트 케이스 반복
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //문서의 갯수
int M = Integer.parseInt(st.nextToken()); //찾고싶은 인덱스
LinkedList <int[]> q = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
q.offer(new int[] {i, Integer.parseInt(st.nextToken())} ); //큐 세팅
}
int count = 0;
while(!q.isEmpty()) {
int poll[] = q.poll();
boolean isMax = true;
for(int i=0;i<q.size();i++) {
if(poll[1]<q.get(i)[1]) { //중요도가 더 큰게 있다면
q.offer(poll); //뽑았던 맨 처음 값을 맨 뒤에 추가
isMax = false;
for(int j=0;j<i;j++) { //중요도 큰 요소보다 앞에있는 값들을 poll해서 맨 뒤에 붙여줌
q.offer(q.poll());
}
break; //여기에 break안 걸면 최댓값 찾아도 모든 큐를 탐색해서 메모리 초과가 나옴.
}
}
if(isMax == false)
continue;
count++;
if(poll[0] == M)
break;
}
sb.append(count+"\n");
}
System.out.println(sb);
}
}
내가 최대한 풀어봄 근데 이해가 아니라 암기해서 푼 거 같은 느김이다 ㅠ
큐 공부 참고 사이트
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기 (tistory.com)
자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기 (tistory.com)
[백준] 1966번 : 프린터 큐 - JAVA [자바] (tistory.com)
[알고리즘 PS] 백준 1966 프린터 큐 자바 문제 풀이 (tistory.com)
백준1966 프린터 큐 자바 : 네이버 블로그 (naver.com)
[Deque]문제#2. 프린터 큐(백준 196.. : 네이버블로그 (naver.com)
참고해서 큐의 개념을 완벽하게 익히자 !
'알고리즘 > 백준' 카테고리의 다른 글
2164번 문제 : 카드 2 (0) | 2023.03.29 |
---|---|
2108번 문제 : 통계학 (0) | 2023.03.29 |
1929번 문제 : 소수구하기 (0) | 2023.03.22 |
1920번 문제 : 수 찾기 (0) | 2023.03.20 |
1874번 문제 : 스택 수열 (0) | 2023.03.19 |