* 문제 설명
- 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다.
그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다.
- 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다.
- 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
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 |
이번에도 문제를 이해하는 데 시간이 많이 걸렸습니다.
더욱이 테스트 케이스도 딸랑 2개밖에 없는데..왜 무엇이 문제인지 한참 해맸던 것 같습니다.
처음에 문제를 보고 해맨 부분은 "가장 큰 값 다음에 서로 같은 값이 있는 경우는 어떻게 할 것인가?" 라는 문제 였습니다.
위의 [1, 1, 9, 1, 1]을 고유의 인덱스로 표현하면, [A, B, C, D, E, F] 이며 출력순서는 C, D, E, F, A, B 라고 합니다.
그러므로 "가장 큰값 이후의 순서가 서로 같으면 큰 값 다음 대상이다" 라고 생각 하고 접근하였습니다.
하지만 답을 제출하면 계속해서 틀렸다고 나와서 도통 뭐가 틀렸는지 알 수 없어서 힘들었습니다.
* 아니 테스트 케이스를 좀더 주면 어디 덧나나요 프로그래머스 님들....?
그러다 생각을 조금 바꾸어 "나보다 큰값이 존재하면 나는 뒤로 가고, 나보다 큰 값이 없으면 나는 제외된다" 라는 내용을 한번 적용 해 보기로 하였습니다.
먼저 데이터가 들어오면 각 데이터를 고유의 인덱스를 추가해 주는 작업을 합니다.
{
int priorities[] = { 1, 1, 9, 1, 1, 1 };
int location = 0;
LinkedList<Integer[]> sort = new LinkedList<>(); // 데이터를 담을 리스트
for (int i = 0; i < priorities.length; i++) { // 데이터를 key, value로 담아둡니다.
Integer[] value = new Integer[] { i, priorities[i] };
sort.add(value);
}
sort.forEach( arg->{
System.out.printf("인덱스(%d) : %d, ",arg[0],arg[1]);
});
}
위 내용을 실행하면 고유의 인덱스가 존재하면서 값도 잘 가지고 있는 연결리스트가 완성됩니다.
숫자 배열의 값은 [1, 1, 9, 1, 1, 1] 이며 인덱스는 [0, 1, 2, 3, 4, 5] 입니다.
이제 조건을 살펴보겠습니다.
나보다 큰값이 존재하면 나는 뒤로 가고, 나보다 큰 값이 없으면 나는 제외(출력)된다.
나를 기준으로 조회를 하려면 나 말고 다른 대상을 찾아야 하므로 나의 인덱스에 +1 이 증가된 반복문이 필요 합니다.
그리고 나보다 큰 값이 없을 때 까지 반복문을 동작해야 합니다.
2가지 내용을 통해 개념을 정리해서 간단한 코드를 작성합니다.
{
Integer[] value = sort.get(0); //나 입니다.
boolean imBig = true;
for (int j = 1; j < sort.size() - 1; j++) { //나 이외의 값 입니다.
Integer[] check = sort.get(j);
if (value[1] < check[1]) { // 본인보다 큰 값이 있습니다.
imBig = false;
}
}
System.out.println(imBig);
}
sort라는 연결 리스트(LinkedList)에는 숫자(Integer)형태의 배열을 가지고 있으며 0번째가 인덱스, 1번째가 값을 가지고 있습니다.
위 단순한 코드는 0번째 값을 대상으로 자기보다 큰 값이 있는지, 없는지를 판별하는 코드 입니다.
나보다 큰 값이 없으면 나는 제외(출력)되고 의 조건은 이제 완성 되었습니다.
다음으로 "나보다 큰 값이 있으면 나는 뒤로가고"의 조건을 완성하여 보겠습니다.
{
Integer[] value = sort.get(0); //나 입니다.
boolean imBig = true;
for (int j = 1; j < sort.size() - 1; j++) { //나 이외의 값 입니다.
Integer[] check = sort.get(j);
if (value[1] < check[1]) { // 본인보다 큰 값이 있습니다.
imBig = false;
}
}
System.out.println(imBig);
if (!imBig) { //나보다 큰 값이 있으면 나는 제거되고 뒤로 갑니다.
sort.remove(0);
sort.add(value);
}
}
이렇게 하면 나는 제거되면서 add 메소드를 통해 맨 뒤로 붙게 되었습니다.
만약 내가 가장 큰 값이어서 더 이상 동작할 필요없이 출력되어야 한다면 sort 연결리스트에서 제거되게 한 뒤에 재 정렬을 담을 연결리스트를 새로 만들어 추가하여 줍니다.
이러한 방법을 반복문을 통해서 sort의 값이 전부 사라질 때 까지 동작시켜 줍니다.
public static int solution(int[] priorities, int location) {
LinkedList<Integer[]> sort = new LinkedList<>(); // 데이터를 담을 리스트
for (int i = 0; i < priorities.length; i++) { // 데이터를 key, value로 담아둡니다.
Integer[] value = new Integer[] { i, priorities[i] };
sort.add(value);
}
sort.forEach( arg->{
System.out.printf("인덱스(%d) : %d, ",arg[0],arg[1]);
});
LinkedList<Integer[]> re_sort = new LinkedList<>(); // 순회한 데이터를 담을 리스트
while (true) {
boolean imBig = true;
Integer[] value = sort.get(0); // 나 입니다.
for (int j = 1; j < sort.size() - 1; j++) { //나 이외의 값 입니다.
Integer[] check = sort.get(j);
if (value[1] < check[1]) { // 본인보다 큰 값이 있으면 맨 뒤로 보냅니다.
imBig = false;
break;
}
}
if (!imBig) { //나보다 큰 값이 있으면 나는 제거되고 뒤로 갑니다.
sort.remove(0);
sort.add(value);
}
else{ // 보내는 경우가 아니면(자신이 제일 큰 경우 이면)
re_sort.add(value); // 재정렬 리스트에 값을 담고
sort.remove(value); // 기존 리스트에서 자신을 제거
}
if (sort.size() == 0) { // 두개의 리스트 크기가 일치하면 전부 완료하였으므로 반복문을 중지 합니다.
break;
}
}
return 0;
}
거의 다 왔습니다!
이제 남은 것은 재정렬된 re_sort 연결 리스트에서 정렬된 인덱스를 가지고 location 값을 비교하여 줍니다.
public static int solution(int[] priorities, int location) {
LinkedList<Integer[]> sort = new LinkedList<>(); // 데이터를 담을 리스트
for (int i = 0; i < priorities.length; i++) { // 데이터를 key, value로 담아둡니다.
Integer[] value = new Integer[] { i, priorities[i] };
sort.add(value);
}
LinkedList<Integer[]> re_sort = new LinkedList<>(); // 순회한 데이터를 담을 리스트
while (true) {
boolean imBig = true;
Integer[] value = sort.get(0); // 나 입니다.
for (int j = 1; j < sort.size() - 1; j++) { //나 이외의 값 입니다.
Integer[] check = sort.get(j);
if (value[1] < check[1]) { // 본인보다 큰 값이 있으면 맨 뒤로 보냅니다.
imBig = false;
break;
}
}
if (!imBig) { //나보다 큰 값이 있으면 나는 제거되고 뒤로 갑니다.
sort.remove(0);
sort.add(value);
}
else{ // 보내는 경우가 아니면(자신이 제일 큰 경우 이면)
re_sort.add(value); // 재정렬 리스트에 값을 담고
sort.remove(value); // 기존 리스트에서 자신을 제거
}
if (sort.size() == 0) { // 두개의 리스트 크기가 일치하면 전부 완료하였으므로 반복문을 중지 합니다.
break;
}
}
return IntStream.range(0, re_sort.size())
.filter(i -> re_sort.get(i)[0] == location) //인덱스를 찾아서
.map(arg -> arg + 1) // 1을 증가시킨다음에(위치가 0번 부터가 아니라 1번부터 이므로)
.findFirst().getAsInt(); //위치를 알려줍니다.
}
두근거리는 마음을 가지고 제출하여 봅니다!
드디어 성공입니다!
테스트 케이스가 몇개만 더 있었더라면 요구사항을 좀 더 확실하게 이해할 수 있지 않았나 싶습니다.
이상으로 프로그래머스 문제인 프린터에 대해서 정리하여 보았습니다.
궁금한점 또는 틀린점은 언제든 연락주세요! :)
'Java(자바) > 코딩 테스트 & 알고리즘' 카테고리의 다른 글
| 9. 디스크 컨트롤러 (프로그래머스, 힙 Level 3) (0) | 2021.03.02 |
|---|---|
| 8. 더 맵게 (프로그래머스, 힙 Level 2) (0) | 2021.01.26 |
| 6. 기능개발 (프로그래머스, 스택/큐 Level 2) (0) | 2021.01.19 |
| Java Quick 정렬 (0) | 2021.01.17 |
| Java Heap 정렬 (0) | 2021.01.14 |
댓글