>알고리즘 문제
1. k진수에서 소수 개수 구하기
1)문제
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
2)솔루션
class Solution {
fun solution(n: Int, k: Int): Int {
var answer: Int = 0
val longs=spl(n,k)
if(longs.isEmpty()) return 0
val prime=BooleanArray(longs.size){true}
for(i in longs.indices){
for(j in 2L..Math.sqrt(longs[i].toDouble()).toLong()){
if(longs[i]/j!=1L&&longs[i]%j==0L){
prime[i]=false
break
}
}
}
for(i in prime){
if(i) answer++
}
return answer
}
fun spl(n:Int, k:Int):List<Long>{
var tmp=n
val str=StringBuilder()
while(tmp!=0){
str.append(tmp%k)
tmp/=k
}
return str.reverse().toString().split("0").filter{it!=""&&it!="1"}.map{it.toLong()}
}
}-k진수로 변환 후 0을 기준으로 잘라서 1을 제외한 값들을 소수판별을 해서 체크
-숫자가 너무 커질 수있기에 long으로 형변환 시킨후 구했음
2. 짝수행 세기
1)문제
문제 설명
모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어집니다. 다음 조건을 모두 만족하는 2차원 배열 b의 경우의 수를 (107 + 19)로 나눈 나머지를 return 하도록 solution 함수를 완성해주세요.
- b의 모든 원소는 0 아니면 1입니다.
- a의 행/열의 개수와 b의 행/열의 개수가 같습니다. (= a와 b의 크기가 같습니다.)
- i = 1, 2, ..., (a의 열의 개수)에 대해서 a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같습니다.
- b의 각 행에 들어 있는 1의 개수가 짝수입니다. (0도 짝수입니다.)
제한 사항
- a의 행의 개수는 1 이상 300 이하입니다.
- a의 각 행의 길이는 1 이상 300 이하로 모두 동일합니다.
2)솔루션
class Solution {
fun solution(a: Array<IntArray>): Int {
var answer: Int = -1
var coln=IntArray(a[0].size){0}
val row=a.size //행 개수, 세로길이
val col=a[0].size //열 개수, 가로길이
for(i in a[0].indices){
var sum=0
for(j in a.indices){
sum+=a[j][i]
}
coln[i]=sum
}
val mod=10000019
val c=Array(row+1){IntArray(row+1)} //파스칼 법칙 이용해 rowCrow까지 연산해서 저장해둠, c[n][r]=nCr
c[0][0]=1
for(i in 1..row){
for(j in 0..i){
if(i==j||j==0) c[i][j]=1
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod
}
}
val dp=Array(col){IntArray(row+1){0}} //dp[선택된 열][까지의 짝수행 개수]
dp[0][row-coln[0]]=c[row][row-coln[0]] //열의 원소는 row개. 그중 짝수행인 0의 자리를 고르는 경우의수
//선택된 열i, 짝수행수 j
//dp[i][j]==0이면 스킵
//다음 선택에 대하여 짝수행중 k개를 선택한다고 하자
//선택가능한 k범위는
//최소:maxOf(0,coln[i+1]-(row-j)) =>홀수행을 다 선택하고도 1이 남는 경우 고려
//최대:minOf(j,coln[i+1]) =>1의 수가 충분하면 j개까지 선택되고 아니면 최대 1의 개수만큼 선택됨
//그렇게 짝수행에서 k개 선택시 나오는 짝수행 수 = (홀수행에서 1선택한 개수) + (짝수행에서 1 선택 안한 개수)=>coln[i+1]-k +(j-k)
//최종 경우의 수:짝수행에서 1선택 * 홀수행에서 1선택 *이전열까지의 dp경우의 수
for(i in 0..col-2){
for(j in 0..row){
if(dp[i][j]==0) continue
val oddr=row-j
val min=maxOf(0,coln[i+1]-oddr)
val max=minOf(j,coln[i+1])
for(k in min..max){
val next=coln[i+1]-k +(j-k)
val case=(c[j][k].toLong()*c[row-j][coln[i+1]-k].toLong())%mod.toLong()
dp[i+1][next]+=((dp[i][j].toLong()*case)%mod.toLong()).toInt()
}
}
}
return dp[col-1][row]
}
}
-파스칼 항등식을 이용해 조합의 결과값들을 미리 저장 핻ㅁ
-이후 풀이는 주석에 나온대로
3. 쌍둥이 빌딩 숲
1)문제
문제 설명
은비는 길을 걷다가 관광 명소인 쌍둥이 빌딩 숲을 보게 되었습니다. 쌍둥이 빌딩 숲은 일렬로 빌딩들이 줄지어 서있는 곳입니다.
쌍둥이 빌딩 숲에는 높이가 1부터 n까지 각각 2 채씩 총 2n채의 빌딩이 존재하기 때문에 그러한 이름이 붙게 되었으며, 같은 높이를 가지는 빌딩 사이에는 그보다 높은 빌딩이 존재하지 않습니다.
은비는 쌍둥이 빌딩 숲을 한쪽 측면에서(열 방향으로) 바라보고 있습니다. 이때 count 채의 빌딩이 구분되어 보였습니다.
은비의 세계는 안타깝게도 원근감이 존재하지 않지만, 다행히 서로 다른 높이를 가지는 빌딩들은 각각 고유한 색깔을 가지고 있어 어떤 빌딩이 다른 빌딩에 의해 전체가 가려지지 않는다면 볼 수 있습니다.
예를 들어 은비가 바라본 방향에서 가까운 빌딩부터 차례로 높이가 1,1,3,2,2,3 순이라면 높이가 2인 빌딩은 가려져서 보이지 않고, 높이가 1인 빌딩과 높이가 3인 빌딩만 구분되어 보입니다.
n과 count가 주어졌을 때, 빌딩들이 배치될 수 있는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
2)솔루션
class Solution {
fun solution(n: Int, count: Int): Int {
var answer: Int = 0
val dp=Array(n+1){LongArray(n+1){0}}
val mod=1000000007L
//dp[i][j]: i쌍의 빌딩을 가지고 j개의 빌딩이 보이게 하는 경우의수. i가 커질때 더 작은 빌딩을 넣는 연산
//dp[1][1]=1
//dp[i][j]가지고 dp[i+1][j],dp[i+1][j+1]만들기
//dp[i+1][j]: 맨 앞을 제외하고 아무곳이나 집어넣으면 됨(단 쌍을 붙인 상태로):dp[i][j]*2i
//dp[i+1][j+1]: 맨 앞에 두면 됨:dp[i][j]
dp[1][1]=1L
for(i in 1..n-1){
for(j in 1..i){
dp[i+1][j]+=dp[i][j]*2*i
dp[i+1][j+1]+=dp[i][j]
dp[i+1][j]%=mod
dp[i+1][j+1]%=mod
}
}
return (dp[n][count]%mod).toInt()
}
}
-큰 빌딩부터 해서 점점 작은 빌딩을 넣는 식으로 dp를 이용해 풀음
-내용은 주석에
4. 지형 이동
1)문제
문제 설명
N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.
이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.
각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.
제한사항- land는 N x N크기인 2차원 배열입니다.
- land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
- land의 원소는 각 격자 칸의 높이를 나타냅니다.
- 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
- height는 1 이상 10,000 이하인 자연수입니다.
2)솔루션
class Solution {
fun solution(land: Array<IntArray>, height: Int): Int {
var answer = 0
val n=land.size
//그룹화
//그룹별 사다리 생성
//MST구하기-kruskal
//그룹화
//visited는 방문을 체크하면서도 그룹화된 영역을 체크하는 용도로 쓰임
val visited=Array(n){IntArray(n){0}}
var gNum=1
for(i in 0..n-1){
for(j in 0..n-1){
if(visited[i][j]==0){
group(land,visited,i,j,height,n,gNum++)
}
}
}
//사다리 찾기
//visited를 순회하며 경계부분에 해당하면 사다리를 구함
val edge=mutableMapOf<HashSet<Int>,Int>() //출발지와 도착지가 담긴 set, 사다리 비용
val di=intArrayOf(0,0,1,-1)
val dj=intArrayOf(1,-1,0,0)
for(i in 0..n-1){
for(j in 0..n-1){
for(k in 0..3){
val x=i+di[k]
val y=j+dj[k]
if(x in 0..n-1&&y in 0..n-1&&visited[i][j]!=visited[x][y]){
val idx=hashSetOf(visited[i][j],visited[x][y])
val tmp=edge?.get(idx)?:Int.MAX_VALUE
edge.put(idx,minOf(tmp,Math.abs(land[i][j]-land[x][y])))
}
}
}
}
//MST구하기
//kruskal알고리즘으로 구함
//도착지와 가중치값이 들어있는 배열 생성(인덱스는 1부터 gNum-1까지)
val nodes=ArrayList<Triple<Int,Int,Int>>()
for((k,v) in edge){
val tmp=ArrayList<Int>()
for(i in k){
tmp+=i
}
nodes+=Triple(tmp[0],tmp[1],v)
nodes+=Triple(tmp[1],tmp[0],v)
}
nodes.sortBy{it.third}
var roots=IntArray(gNum){it} //인덱스가 자기 부모노드. 초기는 자기 자신이 들어가있음
var rank=IntArray(gNum){0}
for(i in nodes){
if(find(i.first,roots)==find(i.second,roots)) continue
answer+=i.third
union(i.first,i.second,roots,rank)
}
return answer
}
fun find(x:Int, roots:IntArray):Int{
var root=x
while(true){
root=roots[root]
if(root==roots[root]) break
}
return root
}
fun union(x:Int, y:Int, roots:IntArray, rank:IntArray){
val xRoot=find(x,roots)
val yRoot=find(y,roots)
if(xRoot==yRoot) return
if(rank[xRoot]<rank[yRoot]) roots[xRoot]=yRoot
else if(rank[xRoot]>rank[yRoot]) roots[yRoot]=xRoot
else{
roots[yRoot]=xRoot
rank[xRoot]++
}
}
fun group(land:Array<IntArray>,visited:Array<IntArray>,si:Int,sj:Int,height:Int,n:Int,gNum:Int){
val di=intArrayOf(0,0,1,-1)
val dj=intArrayOf(1,-1,0,0)
val stack=ArrayDeque<Pair<Int,Int>>()
stack.addFirst(Pair(si,sj))
visited[si][sj]=gNum
while(stack.isNotEmpty()){
val (ci,cj)=stack.removeFirst()
for(i in 0..3){
val x=ci+di[i]
val y=cj+dj[i]
if(x in 0..n-1&&y in 0..n-1&&visited[x][y]==0&&Math.abs(land[x][y]-land[ci][cj])<=height){
visited[x][y]=gNum
stack.addFirst(Pair(x,y))
}
}
}
}
}-DFS를 이용하여 그룹화 진행
-그룹화된 노드들을 순회하여 사다리들을 뽑아내며 그중 최단거리인 사다리만 남김
-크루스칼 알고리즘으로 MST를 구하면서 최소 사다리 비용을 구함
>코드카타 리뷰
1. 숫자를 k진수로 변환: toString(k)
2. k진수 문자열을 10진수 숫자로 변환: toInt(k)
3. 정규표현식-나중에 따로 시간내서 복습하기
'코틀린-안드로이드' 카테고리의 다른 글
| 36일차)알고리즘 문제(모음사전, 안티세포**중요!!) (0) | 2024.06.29 |
|---|---|
| 35일차)알고리즘 문제(주차요금 계산) (0) | 2024.06.28 |
| 33일차)알고리즘 문제(타겟넘버, 짝수 행 세기), 개인프로젝트 디자인 구상 (0) | 2024.06.26 |
| 32일차)알고리즘 문제(피로도), 챌린지반 강의 1회차, 추가 과제 (0) | 2024.06.25 |
| 31일차)알고리즘 문제(프로세스, 등산코스 정하기, 징검다리), 개인프로젝트 구상 (0) | 2024.06.24 |