51일차)알고리즘 문제(억억단을 외우자, 무인도 여행)

>알고리즘 문제

1. 억억단을 외우자
(1)문제
영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ e ≤ 5,000,000
1 ≤ starts의 길이 ≤ min {e,100,000}
1 ≤ starts의 원소 ≤ e
starts에는 중복되는 원소가 존재하지 않습니다.


(2)솔루션

class Solution {
    fun solution(e: Int, start: IntArray): IntArray {
        var answer: IntArray = IntArray(start.size)
        
        
        val starts=start.sortedDescending()
        val min=starts.last()
        val cnt=IntArray(e+1) //starts.min..e의 약수 개수, idx는 원래수 - min
        for(i in 1..e){
            var s=i
            while(s<=e){
                cnt[s]++
                s+=i
            }
        }
        val result=HashMap<Int,Int>()
        var max=0
        var maxValue=0
        var idx=0
        for(i in e downTo min){
            if(cnt[i]>=max){
                max=cnt[i]
                maxValue=i
            }
            if(i==starts[idx]){
                result.put(i,maxValue)
                ++idx
            }
        }
        for((i,v) in start.withIndex()){
            answer[i]=result[v] as Int
        }
        
        return answer
    }
}

-약수를 일일히 구하기 보단 1부터 e까지 수에대한 각각 e이하의 배수를 구해서 억억단에서 각 수가 몇번 나오는지 구한다.
=>이후 starts의 큰수부터 내려가며 가장많이 니오는 수를 찾음.


2. 무인도 여행
(1)문제
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

제한사항
3 ≤ maps의 길이 ≤ 100
3 ≤ maps[i]의 길이 ≤ 100
maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
지도는 직사각형 형태입니다

(2)솔루션

class Solution {
    fun solution(maps: Array<String>): IntArray {
        var answer: IntArray = intArrayOf()
        val hashSet=HashSet<Pair<Int,Int>>()
        for(i in maps.indices){
            for(j in maps[0].indices){
                hashSet.add(Pair(i,j))
            }
        }
        val di=intArrayOf(0,0,1,-1)
        val dj=intArrayOf(1,-1,0,0)
        
        val q=ArrayDeque<Pair<Int,Int>>()
        var sum=0
        while(hashSet.isNotEmpty()||q.isNotEmpty()){
            var flag=false
            val (curi,curj)=if(q.isEmpty()) {
                val tmp=hashSet.first()
                hashSet.remove(tmp)
                tmp
            } else{
                flag=true
                q.removeFirst()
            }
            
            if(maps[curi][curj]=='X') continue
            
            if(flag){
                sum+=maps[curi][curj].toString().toInt()
            }
            else{
                if(sum!=0) answer+=sum
                sum=maps[curi][curj].toString().toInt()
            }
            
            for(i in 0..3){
                val tmp=Pair(curi+di[i],curj+dj[i])
                if(hashSet.contains(tmp)&&maps[tmp.first][tmp.second]!='X'){
                    hashSet.remove(tmp)
                    q.addLast(tmp)
                }
            }
        }
        //마지막 남은 sum처리
        if(sum!=0) answer+=sum
        answer.sort()
        if(answer.isEmpty()) answer+=-1
        
        return answer
    }
}

-BFS를 이용해서 각 섬을 구해서 이후 정렬해서 답을 구함