>알고리즘 문제
1. 행렬의 곱셈
1)문제
2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.
제한 조건- 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
- 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
- 곱할 수 있는 배열만 주어집니다.
2)솔루션
class Solution {
fun solution(arr1: Array<IntArray>, arr2: Array<IntArray>): Array<IntArray> {
var answer = arrayOf<IntArray>()
for(i in arr1.indices){
var arr=intArrayOf()
for(j in arr2[0].indices){
var tmp=0
for(k in arr1[i].indices){
tmp+=arr1[i][k]*arr2[k][j]
}
arr+=tmp
}
answer+=arr
}
return answer
}
}
2. 표 병합
문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.
위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.
- "UPDATE r c value"
- (r, c) 위치의 셀을 선택합니다.
- 선택한 셀의 값을 value로 바꿉니다.
- "UPDATE value1 value2"
- value1을 값으로 가지고 있는 모든 셀을 선택합니다.
- 선택한 셀의 값을 value2로 바꿉니다.
- "MERGE r1 c1 r2 c2"
- (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
- 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
- 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
- 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
- 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
- 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
- "UNMERGE r c"
- (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
- 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
- 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
- "PRINT r c"
- (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
- 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.
아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.
commands효과
| UPDATE 1 1 menu | (1,1)에 "menu" 입력 |
| UPDATE 1 2 category | (1,2)에 "category" 입력 |
| UPDATE 2 1 bibimbap | (2,1)에 "bibimbap" 입력 |
| UPDATE 2 2 korean | (2,2)에 "korean" 입력 |
| UPDATE 2 3 rice | (2,3)에 "rice" 입력 |
| UPDATE 3 1 ramyeon | (3,1)에 "ramyeon" 입력 |
| UPDATE 3 2 korean | (3,2)에 "korean" 입력 |
| UPDATE 3 3 noodle | (3,3)에 "noodle" 입력 |
| UPDATE 3 4 instant | (3,4)에 "instant" 입력 |
| UPDATE 4 1 pasta | (4,1)에 "pasta" 입력 |
| UPDATE 4 2 italian | (4,2)에 "italian" 입력 |
| UPDATE 4 3 noodle | (4,3)에 "noodle" 입력 |
위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.
아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.
commands효과
| MERGE 1 2 1 3 | (1,2)와 (1,3) 병합 |
| MERGE 1 3 1 4 | (1,3)과 (1,4) 병합 |
위 명령어를 실행하면 아래와 같은 상태가 됩니다.
병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.
아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.
commands효과
| UPDATE korean hansik | "korean"을 "hansik"으로 변경 |
| UPDATE 1 3 group | (1,3) 위치의 셀 값을 "group"으로 변경 |
위 명령어를 실행하면 아래와 같은 상태가 됩니다.
아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.
commands효과
| UNMERGE 1 4 | 셀 병합 해제 후 원래 값은 (1,4)가 가짐 |
위 명령어를 실행하면 아래와 같은 상태가 됩니다.
실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ commands의 길이 ≤ 1,000
- commands의 각 원소는 아래 5가지 형태 중 하나입니다.
- "UPDATE r c value"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
- "UPDATE value1 value2"
- value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
- "MERGE r1 c1 r2 c2"
- r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- "UNMERGE r c"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- "PRINT r c"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- "UPDATE r c value"
- commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.
2)솔루션
class Solution {
fun solution(commands: Array<String>): Array<String> {
var answer: Array<String> = arrayOf<String>()
val nodes=ArrayList<ArrayList<Node>>()
for(i in 0..50){
val arr=ArrayList<Node>()
for(j in 0..50){
arr+=Node(i,j)
}
nodes+=arr
}
for(i in commands){
val command=i.split(" ")
when(command[0]){
"UPDATE" -> run{
if(command.size==4){
update1(nodes,command[1].toInt(),command[2].toInt(),command[3])
}else{
update2(nodes,command[1],command[2])
}
}
"MERGE" -> run{
merge(nodes,command[1].toInt(),command[2].toInt(),command[3].toInt(),command[4].toInt())
}
"UNMERGE" -> run{
unmerge(nodes,command[1].toInt(),command[2].toInt())
}
else -> run{
answer+=prints(nodes,command[1].toInt(),command[2].toInt())
}
}
}
return answer
}
fun update1(nodes:ArrayList<ArrayList<Node>>,r:Int,c:Int,values:String?){
var cur=nodes[r][c]
while(cur!=cur.head){
cur=cur.head
}
cur.value=values
}
fun update2(nodes:ArrayList<ArrayList<Node>>,value1:String?, value2:String?){
for(i in 1..50){
for(j in 1..50){
//어차피 전체 탐색이라 최상단 헤드도 자동 탐색되므로 타고올라갈필요 없음
if(nodes[i][j].value==value1){
nodes[i][j].value=value2
}
}
}
}
fun merge(nodes:ArrayList<ArrayList<Node>>,r1:Int,c1:Int,r2:Int,c2:Int){
//최상단 끼리 비교하여 r1 c1위치의 값을 정함
//r1 c1의 최하단에 r2 c2를 붙임
var cur1=nodes[r1][c1]
var cur2=nodes[r2][c2]
while(cur1!=cur1.head){
cur1=cur1.head
}
while(cur2!=cur2.head){
cur2=cur2.head
}
if(cur1==cur2) return
if(cur1.value==null){
cur1.value=cur2.value
}
while(cur1!=cur1.tail){
cur1=cur1.tail
}
cur1.tail=cur2
cur2.head=cur1
}
fun unmerge(nodes:ArrayList<ArrayList<Node>>,r:Int,c:Int){
var fix=nodes[r][c]
var cur=fix
while(cur!=cur.head){
cur=cur.head
}
val tmpValue=cur.value
while(cur!=cur.tail){
cur.value=null
cur.head=cur
cur=cur.tail
cur.head.tail=cur.head
}
cur.value=null
cur.head=cur
cur=cur.tail
cur.head.tail=cur.head
fix.value=tmpValue
}
fun prints(nodes:ArrayList<ArrayList<Node>>,r:Int,c:Int):String{
var cur=nodes[r][c]
while(cur!=cur.head){
cur=cur.head
}
if(cur.value==null){
return "EMPTY"
}else{
return cur.value as String
}
}
}
class Node(val x:Int, val y:Int){
var value:String?=null
var head:Node=this
var tail:Node=this
}-head tail을 두어 표 병합시 기준이 되는 값의 최하단 tail에 다른 하나를 붙이는 식으로 표현
-특정셀 접근시 최상단 head로 타고 올라가는식
3. 표현 가능한 이진트리
1)문제
문제 설명
당신은 이진트리를 수로 표현하는 것을 좋아합니다.
이진트리를 수로 표현하는 방법은 다음과 같습니다.
- 이진수를 저장할 빈 문자열을 생성합니다.
- 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
- 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
- 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
- 문자열에 저장된 이진수를 십진수로 변환합니다.
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
다음은 이진트리를 수로 표현하는 예시입니다.
주어진 이진트리는 다음과 같습니다.
주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.
노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.
당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.
이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ numbers의 길이 ≤ 10,000
- 1 ≤ numbers의 원소 ≤ 1015
2)솔루션
class Solution {
fun solution(numbers: LongArray): IntArray {
var answer: IntArray = intArrayOf()
for(i in numbers){
answer+=if(check(i)) 1 else 0
}
return answer
}
fun check(n:Long):Boolean{
val str=java.lang.Long.toBinaryString(n).reversed()
var num=n
//println("스트링"+str)
//1일때는 return true
if(n==1L) return true
val queue=ArrayDeque<Pair<Int,Int>>() //인덱스, 높이
val height=height(num).toInt()
//println("${n}: 높이:${height}")
var mid=1
repeat(height-1){mid*=2}
if(mid>str.length) return false
queue.addLast(Pair(mid,height))
while(queue.isNotEmpty()){
val cur=queue.removeFirst()
if(cur.second==1) continue
var pow=1
repeat(cur.second-2){pow*=2}
val front=cur.first+pow
val back=cur.first-pow
val curValue=if(cur.first>str.length) '0' else str[cur.first-1]
val frontValue=if(front>str.length) '0' else str[front-1]
val backValue=if(back>str.length) '0' else str[back-1]
//println(curValue)
if(curValue=='0'){
if(frontValue=='1'||backValue=='1'){
return false
}
}
queue.addLast(Pair(front,cur.second-1))
queue.addLast(Pair(back,cur.second-1))
}
return true
}
fun height(num:Long):Long{
var tmp=num
var idx=0L
while(tmp!=1L){
tmp/=2L
++idx
}
++idx
var idxx=0L
while(idx!=1L){
idx/=2L
++idxx
}
return idxx+1
}
}-높이는 값이 t 라 할시 높이 n에 대하여 2^(2^(n-1)-1)<= t < 2^(2^n -1)임을 이용해서 구하면 된다.
-포화 이진 트리를 만들었을시 중앙값의 인덱스는 2^(n-1)이고 높이 n의 노드에 대해 자식노드 인덱스는 2^(n-2)만큼 더하거나 뺀 값
-위 사실들을 이용하여 최상단 루트노드부터 순차적으로 내려가며 루트노드가0인데 자식노드에 1이 있는 경우를 체크해서 있으면 안 만들어짐을 확인할 수 있다.
4. 부대 복귀
1)문제
문제 설명
문제 설명
강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.
강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.
제한사항- 3 ≤ n ≤ 100,000
- 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
- 2 ≤ roads의 길이 ≤ 500,000
- roads의 원소의 길이 = 2
- roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
- 동일한 정보가 중복해서 주어지지 않습니다.
- 동일한 [a, b]가 중복해서 주어지지 않습니다.
- [a, b]가 있다면 [b, a]는 주어지지 않습니다.
- 1 ≤ sources의 길이 ≤ 500
- 1 ≤ sources[i] ≤ n
- 1 ≤ destination ≤ n
2)솔루션
class Solution {
fun solution(n: Int, roads: Array<IntArray>, sources: IntArray, destination: Int): IntArray {
var answer: IntArray = intArrayOf()
val road=Array<HashSet<Int>>(n+1){hashSetOf<Int>()}
for(i in roads){
road[i[0]].add(i[1])
road[i[1]].add(i[0])
}
val queue=ArrayDeque<Int>()
val costs=IntArray(n+1){500000}
val ends=hashSetOf<Int>()
for(i in sources){
ends.add(i)
}
costs[destination]=0
queue.addLast(destination)
while(queue.isNotEmpty()){
val cur=queue.removeFirst()
val tmp=1+costs[cur]
for(i in road[cur]){
if(tmp<costs[i]){
costs[i]=tmp
queue.addLast(i)
}
}
}
for(i in sources){
val tmp=costs[i]
answer+=if(tmp==500000) -1 else tmp
}
return answer
}
}-일반적인 다익스트라로 풀려고 하면 코스트값이 최소인 노드를 찾는 과정에서 시간초과가 나기 때문에 bfs로 풀었다.
'코틀린-안드로이드' 카테고리의 다른 글
| 29일차)알고리즘 문제(의상, 미로 탈출 명령어, 2차원 동전 뒤집기) (0) | 2024.06.22 |
|---|---|
| 28일차)알고리즘 문제(할인 행사) (0) | 2024.06.21 |
| 26일차)알고리즘 문제(연속 펄스 부분 수열의 합, 산 모양 타일, 상담원 인원, n^2 배열 자르기), 입문 강의 4주차, 개인과제-로그인 앱 만들기 (0) | 2024.06.19 |
| 25일차)알고리즘 문제(연속 부분 수열 합의 개수, H-Index, 인사고과), 입문 강의 1~3주차 (0) | 2024.06.18 |
| 24일차)알고리즘 문제(고고학 최고의 발견, n + 1 카드게임, 귤 고르기, 괄호 회전하기) (1) | 2024.06.16 |