[프로그래머스] 프로세스

문제 주소

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

문제 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다. 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• priorities의 길이는 1 이상 100 이하입니다.
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예

priorities location return

[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

제출 코드

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] p, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();

        Integer [] priorities = new Integer[p.length];
        for(int i = 0; i<p.length; i++){
            map.put(i,p[i]);
            priorities[i] = p[i];
        }
        
        Arrays.sort(priorities, Collections.reverseOrder());
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=priorities[count-1]){
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

테스트 1 〉	통과 (0.51ms, 76.6MB)
테스트 2 〉	통과 (1.64ms, 82.3MB)
테스트 3 〉	통과 (0.87ms, 70.3MB)
테스트 4 〉	통과 (0.77ms, 83.5MB)
테스트 5 〉	통과 (1.06ms, 78.3MB)
테스트 6 〉	통과 (0.64ms, 77.8MB)
테스트 7 〉	통과 (0.59ms, 78.5MB)
테스트 8 〉	통과 (0.83ms, 77.6MB)
테스트 9 〉	통과 (0.45ms, 82.7MB)
테스트 10 〉	통과 (0.57ms, 74.4MB)
테스트 11 〉	통과 (0.78ms, 78.8MB)
테스트 12 〉	통과 (0.56ms, 75.6MB)
테스트 13 〉	통과 (1.18ms, 74MB)
테스트 14 〉	통과 (0.35ms, 78.3MB)
테스트 15 〉	통과 (0.49ms, 75.9MB)
테스트 16 〉	통과 (0.43ms, 73.8MB)
테스트 17 〉	통과 (0.92ms, 73MB)
테스트 18 〉	통과 (0.48ms, 64.4MB)
테스트 19 〉	통과 (0.91ms, 75.9MB)
테스트 20 〉	통과 (0.73ms, 76MB)

문제 풀이

제일 빠른거 제일 먼저 하고 그 뒤쪽으로 탐색하는거네

List에다 넣어놓고 remove를 해봐야지

→ 뭐가 몇번짼지 알아야돼서 Map 쓰기로 함

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] priorities, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();
        for(int i = 0; i<priorities.length; i++){
            map.put(i,priorities[i]);
        }

        int max = 0;
        //find max
        ArrayList<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet()); 
        for(Map.Entry<Integer,Integer> entry : list){
                            
                Integer key = entry.getKey();
                Integer index = entry.getValue();
            
            if(index>max){
                max = index;
            }
        }
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(map.size()>0){
            if(order.getOrDefault(idx,-1)!=-1){
                if(map.get(idx)>=max){
                    order.put(idx,count);
                    map.remove(idx);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }
        
        return order.get(location);
    }
}

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.
테스트 결과 (~˘▾˘)~
2개 중 0개 성공

while문이 안 끝나나봄

map.remove했는데 왜?

remove로 가는 if가 실행이 안 돼서 그랬을듯

일단 while이 안 끝나는거 같으니까

나중에는 count≥priorities.length 로 끝낼건데

지금은 idx≥priorities.length로 돌려봄

while(idx>=priorities.length){
            if(order.getOrDefault(idx,-1)!=-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    map.remove(idx);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] priorities, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();
        for(int i = 0; i<priorities.length; i++){
            map.put(i,priorities[i]);
        }

        int max = 0;
        //find max
        ArrayList<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet()); 
        for(Map.Entry<Integer,Integer> entry : list){
                            
                Integer key = entry.getKey();
                Integer index = entry.getValue();
            
            if(index>max){
                max = index;
            }
        }
        System.out.println("max: "+max);
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(idx>=priorities.length){
            if(order.getOrDefault(idx,-1)!=-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    map.remove(idx);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

Exception in thread "main" java.lang.NullPointerException
	at Solution.solution(Unknown Source)
	at SolutionTest.lambda$main$0(Unknown Source)
	at SolutionTest$SolutionRunner.run(Unknown Source)
	at SolutionTest.main(Unknown Source)

그냥 배열 써도 되지 않나 싶어서 고쳐봄

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] priorities, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();
        
        for(int i = 0; i<priorities.length; i++){
            map.put(i,priorities[i]);
        }

        int max = 0;
        //find max
        for(int i = 0; i<priorities.length ;i++){
            if(max<priorities[i]){
                max = priorities[i];
            }
        }
        
        System.out.println("max: "+max);
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(idx>=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    map.remove(idx);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

그리고 이미 order에 있으면 패스해야하는데 없을때만 하는것도 수정해봄

while(idx>=priorities.length){

저거 부등호 방향 잘못된거같음

while(idx<=priorities.length){

이렇게 해봄

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

아 왜 저렇게 뜨는지 알았음

while(idx<priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    map.remove(idx);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }

→

idx를 %priorities.length로 나눠버리는데 어떻게 (idx<priorities.length) 이 조건이 달성될 수 있겠음

그냥 count로 바꿈

또 nullpointererror가 뜸

remove를 해버려서 idx가 달라졌을수 있다고 함

근데 order에 들어있나 안들어있나로 이미 체크하는데 map에서 remove할 필요가 없는거같음

while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }

이렇게 해봄

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=max){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    count++;
                }
            }
            idx = (idx+1)%priorities.length;
        }

