>알고리즘 문제
1.의상
1)문제
문제 설명
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
종류이름| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
- 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
- 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
- 코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
2)솔루션
class Solution {
fun solution(clothes: Array<Array<String>>): Int {
var answer = 1
val map = hashMapOf<String,ArrayList<String>>()
for(i in clothes){
if(!map.keys.contains(i[1])){
map.put(i[1],ArrayList<String>())
}
map[i[1]]?.add(i[0])
}
for((key,value) in map){
answer*=value.size+1
}
return answer-1
}
}-의상을 종류별로 나누어 맵에 저장.
-모두 안 입는 것을 제외하고 종류별로 안입거나 하나씩 골라입을 수 있으므로 종류별 의상수 +1을 곱연산 후 아무것도 안입는 1을 빼서 구한다.
2. 미로탈출 명령어
1)문제
문제 설명
n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.
- 격자의 바깥으로는 나갈 수 없습니다.
- (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
- 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
- l: 왼쪽으로 한 칸 이동
- r: 오른쪽으로 한 칸 이동
- u: 위쪽으로 한 칸 이동
- d: 아래쪽으로 한 칸 이동
예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.
미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.
예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.
....
..S.
E...
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.
탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.
- lldud
- ulldd
- rdlll
- dllrl
- dllud
- ...
이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.
격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.
제한사항
- 2 ≤ n (= 미로의 세로 길이) ≤ 50
- 2 ≤ m (= 미로의 가로 길이) ≤ 50
- 1 ≤ x ≤ n
- 1 ≤ y ≤ m
- 1 ≤ r ≤ n
- 1 ≤ c ≤ m
- (x, y) ≠ (r, c)
- 1 ≤ k ≤ 2,500
2)솔루션
class Solution {
fun solution(n: Int, m: Int, x: Int, y: Int, r: Int, c: Int, k: Int): String {
var answer: String = ""
if((k-Math.abs(x-r)-Math.abs(y-c))%2!=0||k<Math.abs(x-r)+Math.abs(y-c)) return "impossible"
val dulr=intArrayOf(0,0,0,0)
if(x<r) dulr[0]=r-x else dulr[1]=x-r
if(y<c) dulr[3]=c-y else dulr[2]=y-c
var cost=k
var curx=x
var cury=y
//최소움직임만큼 미리 제거. 최소움직임만큼 움직일때는 코스트 제거x
cost-=dulr[0]+dulr[1]+dulr[2]+dulr[3]
//일단 도착지만큼 d를 움직임
curx+=dulr[0]
repeat(dulr[0]){
answer+="d"
}
//추가로 남는 코스트에서 최소 lr을 움직일 코스트와 u 움직일 코스트를 제외
//그 후 남은 코스트에서 절반과 바닥에 닿는 n-curx중 더 작은 값만큼 간다.
var distD=minOf(cost/2,n-curx)
curx+=distD
cost-=distD
repeat(distD){
answer+="d"
}
cost-=distD //u움직임 미리 빼둠
//일단 도착지 위치까지 만큼 l을 움직임
cury-=dulr[2]
repeat(dulr[2]){
answer+="l"
}
//우선 우측에 가야할 코스트를 제외해둠
//이후 남은 코스트에서 절반과 벽에 닿는 cury-1중 더 작은값만큼 간다.
var distL=minOf(cost/2,cury-1)
cury-=distL
cost-=distL
repeat(distL){
answer+="l"
}
cost-=distL //r 가야하는 부분 미리 빼줌
//최종적으로 남은 코스트만큼 rl을 반복
repeat(cost/2){
answer+="rl"
}
//우측 추가
while(cury!=c){
answer+="r"
cury++
}
//상단 추가
while(curx!=r){
answer+="u"
curx--
}
return answer
}
}-불가능 부터 체크후 시작
<1>최단거리로 부터 한칸이라도 벗어나면 돌아오는데 똑같은 거리를 움직여야 하므로 총 이동거리에 최단거리를빼면 2의 배수가 나와야 한다. 아니면 불가능
<2>총 이동거리가 최단거리보다 적어도 도착 불가능
-상, 하, 좌, 우에 해당하는 최소 필요 거리를 집어넣는다: 출발부터 도착까지 최단거리로 이동하는동안 드는 코스트를 집어넣음
-우선 총 거리에서 최소 필요 거리들을 빼고 시작. 추후 해당되는 움직임을 할때는 코스트에서 빼주지 않는다.
-우선 사전순으로 가장 우선인 down부터 계산
<1>우선 최소 필요 거리만큼 움직임: 코스트는 앞서 미리 빼두었으므로 놔둠
<2>최대한 움직일 수 있는만큼 d를 움직임: 벽에 닿는 코스트와 갔다가 돌아올수 있을만큼 남기는 코스트중 더 작은것을 선택
=>갔다가 돌아올 수 있는 코스트가 minOf(n-curx,cost/2)인 이유: 첫번째로 n-curx는 벽에 닿는 경우. 두번째로 cost/2는 d로 갔으니 u로 돌아올 코스트만 고려한 결과. 왜 그러냐면 최소 필요거리는 미리 빼두었으니 d로 갔다가 u로 돌아올만큼만 남겨두면 나머지 u l r 최소 필요거리만큼 움직여서 도착지로 갈 수 있음.
<3>d로 움직인 거리인 distD를 cost에서 빼줌
<4>d로 간만큼 u로돌아올것이니 distD만큼 또 다시 cost에서 빼둠
<5>이러면 cost로 남는것은 l과 r로 움직이는 코스트(최소거리를 제외한)
<6>l로 최소거리 만큼 움직임: 코스트는 미리 빼주었으니 그대로 둠
<7>l로 갈 수 있는만큼 움직임: 벽에 닿거나 돌아올 거리를 고려(d와 같은 원리)
<8>l로 움직인 거리인 distL을 빼줌
<9>r로 돌아올 거리인 distL을 한번 더 빼줌
<10>최종적으로 남은 cost는 경우:l로 벽에 닿는 경우인데 이때 l로는 더 못가니 rl을 반복하여 제자리서 움직이며 남은 코스트를 전부 소모
<11>이제 r과 u로 순서대로 움직여서 도착지로 감
3. 2차원 동전 뒤집기
1)문제
문제 설명
한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.
예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.
직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.
제한사항
- 1 ≤ beginning의 길이 = target의 길이 ≤ 10
- 1 ≤ beginning[i]의 길이 = target[i]의 길이 ≤ 10
- beginning[i][j]와 target[i][j]는 i + 1행 j + 1열의 동전의 상태를 나타내며, 0 또는 1의 값으로 주어집니다.
- 0은 동전의 앞면을, 1은 동전의 뒷면을 의미합니다.
2)솔루션
class Solution {
fun solution(b: Array<IntArray>, t: Array<IntArray>): Int {
var answer: Int = 0
var min=21
val rcCheck=IntArray(b.size+b[0].size){0}
if(check(b,t)) return 0
while(addOne(rcCheck)){
var cnt=0
//i 행 뒤집기
val k=copy(b)
for(i in 0..b.size-1){
if(rcCheck[i]==1){
rowOp(k,i)
++cnt
}
}
//i 열 뒤집기
for(i in 0..b[0].size-1){
if(rcCheck[i+b.size]==1){
colOp(k,i)
++cnt
}
}
if(check(k,t)){
min=minOf(min,cnt)
}
}
if(min==21) min=-1
return min
}
fun copy(b:Array<IntArray>):Array<IntArray>{
val new=Array<IntArray>(b.size){IntArray(b[0].size){0}}
for(i in b.indices){
for(j in b[0].indices){
new[i][j]=b[i][j]
}
}
return new
}
//끝나면 false
fun addOne(arr:IntArray):Boolean{
var idx=0
while(true){
if(idx==arr.size) return false
if(arr[idx]==0){
arr[idx]=1
break
}else{
arr[idx]=0
++idx
}
}
return true
}
fun check(arr:Array<IntArray>, t:Array<IntArray>):Boolean{
for(i in arr.indices){
for(j in arr[0].indices){
if(arr[i][j]!=t[i][j]) return false
}
}
return true
}
fun rowOp(arr:Array<IntArray>, r:Int){
for(i in 0..arr[r].size-1){
if(arr[r][i]==0) arr[r][i]=1 else arr[r][i]=0
}
}
fun colOp(arr:Array<IntArray>, c:Int){
for(i in 0..arr.size-1){
if(arr[i][c]==0) arr[i][c]=1 else arr[i][c]=0
}
}
}
-어느 행이나 열을 먼저 뒤집는지 순서는 결과에 영향을 주지 않음
-뒤집기를 두번하면 원상복귀되므로 한번 이하로만 뒤집는 경우를 고려하면 됨.
-즉 모든 행 열에 대하여 뒤집거나 안뒤집거나를 고려해서 경우의수를 체크하면 된다.
'코틀린-안드로이드' 카테고리의 다른 글
| 31일차)알고리즘 문제(프로세스, 등산코스 정하기, 징검다리), 개인프로젝트 구상 (0) | 2024.06.24 |
|---|---|
| 30일차)알고리즘 문제(기능개발, 카운트 다운) (0) | 2024.06.23 |
| 28일차)알고리즘 문제(할인 행사) (0) | 2024.06.21 |
| 27일차)알고리즘 문제(행렬의 곱셈, 표 병합, 표현 가능한 이진트리, 부대복귀) (0) | 2024.06.20 |
| 26일차)알고리즘 문제(연속 펄스 부분 수열의 합, 산 모양 타일, 상담원 인원, n^2 배열 자르기), 입문 강의 4주차, 개인과제-로그인 앱 만들기 (0) | 2024.06.19 |