[Android, 내일배움캠프] 공부일지(2024-06-28)

오늘 공부한 내용 정리(2024년 6월 28일)

 

 

코드카타 문제풀이

게임(Silver 3, 1072번)

문제 내용

 

문제 풀이 방법

게임 횟수(X)와 이긴 게임의 개수(Y)가 주어질 때, Z는 현재 승률이다. 형택이가 게임을 몇 번 이겨야 Z가 변하는지 출력.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

private var winRate = 0
private var games = 0
private var winCnt = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ").map { it.toInt() }
    games = input[0]
    winCnt = input[1]
    winRate = getPercent(winCnt, games)

    binarySearch(1, 1e9.toInt())
}

private var result = -1
private fun binarySearch(start: Int, end: Int) {
    if (start > end) {
        println(result)
        return
    }

    // mid가 추가 판수가 된다.
    val mid = (start + end) / 2
    // 승률 구하기.
    val newWinRate = getPercent(winCnt + mid, games + mid)

    if (newWinRate > winRate) {
        // 새로운 승률이 기존 슴률보다 높다면?
        // mid 이후 값들(mid 포함)은 정답이 아님.
        result = mid
        binarySearch(start, mid - 1)
    } else {
        // 새로운 승률이 기존 승률보다 낮다면?
        // mid 포함 mid 이전의 값들은 정답이 아님.
        binarySearch(mid + 1, end)
    }
}

private fun getPercent(x: Int, y: Int): Int {
    return (x.toLong() * 100 / y).toInt()
}

 

풀이 과정

현재 판 수(gameCnt)와 승리 횟수(winCnt)를 이용해 현재 승률(winRate)을 계산해 준다.

판수의 제한이 1부터 10억까지이므로 이분 탐색을 start를 1로, end를 10억으로 삼고 호출한다.

 

이분 탐색 함수(binarySearch)에서는 (start + end) / 2로 mid의 값을 구해준다. mid가 현재 추가 판수가 된다.

mid와 위에서 초기화한 gameCnt와 winCnt를 이용해 새로운 승률을 계산한다.

새로운 승률이 기존 승률보다 크다면 최종 판수(result)에 mid를 대입한다.

그리고 binarySearch를 end를 mid - 1로 잡고 재귀 호출한다.

그렇지 않은 경우에는 start를 mid + 1로 잡고 재귀 호출한다.

 

승률을 구하는 함수는 따로 작성해 주었다(getPercent) 범위가 10억까지라서 승률을 구하기 위해 100을 곱해야 하는데, 10억에 100을 곱하게 되면 int의 범위를 넘어가버리기 때문에 따로 함수를 만들어 주었다.

또한 승률 구하는 코드를 중복해서 쓰고 싶지 않아서이다.

 

 

문제 해결 과정

승률 계산을 웬만하면 int로 하는 것이 좋다. double 또는 float로 승률을 구하게 되면 소소한 오차가 발생하게 되는데, 그 오차로 인해 gameCnt와 winCnt가 큰 수가 입력될 경우, 부정확한 답을 도출할 수 있다.

또한 이분 탐색을 사용하지 않고 수학 공식을 이용해 푸는 방법도 있던데, 그 방법이 훨씬 코드가 덜 복잡할 듯하다.

나는 수학 공식을 모르기 때문에 이분 탐색으로 풀었다.

 

 

섬의 개수(Silver 2, 4963번)

문제 내용

 

문제 풀이 방법

직사각형의 지도가 주어질 때(크기는 w x h이다), 바다는 0이고, 땅이 1로 입력될 때, 섬의 개수를 구해서 출력.

1이 여러 개 있을 때 하나의 섬이 될 수 있는 조건은 기준 1에 가로, 세로, 대각선으로 연결할 수 있으면 하나의 섬으로 간주한다.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

private var graph = arrayOf<MutableList<Int>>()
private var visited = arrayOf<Array<Boolean>>()