여기에서 max랑만 비교하면 안되고 order의 전에 저장된 거랑 비교해줘야 할듯함

int [] sorted = Arrays.sort(priorities);
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){

                if(map.get(idx)>=sorted[count-1]){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }

이렇게 해줌

int [] sorted = Arrays.sort(priorities);

→

Arrays.sort(priorities);

Arrays.sort(priorities);
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=priorities[count-1]){
                    System.out.println("idx: "+idx+" count: "+count);
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();

        for(int i = 0; i<priorities.length; i++){
            map.put(i,priorities[i]);
        }   
        Arrays.sort(priorities);
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<priorities.length){
            System.out.println("count: "+count);
            System.out.println("idx: "+idx);
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=priorities[count-1]){
                    System.out.println("map.get(idx)"+map.get(idx));
                    System.out.println("priorities[count-1]: "+priorities[count-1]);
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

테스트 1
입력값 〉	[2, 1, 3, 2], 2
기댓값 〉	1
실행 결과 〉	실행한 결괏값 2이 기댓값 1과 다릅니다.
출력 〉	
count: 1
idx: 0
map.get(idx)2
priorities[count-1]: 1
count: 2
idx: 1
count: 2
idx: 2
map.get(idx)3
priorities[count-1]: 2
count: 3
idx: 3
map.get(idx)2
priorities[count-1]: 2
테스트 2
입력값 〉	[1, 1, 9, 1, 1, 1], 0
기댓값 〉	5
실행 결과 〉	실행한 결괏값 1이 기댓값 5과 다릅니다.
출력 〉	
count: 1
idx: 0
map.get(idx)1
priorities[count-1]: 1
count: 2
idx: 1
map.get(idx)1
priorities[count-1]: 1
count: 3
idx: 2
map.get(idx)9
priorities[count-1]: 1
count: 4
idx: 3
map.get(idx)1
priorities[count-1]: 1
count: 5
idx: 4
map.get(idx)1
priorities[count-1]: 1

배열 정렬을 desc로 해야한다는걸 깨달음

Arrays.sort(priorities, Collections.reverseorder());

^

int [] 는 안되고 Integer [] 만 된다고 함

public int solution(int[] p, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();

        Integer [] priorities = new Integer[priorities.length];
        for(int i = 0; i<p.length; i++){
            map.put(i,p[i]);
            priorites[i] = p[i];
        }
        
        Arrays.sort(priorities, Collections.reverseorder());

바꿔봤는데 안됨

Collections.reverseOrder()

O가 대문자여야 함

저거 수정하고 테스트 통과함

class Solution {
    public int solution(int[] p, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();

        Integer [] priorities = new Integer[p.length];
        for(int i = 0; i<p.length; i++){
            map.put(i,p[i]);
            priorities[i] = p[i];
        }
        
        Arrays.sort(priorities, Collections.reverseOrder());
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<priorities.length){
            System.out.println("count: "+count);
            System.out.println("idx: "+idx);
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=priorities[count-1]){
                    System.out.println("map.get(idx)"+map.get(idx));
                    System.out.println("priorities[count-1]: "+priorities[count-1]);
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

제출해봄

테스트 1 〉	통과 (15.22ms, 79.3MB)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	통과 (24.03ms, 82.1MB)
테스트 4 〉	통과 (17.52ms, 70MB)
테스트 5 〉	실패 (런타임 에러)
테스트 6 〉	통과 (19.92ms, 84.3MB)
테스트 7 〉	통과 (20.63ms, 86.8MB)
테스트 8 〉	통과 (39.32ms, 84.4MB)
테스트 9 〉	통과 (9.75ms, 72.7MB)
테스트 10 〉	통과 (20.35ms, 79.4MB)
테스트 11 〉	통과 (18.67ms, 81.8MB)
테스트 12 〉	통과 (13.58ms, 77MB)
테스트 13 〉	통과 (21.45ms, 78.1MB)
테스트 14 〉	통과 (7.00ms, 75.8MB)
테스트 15 〉	통과 (14.39ms, 75.6MB)
테스트 16 〉	통과 (11.08ms, 84.5MB)
테스트 17 〉	통과 (18.32ms, 76.6MB)
테스트 18 〉	실패 (런타임 에러)
테스트 19 〉	통과 (19.90ms, 76.7MB)
테스트 20 〉	통과 (16.02ms, 78.8MB)

while(count<priorities.length)

→ 다시 while(count≤priorities.length) 로 바꿨더니 잘 됨

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] p, int location) {
        //등록, 뭐가 몇번째에 실행되었는지 알려면 Map 써야할듯
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> order = new HashMap<Integer,Integer>();

        Integer [] priorities = new Integer[p.length];
        for(int i = 0; i<p.length; i++){
            map.put(i,p[i]);
            priorities[i] = p[i];
        }
        
        Arrays.sort(priorities, Collections.reverseOrder());
        
        //인덱스
        int idx = 0;
        int count = 1;
        //find process
        //order에 포함됐으면 건너뜀
        while(count<=priorities.length){
            if(order.getOrDefault(idx,-1)==-1){
                if(map.get(idx)>=priorities[count-1]){
                    order.put(idx,count);
                    count++;
                }

            }
            idx = (idx+1)%priorities.length;
        }
        return order.get(location);
    }
}

이렇게 제출하고 통과함