20266.04.13
문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
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 … 과 같이 표현합니다.
입출력 예
문제 풀이
1차 실행 오류
location 뒤에 우선순위가 더 큰 값이 있는 경우를 고려하지 않음
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
int max = priorities[0];
int maxIndex = 0;
int len = priorities.length;
// 우선순위가 가장 큰 수와 인덱스 구하기
for (int i = 1; i < len; i++) {
int n = priorities[i];
if (n > max) {
max = n;
maxIndex = i;
}
}
if (maxIndex == location) {
return 1;
}
int goal = priorities[location];
for (int i = 0; i < len; i++) {
int index = (i + maxIndex) % len;
int n = priorities[index];
if (index == location) {
return answer + 1;
}
if (n >= goal) {
answer++;
}
}
return answer;
}
}2차 실행 오류
문제를 제대로 이해하지 못했음. 현재 작업보다 우선순위가 더 높은 작업이
있을 경우, 큐의 맨 뒤로 이동해서 밀리는 과정을 구현하지 않음
class Solution {
public int solution(int[] priorities, int location) {
int answer = 1;
int max = priorities[0];
int maxIndex = 0;
int len = priorities.length;
// 우선순위가 가장 큰 수와 인덱스 구하기
for (int i = 1; i < len; i++) {
int n = priorities[i];
if (n > max) {
max = n;
maxIndex = i;
}
}
if (maxIndex == location) {
return answer;
}
int goal = priorities[location];
boolean isPassed = false;
for (int i = 0; i < len; i++) {
int index = (i + maxIndex) % len;
int n = priorities[index];
if (index == location) {
isPassed = true;
}
else if (n >= goal && isPassed == false) {
answer++;
}
else if (n > goal && isPassed == true) {
answer++;
}
}
return answer;
}
}나의 코드
소요시간: 1시간 30분
시간 복잡도: O()
LinkedHashMap을 이용하여 순서대로 우선순위와 인덱스를 삽입한 후,
현재 우선순위가 가장 높은 값을 탐색하는 함수를 따로 만들어서
큐의 동작을 구현하였다.
import java.util.Map;
import java.util.LinkedHashMap;
class Solution {
// 현재 해시맵에서 가장 큰 값 탐색
public int findMax(Map<Integer, Integer> map) {
int max = 0;
for (int value : map.values()) {
if (value > max) {
max = value;
}
}
return max;
}
public int solution(int[] priorities, int location) {
int answer = 0;
int len = priorities.length;
Map<Integer, Integer> map = new LinkedHashMap<>();
// 우선순위와 인덱스를 해시맵에 저장
for (int i = 0; i < len; i++) {
map.put(i, priorities[i]);
}
int count = 1;
while(true) {
int max = findMax(map);
int firstKey = 0;
int firstValue = 0;
// 첫 번째 키와 값 얻기
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
firstKey = entry.getKey();
firstValue = entry.getValue();
break;
}
if (max == priorities[location] && location == firstKey) {
break;
}
if (max == firstValue) { // 맨 앞의 값의 우선순위가 가장 높다면
map.remove(firstKey); // 목록에서 제거
answer++;
}
else { // 맨 앞의 값이 우선순위가 가장 높은 값이 아니라면
map.remove(firstKey);
map.put(firstKey, firstValue); // 맨 뒤로 보내기
}
}
return answer;
}
}AI 코드
.poll(): 맨 앞 요소를 꺼내고 제거하는 함수
제거하지 않고 확인만 하려면 .peek()
.anyMatch()가 Stream API에 속해있기 때문에 .stream()을 사용하여 변환
해시맵이 아니더라도 키와 값을 배열을 통해 저장해서 구현하는 것도
좋은 방법이라는 생각이 듦.
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int solution(int[] priorities, int location) {
Deque<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < priorities.length; i++) {
queue.add(new int[]{i, priorities[i]});
}
int count = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
boolean hasHigher = queue.stream().anyMatch(e -> e[1] > cur[1]);
if (hasHigher) {
queue.add(cur); // 뒤로
} else {
count++;
if (cur[0] == location) return count;
}
}
return -1;
}
}