46일차)알고리즘 문제(경사로의 개수, 택배 상자), 팀프로젝트 마무리 및 발표, 비행기 전광판 과제

>알고리즘 문제
1. 경사로의 개수
1)문제

현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다.
경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로 이동할 때 경사가 d[i]인 길을 지나야 함을 나타냅니다. 전기차가 경사로를 반복적으로 이동할 때 받는 스트레스를 관찰하기 위해 주어진 경사수열을 k번 반복할 수 있는 경로를 찾으려 합니다. 같은 칸을 여러 번 방문하거나 지나온 길을 바로 되돌아가는 경로도 가능합니다.
예를 들어 아래와 같은 격자에서 경사 수열 d = [1, -2, -1, 0, 2]이고 k = 2라고 가정해 보겠습니다. 이 경사 수열을 k = 2 번 반복할 수 있는 경로 중 하나는 아래 그림과 같습니다.

위 경로에서 방문한 칸의 높이는 방문 순서대로 [5, 6, 4, 3, 3, 5, 6, 4, 3, 3, 5]입니다. 길의 경사가 순서대로 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]으로, d가 2번 반복되었습니다.
격자 칸의 높이를 담은 2차원 정수 배열 grid, 경사 수열을 담은 1차원 정수 배열 d와 경사 수열을 반복하는 횟수를 나타내는 정수 k가 매개변수로 주어집니다. 이때, 격자 내에서 조건을 만족하는 경로의 수를 return 하도록 solution 함수를 완성해 주세요. 단, 답이 커질 수 있으므로 1,000,000,007(= 109 + 7)로 나눈 나머지를 return 해주세요.

---

제한사항

• 3 ≤ grid의 길이 = n ≤ 8
• 3 ≤ grid[i]의 길이 = m ≤ 8
  • 0 ≤ grid[i][j] ≤ 1,000
  • grid[i][j]는 각자의 i+1번째 행, j+1번째 열에 위치한 칸의 높이를 나타냅니다.
• 1 ≤ d의 길이 ≤ 100
  • -100 ≤ d의 원소 ≤ 100
• 1 ≤ k ≤ 10^9

2)솔루션

class Solution {
    val MOD=1000000007
    fun solution(grid: Array<IntArray>, d: IntArray, k: Int): Int {
        var answer: Int = 0
        
        //시작점 끝점 경우의수:좌표는 배열로 나타냄
        val route=HashMap<String,HashSet<String>>() //처음좌표,현재좌표
        val cost=HashMap<String,Int>() //처음좌표+현재좌표, cost 
        
        val leni=grid.size
        val lenj=grid[0].size
        //루트찾기
        val di=intArrayOf(1,-1,0,0)
        val dj=intArrayOf(0,0,1,-1)
        
        //dp를 이용 [idx][시작좌표][현재좌표]=경우의수
        val dp=Array(d.size+1){Array(leni*lenj){IntArray(leni*lenj){0}}}
        
        //아직 안움직인 경우의수:1
        for(i in 0..leni*lenj-1){
            dp[0][i][i]=1
        }
        
        for(i in 1..d.size){
            for(j in 0..leni*lenj-1){
                val x=j/lenj
                val y=j%lenj
                for(k in 0..3){
                    val dx=x+di[k]
                    val dy=y+dj[k]
                    if(dx in 0..leni-1&&dy in 0..lenj-1&&grid[dx][dy]-grid[x][y]==d[i-1]){
                        for(l in 0..leni*lenj-1){
                            dp[i][l][dx*lenj+dy]+=dp[i-1][l][j]%MOD
                            dp[i][l][dx*lenj+dy]%=MOD
                        }
                    }
                    
                }
            }
        }
        
        //시작,끝, 경우의수가 담긴 행렬
        //행렬곱을  n번하면 i,j원소가 i에서 j까지 n번에 걸쳐 가는 경우의수
        //즉 k번 곱하면 나온 원소들의 합이 정답
        //k번 곱하기 보다는 k를 2진수로 변환해서 2의 제곱수들의 합으로 k를 만들음
        var mat=dp[d.size]
        var result=Array(mat.size){IntArray(mat.size)}
        for(i in 0..mat.size-1){
            result[i][i]=1
        }
        
        val str=k.toString(2).reversed()
        
        
        
        for(i in 0..str.length-1){
            if(str[i]=='1'){
                result=matmult(result,mat)
            }
            mat=matmult(mat,mat)
        }
        
        for(i in 0..mat.size-1){
            for(j in 0..mat.size-1){
                answer+=result[i][j]
                answer%=MOD
            }
        }

        
        
        return answer
    }
    
