본문 바로가기
♞ | 공부일지/♝ | TIL

[Android] 공부일지(2024-06-29)

by immgga 2024. 6. 29.
오늘 공부한 내용 정리(2024년 6월 29일)

 

꾸준히 정진해 하늘로 계속 올라가는 열기구처럼 삶의 목표를 위해 나아가는 사람이 되자.

 

알고리즘 문제풀이

트리(Gold 5, 1068번)

문제 내용

 

문제 풀이 방법

노드의 개수(N)와 각 노드의 부모가 주어질 때, 리프 노드의 개수를 출력.

리프 노드란 트리에서 자식 노드가 없는 노드를 뜻한다.

 

 

해결 코드(스포 주의)

더보기
import java.util.*

private var tree = mutableMapOf<Int, MutableList<Int>>()

fun main() = with(Scanner(System.`in`)) {
    val nodeCnt = nextInt()

    // node는 0부터 nodeCnt -1 까지 존재함.
    for (node in 0 until nodeCnt) {
        // parent: node의 부모 노드
        val parent = nextInt()

        // 현재 노드 key값이 map에 존재하지 않으면 새롭게 생성.
        // parent가 -1이고 현재 node key값이 없으면 node key만 생성해주고 continue.
        if (!tree.containsKey(node) && parent == -1) {
            tree[node] = mutableListOf()
            continue
        } else if (!tree.containsKey(node)) {
            tree[node] = mutableListOf()
        } else if (parent == -1) continue

        // tree의 key가 parent인 데이터의 value에 node를 넣어주어야 함.
        if (!tree.containsKey(parent)) tree[parent] = mutableListOf(node)
        else tree[parent]!!.add(node)
    }

    val deleteNode = nextInt()
    // 트리의 노드 안에 있는 자식들의 노드를 모두 제거.
    deleteTree(deleteNode)

    // 현재 살아있는 노드에 남은 deleteNode를 모두 제거
    for (node in tree) {
        node.value.remove(deleteNode)
    }

    var result = 0
    for (nodeData in tree) {
        if (nodeData.value.isEmpty()) result++
    }
    println(result)
}

private fun deleteTree(deleteNode: Int) {
    for (data in tree[deleteNode]!!) {
        // 하위 노드 안에 삭제할 데이터가 남아 있으면 재귀 호출로 하위 데이터를 모두 제거.
        if (tree[data]!!.isNotEmpty()) deleteTree(data)

        tree.remove(data)
    }

    tree.remove(deleteNode)
}

 

풀이 과정

트리를 구현하기 위한 tree 변수를 생성.

총 node의 개수인 nodeCnt를 생성한다.

nodeCnt-1만큼 0부터 반복하면 그 값이 node가 된다. for문 안에 입력값은 현재 node의 parent 값이다.

 

tree의 key에 node값이 존재하지 않은 경우에는 key를 node로 설정하고 빈 mutableList를 생성해 준다.

만약 parent가 -1인 경우도 포함이라면 key를 node로 설정하고 빈 mutableList를 생성해 주는 건 똑같지만 continue를 달아주어서 밑에 로직이 수행되지 않게 막아주었다.

 

아래에는 parent의 key를 가진 데이터가 존재하지 않으면 parent를 key로 가지는 데이터를 생성해 주고, 리스트 데이터는 node를 넣어주었다.

위 조건을 만족하지 않으면 기존 데이터가 존재한다는 뜻이므로 parent key에 node를 넣어준다.

위 for문을 반복하면 key는 node가 되고, value의 list는 node의 자식 노드로 설정되게 된다.

 

이제 삭제할 노드(deleteNode)를 입력받고, deleteTree()를 실행한다.

deleteTree() 함수는 tree의 key가 deleteNode인 데이터의 value에 들어 있는 리스트의 데이터를 모두 확인해서 그 값에 해당하는 노드들도 같이 지워준다.

만약 지워야 하는 노드에 자식 노드가 존재한다면(key가 data인 노드의 value에 리스트 데이터가 존재함) 재귀 호출을 통해 자식 리스트의 데이터도 함께 모두 지워준다.

 

remove 로직이 끝난 후 남은 tree 데이터 중 value가 비어 있는 데이터의 개수를 세서 출력한다. value가 비어 있다는 건 리프 노드임을 뜻하는 것이기 때문이다.

 

 

문제 해결 과정

원래 그래프 탐색 알고리즘으로 풀어야 하는 문제였던 것 같다.

나는 그냥 mutableMap으로 풀었다.

parent와 for문의 node가 헷갈렸던 것을 빼면 그렇게 어렵지는 않았다.

예전에 못 풀고 포기한 문제였는데, 지금은 어렵지 않게 해결했다. 내 알고리즘 문제 풀이 실력이 향상된 걸까?

 

 

개인 공부

수준별 학습반 개인 과제 1주 차

공부 내용 간단 정리

구글 플레이 스토어 UI 구현 남은 랭킹 리스트 구현을 마무리했다.

현재 시간을 기준(2024-06-29)으로 인기 순위 앱 top 10을 구현했다.

이미지와 이름, 카테고리, 별점, 기타 등등을 모두 수정해 주었다.

이것으로 clone ui 1주 차 과제를 완료했다.

 

코드를 여기에 보여주면 분량이 너무 길어지기 때문에 링크를 남겨두도록 하겠다.

https://github.com/ImGaram/nb_camp_project/tree/master/standard_class/clone_ui

 

nb_camp_project/standard_class/clone_ui at master · ImGaram/nb_camp_project

2024 내일배움캠프(Android) 개인과제 코드(과제 해설 포함). Contribute to ImGaram/nb_camp_project development by creating an account on GitHub.

github.com

 


 

오늘 공부 내용 정리 및 회고

알고리즘 문제 1문제를 풀이하고 수준별 학습반 과제 1주 차를 완료했다.

xml로 화면을 구현하니까 코드가 700줄이 다 되어간다. 내가 보고 있는 코드가 어디에 해당하는 코드인지 파악하는 것도 쉽지 않았다.

내일은 푹 쉬고 싶다.

728x90