>>알고리즘 문제
1. 프로세스
1)문제
문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
2)솔루션
class Solution {
fun solution(priorities: IntArray, location: Int): Int {
var queue=ArrayDeque<Pair<Int,Int>>()
priorities.forEachIndexed{i,v -> queue.addLast(Pair(v,i))}
var idx=1
while(true){
val cur=queue.removeFirst()
var flag=false
for(i in queue){
if(i.first>cur.first){
queue.addLast(cur)
flag=true
break
}
}
if(!flag){
if(cur.second==location) break
idx++
}
}
return idx
}
}-값과 인덱스를 묶어 처음에 큐에다가 전부 넣음
-큐에서 하나를 뺀 뒤 큐 안의 값들을 비교해 만약 현재 값보다 우선순위가 높으면 현재 값을 큐에 집어넣고, 우선순위가 낮으면 실행시킨뒤 다음루프로 넘어간다. 단 현재 실행되는 프로세스가 찾고자 하는 프로세스인 location에 해당하면 멈추고 실행 순서인 idx를 반환
2. 등산코스 정하기
1)문제
문제 설명
XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.
등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.
당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.
다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.
- 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.
위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다. 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.
등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.
등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.
XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.
제한사항
- 2 ≤ n ≤ 50,000
- n - 1 ≤ paths의 길이 ≤ 200,000
- paths의 원소는 [i, j, w] 형태입니다.
- i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
- w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
- 1 ≤ i < j ≤ n
- 1 ≤ w ≤ 10,000,000
- 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
- 1 ≤ gates의 길이 ≤ n
- 1 ≤ gates의 원소 ≤ n
- gates의 원소는 해당 지점이 출입구임을 나타냅니다.
- 1 ≤ summits의 길이 ≤ n
- 1 ≤ summits의 원소 ≤ n
- summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
- 출입구이면서 동시에 산봉우리인 지점은 없습니다.
- gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
- 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
- return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.
2)솔루션
import java.util.*
class Solution {
fun solution(n: Int, paths: Array<IntArray>, gates: IntArray, summits: IntArray): IntArray {
var answer: IntArray = intArrayOf()
val path=Array(n+1){ArrayList<Pair<Int,Int>>()}//인덱스는 출발지, Pair(도착지, weight)
val summit=hashSetOf<Int>()
for(i in summits) summit.add(i)
//패스 구성
for(i in paths){
path[i[0]]+=Pair(i[1],i[2])
path[i[1]]+=Pair(i[0],i[2])
}
val costs=IntArray(n+1){Int.MAX_VALUE} //각 지점까지의 최소 intensity
val q:Queue<Pair<Int,Int>> =ArrayDeque<Pair<Int,Int>>() //현 위치, 현 위치까지 최대 edge
for(i in gates){
q.offer(Pair(i,0))
costs[i]=0
}
while(q.isNotEmpty()){
val (cur,cost)=q.poll()
if(cur in summit) continue
if(cost>costs[cur]) continue
for((next,nextcost) in path[cur]){
//가려는 곳이 출입구면 스킵
if(next in gates) continue
val newcost=maxOf(nextcost,cost)
if(newcost>=costs[next]) continue
costs[next]=newcost
q.offer(Pair(next,newcost))
}
}
val answers=ArrayList<Pair<Int,Int>>()
summits.sort()
for(i in summits){
answers+=Pair(i,costs[i])
}
var minV=Int.MAX_VALUE
var minI=0
for((i,j) in answers){
if(j<minV){
minV=j
minI=i
}
}
answer+=minI
answer+=minV
return answer
}
}-우선 어레이리스트로 이루어진 배열에 등산로를 전부 집어넣는다.
-변형 BFS로 풀이
<1>시작은 출입구를 큐에 넣으며 시작
<2>큐에서 하나를 뺀 뒤 만약 봉우리거나 intensity가 해당 지점에서의 최소 intensity보다 크면 루프 넘어감
<3>현재 지점의 인접 등산로들에 대해 출입구로 이어져있으면 루프 스킵하고 아니면 진행
<3>인접 등산로들의 weight와 현재까지의 intensity를 비교해서 다음 지점intensity갱신
<4>intensity가 다음지점최소 intensity보다 크거나 같으면 스킵
<5>해당 없으면 최소 intensity를 갱신하고 큐에 넣음
<6>위 과정의 루프들을 돌아 나온 costs배열값으로 봉우리까지 최소 intentsity들을 뽑아낸뒤 최소값들을 뽑아냄.
<7>최소값이 여러개이면 봉우리 번호가 작은걸 뽑아야 하는데 미리 summits를 정렬해놔서 최소값을 뽑는과정에서 해결됨.
3. 징검다리
1)문제
문제 설명
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
| [21, 17] | [2, 9, 3, 11] | 2 |
| [2, 21] | [11, 3, 3, 8] | 3 |
| [2, 11] | [14, 3, 4, 4] | 3 |
| [11, 21] | [2, 12, 3, 8] | 2 |
| [2, 14] | [11, 6, 4, 4] | 4 |
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
제한사항- 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.
2)솔루션
class Solution {
fun solution(distance: Int, rocks: IntArray, n: Int): Int {
var answer = 0
rocks.sort()
val dist=ArrayList<Int>()
dist+=rocks[0]
for(i in 0..rocks.size-2){
dist+=rocks[i+1]-rocks[i]
}
dist+=distance-rocks[rocks.size-1]
var left=0
var right=distance+1
while(left<right){
val mid=(left+right)/2
var total=0
var removed=0
for(i in dist){
total+=i //앞에서부터 돌이 제거될때마다 처음부터 첫돌사이까지의 거리
//최소거리인 mid가 되기전까지 돌 제거
//최소거리를 만족하면 돌을 제거하지 않고 다음 돌부터 다시 제거
//이때 total은 제거되지 않은 돌부터 다음 첫돌까지 거리
if(total<mid){
removed++
}else{
total=0
}
}
if(n>removed){//돌을 더 제거해야 하므로 우측 범위 선택
left=mid+1
}else if(n<removed){//돌을 덜 제거해야 하므로 좌측 범위 선택
right=mid
}else{//순차적으로 제거한 결과 나온 최소거리이므로 최적의 경우엔 최소거리가 더 커질 가능성이 있다. 즉 우측 범위 선택
left=mid+1
}
}
return left-1
}
}-찾는 기준을 최소거리로 해서 이진탐색을 이용함
-left를 1, right를 distance+1로 해서 이진탐색 =>distance+1인 이유는 그냥 distance로 하면 돌을 전부 제거하는 경우를 포함시키지 못함
-mid를 기준으로 돌을 더 제거해야 하면 좌측범위, 돌을 덜 제거해야 하면 우측범위로 해서 루프돌림.
>개인프로젝트 구상
https://appdevelopjava.tistory.com/40
'코틀린-안드로이드' 카테고리의 다른 글
| 33일차)알고리즘 문제(타겟넘버, 짝수 행 세기), 개인프로젝트 디자인 구상 (0) | 2024.06.26 |
|---|---|
| 32일차)알고리즘 문제(피로도), 챌린지반 강의 1회차, 추가 과제 (0) | 2024.06.25 |
| 30일차)알고리즘 문제(기능개발, 카운트 다운) (0) | 2024.06.23 |
| 29일차)알고리즘 문제(의상, 미로 탈출 명령어, 2차원 동전 뒤집기) (0) | 2024.06.22 |
| 28일차)알고리즘 문제(할인 행사) (0) | 2024.06.21 |