private val dx = listOf(-1, 1, 0, 0, -1, 1, -1, 1)
private val dy = listOf(0, 0, -1, 1, -1, 1, 1, -1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    while (true) {
        var isLandCnt = 0
        val (y, x) = readLine().split(" ").map { it.toInt() }
        if (x == 0 && y == 0) break

        graph = Array(x) { mutableListOf() }
        visited = Array(x) { Array(y) { false } }
        for (i in 0 until x) {
            graph[i].addAll(readLine().split(" ").map { it.toInt() })
        }

        for (i in 0 until x) {
            for (j in 0 until y) {
                if (graph[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true
                    isLandCnt++

                    island(i, j, x, y)
                }
            }
        }

        println(isLandCnt)
    }
}

private fun island(x: Int, y: Int, xSize: Int, ySize: Int) {
    for (i in dx.indices) {
        val mx = x + dx[i]
        val my = y + dy[i]

        if (mx in 0 ..< xSize && my in 0 ..< ySize) {
            if (graph[mx][my] == 1 && !visited[mx][my]) {
                visited[mx][my] = true

                island(mx, my, xSize, ySize)
            }
        }
    }
}

 

풀이 과정

지도상의 땅과 바다를 입력받을 graph 변수와 섬 방문 여부를 체크할 visited를 생성한다.

섬의 가로, 세로, 대각선을 비교할 dx, dy도 생성한다.

 

입력값이 "0 0"일 때까지 입력받아야 되기 때문에, 무한 반복을 돌리고 입력값(x, y)이 둘 다 0이면 반복을 종료한다.

입력받은 x, y를 이용해 graph, visited를 초기화한다.

초기화한 graph에 입력받은 값들을 넣어준다.

 

2중 for문으로 graph를 순회한다.

만약 방문하지 않은(visited == false) 섬이 있다면(graph == 1), 방문 여부를 true로 설정해 주고 섬의 개수를 세는 카운트(isLandCnt)를 증가시킨다.

그리고 island() 함수를 수행한다(dfs).

 

island 함수에서는 dx, dy를 이용해 현재 위치의 1에서 모든 방향의 1칸 이내에 다른 땅(1)이 있다면 그 부분을 중심으로 잡고 다시 함수를 수행한다(재귀 호출).

위 과정을 반복하면 하나의 섬을 모두 방문하고 종료된다.

 

반복 종료 후 최종 isLandCnt를 출력한다.

 

 

문제 해결 과정

기존에는 상하좌우만 봤는데 이 문제는 대각선을 포함해 모든 칸을 봐야 한다는 점만 다른 평범한 그래프 탐색 문제였다.

 

 

개인 공부

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

공부 내용 간단 정리

이번 개인 과제 구현 내용은 유명 앱의 UI를 클론 코딩하는 것이다.

코드를 같이 보여주기에는 너무 포스팅이 길어질 것 같기 때문에 사진으로 대체하겠다.

아직 미완성이다.

 

나는 Google Play Store를 골랐다.

상단의 검색 바는 constrainLayout으로 감싸서 mic 아이콘과 search 아이콘에 editText를 섞어서 만들어 주고, notification icon이랑 account 아이콘과 horizontal chain을 둘러 주었다.

 

카테고리는 HorizontalScrollView를 이용해 수평 스크롤이 가능하게 설정했다.

현재 랭킹 부분은 제작 중이다(내일 완료할 예정).

 

bottom navigation 부분은 진짜 BottomNavigationView를 사용한 건 아니고, ImageView와 TextView로 껍데기를 만들어서 그럴싸하게 만들어 주었다.

 

---

 

오늘 공부 내용 정리 및 회고

알고리즘 문제는 평범하게 2문제 풀었고, 개인 과제에 충실했던 날이다.

알고리즘 문제는 이분 탐색과 그래프 탐색 문제를 풀었다.

UI 요소를 생성하면 갑자가 xml의 design 탭 상의 ui 요소가 사라지는 오류가 생겨서 종종 android studio를 껐다가 켜야 했다.

왜 문제가 생기는지는 알지 못했다.

만들다 보니 꽤나 그럴싸해져서 기분은 좋았다.

하지만 xml로 만드는 것이다 보니 코드가 수백 줄을 넘어가서 보기가 힘들어진다는 점이 있었다.

여기서 다시 한번 xml의 문제점을 다시 한번 깨닫게 되었다.