41일차)알고리즘 문제(다리를 지나는 트럭, 호텔 방 배정), 팀프로젝트

>알고리즘 문제

1. 다리를 지나는 트럭

1)문제

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

2)솔루션

class Solution {
    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        var answer = 0
        
        val q=ArrayDeque<Int>(bridge_length)
        repeat(bridge_length){
            q.addLast(0)
        }
        var total=0
        var idx=0
        
        while(true){
            total-=q.removeFirst()
            answer++
            if(total==0&&idx==truck_weights.size) break
            
            if(idx<truck_weights.size&&weight-total>=truck_weights[idx]){
                val tmp=truck_weights[idx++]
                total+=tmp
                q.addLast(tmp)
            }else{
                q.addLast(0)
            }
        }
        
        
        return answer
    }
}

-처음에는 큐에 전부 0으로 채움

-트럭이 올라가면 트럭 무게를 큐에 집어넣음

-다리위 무게 총합이 한계라 트럭이 못올라가면 0을 넣음

-while문을 돌려서 시간 계산

 

 

 

2. 호텔 방 배정

1)문제

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호배정된 방 번호

1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

2)솔루션

class Solution {
    fun solution(k: Long, room_number: LongArray): LongArray {
        var answer = LongArray(room_number.size)
        
        val assigned=HashMap<Long,Long>()
        
        
        //방을 추가시에는 키는 배정된 방, 값은 빈방
        //키로 체크해서 배정된 방이 아니면 키+1로 맵에 넣어줌
        //키로 체크해서 배정된 방이면 배정된 방들목록을 모아두면서 다음방으로 넘어감
        //배정되지 않은 방이 나오면 배정해줌(마찬가지로key,key+1)
        //모아둔 방들의 값도 전부 key+1로 갱신
        for((i,value) in room_number.withIndex()){
            var v=value
            val tmpset=HashSet<Long>()
            while(assigned.containsKey(v)){
                tmpset.add(v)
                v=assigned[v] as Long
            }
            for(j in tmpset){
                assigned.put(j,v+1)
            }
            assigned.put(v,v+1)
            answer[i]=v
        }
        
        
        
        
        return answer
    }
}

 

 

>팀프로젝트

https://appdevelopjava.tistory.com/55