    fun matmult(m1:Array<IntArray>, m2:Array<IntArray>):Array<IntArray>{
        val n=m1.size
        val result=Array(n){IntArray(n)}
        for(i in 0..n-1){
            for(j in 0..n-1){
                for(k in 0..n-1){
                    result[i][j]+=((m1[i][k].toLong()*m2[k][j].toLong())%MOD.toLong()).toInt()
                    result[i][j]%=MOD
                }
            }
        }
        return result
    }
    
    
}

-큐를 이용해서 BFS로 루트를 찾으려 했으나 메모리 초과가 나서 dp로 진행함.
-dp로 구한 결과에서  i,j의 원소는 i에서 j로 가는 루트수를 의미하므로 해당 행렬을 k회 곱하면 i,j원소가 i에서 k번 거쳐 j로 가는 경우의 수를 구하게 된다. 
-근데 그냥 k번 곱하면 시간이 많이 걸리므로 k를 2진수로 변환시킨후 기존 dp행렬을 계속 제곱해가면서 k를 2제곱수들의 곱으로 구성시킨다.
 
 
2. 택배상자
1)문제

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.
만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.
예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.
택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

---

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

 
2)솔루션

import java.util.*
class Solution {
    fun solution(order: IntArray): Int {
        var answer: Int = 0
        val stack = ArrayDeque<Int>()
        var max=0
        var idx=1
        for(i in order){
            if(idx<i){
                while(idx<i){
                    max=idx
                    stack.push(idx++)
                }
                answer++
                idx++
            }else if(idx>i){
                if(max==i){
                    stack.pop()
                    max=stack.peek()?:0
                    answer++
                }else{
                    break
                }
            }else{
                answer++
                idx++
            }
        }
        return answer
    }
}

 
 
 
>팀프로젝트 마무리
https://appdevelopjava.tistory.com/61

최종 완성

 
> 비행기 전광판 과제

package com.example.airplane

open class Flight(
    val flightInfo: FlightInfo,
    private val flightCreatedTime: String, //비행편 생성 시간
    private val updatedTime: String, ///비행편 업데이트 시간
    val scheduledTime: String, //예정시간
    var changeTime: String, //업데이트된 시간
    val codeshare: List<String>, //공동운항
    var flightStatus: String, //상태(탑승, 결항등)
)

data class FlightInfo(
    val id: String, //항공편 아이디
    val airplaneUniqueCode: String, //항공기 고유 코드
    val airlineCode: String, //항공사 코드
    val flightCode: String //편명
)

data class DepartureInfo(
    val destination:String, //목적지
    var checkinCounters: List<String>, //체크인 하는 곳
    var gateNumber:Int //탑승구
)

data class ArrivalInfo(
    val origin:String, //출발지
    var exit:String //출구
)

class DepartureFlight(
    val departureInfo: DepartureInfo,
    flightInfo: FlightInfo,
    flightCreatedTime: String,
    updatedTime: String,
    scheduledTime: String,
    changeTime: String,
    codeshare: List<String>,
    flightStatus: String,
) : Flight(
    flightInfo,
    flightCreatedTime,
    updatedTime,
    scheduledTime,
    changeTime,
    codeshare,
    flightStatus
){}

class ArrivalFlight(
    val arrivalInfo: ArrivalInfo,
    flightInfo: FlightInfo,
    flightCreatedTime: String,
    updatedTime: String,
    scheduledTime: String,
    changeTime: String,
    codeshare: List<String>,
    flightStatus: String,
) : Flight(
    flightInfo,
    flightCreatedTime,
    updatedTime,
    scheduledTime,
    changeTime,
    codeshare,
    flightStatus
){}

-공통인 부분은 Flight클래스로 만들음
-비행기 정보는 FlightInfo라는 데이터 클래스로 묶음
-출발전광판에만 존재하는 정보는 DepartureInfo로 묶음
-도착 전광판에만 존재하는 정보는 ArrivalInfo로 묶