>알고리즘 문제
1. 고고학 최고의 발견
1)문제
문제 설명
고고학자인 혜선은 오래전부터 성궤의 행방을 추적해왔습니다. 그동안 그의 연구는 주류 학자들로부터 인정받지 못했었지만, 혜선이는 포기하지 않고 조사를 계속했고 마침내 성궤의 행방을 알아내었습니다.
그러나 오래전 누군가로부터 봉인된 성궤는 특별한 잠금장치에 의해 보호되고 있었습니다. 잠금장치는 일종의 퍼즐과 연결되어 퍼즐을 해결하면 열리는 것으로 보입니다.
퍼즐은 시계들이 행렬을 이루는 구조물인데 하나의 시계에 시곗바늘은 하나씩만 있습니다. 각 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다. 시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면 그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다. 행렬의 모서리에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 세 시계의 시곗바늘들이 함께 돌아가며, 꼭짓점에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 두 시계의 시곗바늘들이 함께 돌아갑니다.
각 시계는 12시, 3시, 6시, 9시 방향 중의 한 방향을 가리키고 있습니다. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗바늘이 12시 방향을 가리키면 퍼즐이 해결되어 성궤를 봉인하고 있는 잠금장치가 열릴 것입니다.
노후화된 퍼즐 기계장치가 걱정되었던 혜선은 가능한 최소한의 조작으로 퍼즐을 해결하려고 합니다. 시곗바늘들의 행렬 clockHands가 매개변수로 주어질 때, 퍼즐을 해결하기 위한 최소한의 조작 횟수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ clockHands의 길이 ≤ 8
- clockHands는 2차원 배열이며 행과 열의 크기가 동일합니다.
- 0 ≤ clockHands의 원소 ≤ 3
- clockHands[i]의 원소들은 시곗바늘의 방향을 나타내며 0은 12시 방향, 1은 3시 방향, 2는 6시 방향, 3은 9시 방향을 나타냅니다.
- 해결 가능한 퍼즐만 주어집니다.
2) 솔루션
class Solution {
fun solution(clockHands: Array<IntArray>): Int {
var answer: Int = 0
val n=clockHands.size
var min=Int.MAX_VALUE
val rot=IntArray(n){0} //회전체크
while(true){
val copy=copy(clockHands)
var rotNum=0
//rot로 첫줄회전
for(i in rot.indices){
rotation(copy,0,i,rot[i])
rotNum+=rot[i]
}
//아래 줄들 회전
for(i in 1..n-1){
for(j in 0..n-1){
val rotTmp=(4-copy[i-1][j])%4
rotation(copy,i,j,rotTmp)
rotNum+=rotTmp
}
}
//맨아랫줄이 모두 0이면 min갱신
if(copy[n-1].average()==0.0) min=minOf(min,rotNum)
//rot끝 여부 체크 후 갱신
if(rot.average()==3.0) break
var idx=0
while(true){
rot[idx]+=1
if(rot[idx]==4){
rot[idx++]=0
}else{
break
}
}
}
return min
}
fun copy(arr:Array<IntArray>):Array<IntArray>{
val tmp=Array(arr.size){IntArray(arr.size){0}}
for(i in arr.indices){
for(j in arr[0].indices){
tmp[i][j]=arr[i][j]
}
}
return tmp
}
fun rotation(arr:Array<IntArray>,x:Int,y:Int,n:Int){
try{
arr[x][y]+=n
arr[x][y]%=4
}catch(e:Exception){}
try{
arr[x+1][y]+=n
arr[x+1][y]%=4
}catch(e:Exception){}
try{
arr[x-1][y]+=n
arr[x-1][y]%=4
}catch(e:Exception){}
try{
arr[x][y+1]+=n
arr[x][y+1]%=4
}catch(e:Exception){}
try{
arr[x][y-1]+=n
arr[x][y-1]%=4
}catch(e:Exception){}
}
}-특정 칸의 회전에 대해 인접칸의 회전수가 종속적으로 결정됨
-때문에 모서리 한줄을 골라 임의로 회전시키고 시작하면 해당줄을 12시방향으로 정렬시키기위해 그 다음줄의 회전수가 결정됨.
-마찬가지로 그 다음줄도 임.
-위의 방식으로 반복해서 내려가 마지막줄이 12시방향으로 정렬되는 경우의 수중 가장 조작횟수가 적은것을 고르면 됨
2. n + 1 카드게임
1)문제
당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다.
- 처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다.
- 게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.
- 카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.
예를 들어 n = 12, coin = 4이고 [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4] 순서대로 카드를 뽑도록 카드 뭉치가 섞여 있습니다.
처음에 3, 6, 7, 2 카드 4장(= n/3)과 동전 4개(= coin)를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13(= n+1)입니다. 다음과 같은 방법으로 최대 5라운드까지 도달할 수 있습니다.
- 1라운드에서 뽑은 카드 1, 10을 동전 두 개를 소모해서 모두 가집니다. 카드 3, 10을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2, 6, 7이고 동전이 2개 남습니다.
- 2라운드에서 뽑은 카드 5, 9를 동전을 소모하지 않고 모두 버립니다. 카드 6, 7을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2고 동전이 2개 남습니다.
- 3라운드에서 뽑은 카드 8, 12 중 동전 한 개를 소모해서 카드 12를 가집니다. 카드 1, 12을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 2이고 동전이 1개 남습니다.
- 4라운드에서 뽑은 카드 11, 4 중 동전 한 개를 소모해서 카드 11을 가집니다. 카드 2, 11을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드와 동전은 없습니다.
- 5라운드에서 카드 뭉치에 남은 카드가 없으므로 게임을 종료합니다.
처음에 가진 동전수를 나타내는 정수 coin과 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards가 매개변수로 주어질 때, 게임에서 도달 가능한 최대 라운드의 수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 0 ≤ coin ≤ n
- 6 ≤ cards의 길이 = n < 1,000
- cards[i]는 i+1번째로 뽑는 카드에 적힌 수를 나타냅니다.
- 1 ≤ cards[i] ≤ n
- cards의 원소는 중복되지 않습니다.
- n은 6의 배수입니다.
2)솔루션
class Solution {
fun solution(coin: Int, cards: IntArray): Int {
var answer: Int = 0
val n=cards.size
var coins=coin
var idx=n/3-1
//initset 초기화후 pair 수와 unpairedset을 남겨둠
//뽑은 카드는 picked에 넣음
//매 라운드마다 picked에 카드 두장씩을 넣으면서 비교 없으면 종료
//코인 2개이상일때 unpaired와 쌍을 이루는 카드가 두장이상 있으면 추가
//코인 1개 이상일때 unpaired와 쌍을 이루는 카드가 한장이상 있으면 추가
//코인이 2개이상인데 pair가 0이면 picked에서 쌍을 이루는 2장 가져와서 pair 1상승
//이후 pair체크 후 1감소시키고 다음라운드. 감소시킬값이 없으면 종료
val unpaired=hashSetOf<Int>()
for(i in 0..n/3-1){
unpaired.add(cards[i])
}
var pair=0
val removed=hashSetOf<Int>()
for(i in unpaired){
for(j in unpaired){
if(i>=j) continue
if(n+1-i==j){
removed.add(i)
removed.add(j)
++pair
}
}
}
var round=0
//picked와 unpaired를 미리 체크해서 페어해두는것
//매번 picked전체와 unpaired전체를 비교할필요 없이 비교 수를 최소화함.
var pickedpaired=0
val picked=hashSetOf<Int>()
while(true){
println("${round}/${pair}")
++round
if(idx==n-1){
break
}
repeat(2) {
val tmp=cards[++idx]
var remove=0 //0은 없는 원소니깐 제거시도시 문제 없음
for(i in unpaired){
if(n+1-tmp==i){
remove=i
pickedpaired++
break
}
}
if(remove==0){
picked.add(tmp)
}else{
unpaired.remove(remove)
}
}
if(coins>=2){
if(pickedpaired>=2){
pickedpaired-=2
pair++
coins-=2
continue
}
}
if(coins>=1){
if(pickedpaired>=1){
pickedpaired--
coins--
continue
}
}
if(coins>=2&&pair==0){
val removed=hashSetOf<Int>()
var flag=false
for(i in picked){
for(j in picked){
if(i>=j) continue
if(n+1-i==j){
removed.add(i)
removed.add(j)
flag=true
break
}
}
if(flag) {
break
}
}
if(flag){
picked.removeAll(removed)
coins-=2
continue
}
}
if(pair==0) break
pair--
}
return round
}
}
3. 귤 고르기
1)문제
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
- 1 ≤ tangerine의 원소 ≤ 10,000,000
2)솔루션
class Solution {
fun solution(k: Int, tangerine: IntArray): Int {
var answer: Int = 0
var cur=0
var lists=hashMapOf<Int,Int>()
for(i in tangerine){
if(lists[i]!=null){
lists[i]=lists[i]!!.plus(1)
}else{
lists.put(i,1)
}
}
var valueList=lists.values.toList().sortedDescending()
var total=0
for(i in valueList){
total+=i
answer++
if(total>=k) break
}
return answer
}
}-귤을 크기를 키로하는 맵에 집어넣음
-맵의 값 리스트를 뽑아내 숫자가 큰 순서대로 넣어서 종류가 최소가 되게 한다.
4. 괄호 회전하기
1)문제
문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
- 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- s의 길이는 1 이상 1,000 이하입니다.
2)솔루션
class Solution {
fun solution(s: String): Int {
var answer: Int = 0
val max=s.length
var deque=ArrayDeque<Char>()
for(i in s){
deque.addLast(i)
}
repeat(max){
deque.addLast(deque.removeFirst())
if(check(deque)){
answer++
}
}
return answer
}
fun check(deque:ArrayDeque<Char>):Boolean{
val stack=ArrayDeque<Char>()
for(i in 0..deque.size-1){
if(stack.isEmpty()){
stack.addFirst(deque[i])
continue
}
val tmp=stack[0]
if(tmp=='('&&deque[i]==')') stack.removeFirst()
else if(tmp=='['&&deque[i]==']') stack.removeFirst()
else if(tmp=='{'&&deque[i]=='}') stack.removeFirst()
else stack.addFirst(deque[i])
}
if(stack.isEmpty()) return true
else return false
}
}-스택을 이용
-스택에 여는 괄호를 넣다가 맨위 원소가 짝이 맞는 닫는 괄호가 만나면 스택에서 빠져나옴.
-이 과정을 반복했을때 모든 괄호를 순회 후 스택이 비어있으면 옳고 아니면 틀린것임을 이용
'코틀린-안드로이드' 카테고리의 다른 글
| 26일차)알고리즘 문제(연속 펄스 부분 수열의 합, 산 모양 타일, 상담원 인원, n^2 배열 자르기), 입문 강의 4주차, 개인과제-로그인 앱 만들기 (0) | 2024.06.19 |
|---|---|
| 25일차)알고리즘 문제(연속 부분 수열 합의 개수, H-Index, 인사고과), 입문 강의 1~3주차 (0) | 2024.06.18 |
| 23일차)알고리즘 문제(멀리 뛰기, 에어컨, 아방가르드 타일링, 숫자 타자 대회) (1) | 2024.06.14 |
| 22일차)알고리즘 문제(N개의 최소공배수), 복습(배열생성, ArrayDeque,repeat,forEachIndexed) 개인과제(키오스크) (1) | 2024.06.13 |
| 21일차)알고리즘 문제(예상 대진표), 복습 및 과제 피드 (0) | 2024.06.12 |