>알고리즘 문제
1. 섬 연결하기
1)문제
문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
제한사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는 ((n-1) * n) / 2이하입니다.
- 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
2)솔루션
class Solution {
fun solution(n: Int, costs: Array<IntArray>): Int {
var answer = 0
//MST
val arr = Array(n){ArrayList<Pair<Int,Int>>()} //v1:v2,cost
for(i in costs){
arr[i[0]]+=Pair(i[1],i[2])
arr[i[1]]+=Pair(i[0],i[2])
}
val vertex=HashSet<Int>()
vertex+=0
while(vertex.size!=n){
var min=Int.MAX_VALUE
var minNode=0
for(i in vertex){
for((node,cost) in arr[i]){
if(!vertex.contains(node)&&cost<min){
minNode=node
min=cost
}
}
}
vertex+=minNode
answer+=min
}
return answer
}
}-MST구하는 방식으로 풀이
2. 조이스틱
1)문제
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한 사항
- name은 알파벳 대문자로만 이루어져 있습니다.
- name의 길이는 1 이상 20 이하입니다.
2)솔루션
class Solution {
fun solution(name: String): Int {
var answer = 0
answer+=Alpha(name)
answer+=Move(name)
return answer
}
fun Alpha(name:String):Int{
var total = 0
for(i in name){
total+=minOf(i.toInt() - 'A'.toInt(), 'Z'.toInt() - i.toInt() + 1)
}
return total
}
fun Move(name:String):Int{
val q=ArrayDeque<Node>()
val initCheck=BooleanArray(name.length){false}
for(i in name.indices){
if(name[i]=='A') initCheck[i]=true
}
q.addLast(Node(0,0,initCheck))
var min=Int.MAX_VALUE
while(q.isNotEmpty()){
val cur=q.removeFirst()
if(!cur.check.contains(false)){
min=minOf(min,cur.total)
continue
}
var left=0
var idxl=0
while(true){
idxl=cur.cur -left
if(idxl<0) idxl+=name.length
if(!cur.check[idxl]) break
left++
}
var right=0
var idxr=0
while(true){
idxr=cur.cur + right
if(idxr>=name.length) idxr-=name.length
if(!cur.check[idxr]) break
right++
}
val node1 = Node(idxl,left+cur.total,cur.check.copyOf().apply{this[idxl]=true})
val node2 = Node(idxr,right+cur.total,cur.check.copyOf().apply{this[idxr]=true})
q.addLast(node1)
q.addLast(node2)
}
return min
}
}
data class Node(val cur:Int, var total:Int, var check:BooleanArray)-알파벳 변경 횟수와 움직임 횟수를 각각 구해서 더하는 방식으로 풀이
-움직임은 BFS를 이용
3. N으로 표현
1)문제
문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
2)솔루션
class Solution {
fun solution(N: Int, number: Int): Int {
var answer = 0
val dp = Array(9){HashSet<Int>()}
//초기화
var tmp = N
for(i in 1..8){
dp[i]+=tmp
tmp=10*tmp+N
}
if(number==N) return 1
for(i in 2..8){
var prev=1
while(prev<i){
for(j in dp[prev]){
for(k in dp[i-prev]){
dp[i]+=j+k
dp[i]+=j-k
dp[i]+=j*k
if(k!=0) dp[i]+=j/k
}
}
prev++
}
if(dp[i].contains(number)) return i
}
return -1
}
}-사용횟수가 1인것부터 시작해 8회인것까지 순차적으로 구함
-n회인것은 1 과 n-1, 2와 n-2, ... , n-1과 1의 조합으로 사칙연산을 해서 구하였다.
-각 루프마타 number가 나왔는지 체크해서 결과값 반환
>개인 공부
1. Result 에러 핸들링
1)용도: 결과 값을 받아서 exception 발생 여부를 체크
2)사용 메소드와 프로퍼티
-isSuccess: 성공여부
-isFailure: 실패 여부
-getOrNull(): exception이 발생하지 않으면 해당값, 아니면 null
-exceptionOrNull(): exception이 발생하면 해당 exception, 아니면 null
3)Recover: 에러케이스 별로 원하는 결과값을 지정할 수 있다.
4)예시
fun login(userName: String) {
viewModelScope.launch {
val userStatus = runCatching {
repository.requestUserStatus(userName)
}.onSuccess { userStatus ->
// ..
}.onFailure { error ->
// ..
}.recover { error ->
return@recover when(error) {
is ABCException -> "ABC"
// ...
else -> "STATUS_UNKNOWN"
}
}
}
}
//recover에서 when을 사용하지 않고 그냥 error -> "STATUS_UNKWON" 처럼도 가능
5)코루틴과 사용시 주의점:
-코루틴이 suspend지점에서 재개되기 전에 취소여부 확인
=>취소되었다면 Exception이 뜨면서 catch해 버리기때문에 suspend지점 이후 나머지 코루틴이 실행되지않음
예시)
class DataPresenter(
private val coroutineScope: CoroutineScope,
private val provider: DataProvider,
private val view: View
) {
fun load() {
coroutineScope.launch {
view.showProgressBar()
val data = runCatching {
provider.loadFromDB() // suspend function
}.getOrNull()
view.hidProgressBar()
data?.let { view.display(it) }
?: run { view.showError() }
}
}
fun onUserCancel() { // onBackPressed
coroutineScope.coroutineContext.cancel()
}
}-데이터 로드중 뒤로가기를 눌러 코루틴이 취소되면 suspend에서 재개시 Exception확인 후 실행 중단됨
6)사용법: runCatching으로 특정값을 할당하는 동작을 하고자 하면 타입을 Result<~>로 묶어준다.
-예시:
val statusResult: Result<String> = runCatching {
repository.userStatusNetworkRequest(userName)
}.onSuccess { status ->
// ..
}.onFailure { error ->
// ..
}.recover { error ->
"STATUS_UNKNOWN"
}-여기서 값을 빼내려면 getOrNull()
-성공여부를 체크하려면 isSuccess나 isFailure사용
2. UI State Pattern
1)방법: 뷰모델에서 데이터 처리상태에 따라서 State를 view에 전달해서 어떤 화면을 보여줄지 결정
2)구현방법:
<1>sealed class로 상태를 나눔
<2>뷰모델에서 데이터 처리결과에 따라 상태와 데이터를 Sealed class로 보냄(livedata나 stateflow로)
<3>뷰에서는 해당 값을 받을때마다 UI State에 따라 다르게 화면을 보여준다.
3. submitList할때 참조값이 같은 list를 넣으면 diffUtil에서 비교가 제대로 일어나지 않음
=>리스트를 넣어줄때 list.toList()로 새로운 참조값을 가지는 리스트를 넣어줘야 갱신이 됨.
4. LiveData는 구독전의 값은 못받음. 반면 stateflow는 구독하기전에 설정된 최신값은 받아올 수 있음
=>예시로
_result.value=1
_result.value=2
이런식으로 연속적으로 보내면 순차처리하는게 아니라 2만 받아들임
5. sharedPreference의 CRUD는 기본적으로 동기적으로 처리된다.
=>즉 읽기함수와 쓰기함수를 순차적으로 적으면 처리도 순차적으로 진행
=>처리는 메인 Thread에서 진행되므로 필요에 따라(큰 데이터를 다루는 경우) 비동기 처리작업을 할 필요도 있다
6. coroutineScope와 CoroutineScope의 차이:
1)coroutineScope
-상위 코루틴 스코프가 있을때 사용
-새로운 코루틴 스코프를 생성=> context는 상위 코루틴 스코프를 받음:예를 들어 상위가 Dispatchers.IO면 자신도 Dispatchers.IO가 된다.
-수명은 블록내 작업이 모두 종료될때까지
-역할: 일시중단 함수-블록내 작업이 종료될때까지 속해있는 코루틴을 멈춰놓음
코루틴 병렬처리: deffered객체를 각각 만들어둔뒤 나중에 await를써야 병렬처리됨. 생성과 동시에 await를 쓰면 순차처리됨
-예시
val adef=async{delay(1000)
1
}
val bdef=async{delay(2000)
2
}
val a=adef.await()
val b=bdef.await()
print(a+b)
//이러면 병렬처리로 2초만에 끝남
-잘못된 예시
val a=async{delay(1000)
1
}.await()
val b=async{delay(2000)
2
}.await()
print(a+b)
//이러면 순차처리가 되어 3초가 걸림
2)CoroutineScope
-상위 코루틴 스코프. 해당 스코프 내에서 하위 코루틴들을 만들어 시작할 수 있게 해줌
-코루틴스코프를 소유한 객체와 동일한 수명을 가짐
-특정 distpatcher나 context와 함께 생성
@코루틴의 context
1)구성
<1>Dispatcher: 어느 스레드에서 실행될지 결정
<2>Job 코루틴 생명주기 관리
<3>코루틴 네임: 디버깅과 로깅에 사용
2) 사용방법
-예시
val job = Job()
val context = Dispatchers.IO + job + CoroutineName("MyCoroutine")
val coroutine = CoroutineScope(context).launch {
// 코루틴이 Dispatchers.IO에서 실행되며, Job으로 생명주기를 관리하고, "MyCoroutine"이라는 이름을 가짐
}
//생명주기는 Job으로 관리
//부모 코루틴을 취소시키면 자식 코루틴들도 자동으로 취소됨
job.cancel() //이러면 코루틴이 취소됨