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

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

 

 

1. 코드카타 문제풀이

A. Hashing(백준, 15829번)

문제 내용

 

문제 풀이 방법

• 입력받은 문자열을 사용해 해시 값을 출력.
• 해시 값을 구하는 방법은 a가 1이고 z가 26일 때, a의 int 값 * 31의 n제곱 % 1234567891과 같은 형식으로 구할 수 있다. n의 값은 a가 문자열에서 몇 번째 값인지 구해서 대입한다.

 

해결 코드(스포 주의)

import java.util.Scanner
import kotlin.math.pow

fun main() = with(Scanner(System.`in`)) {
    nextInt()
    val string = next()
    val mod = 1234567891

    var result: Long = 0
    var powValue = 31.0.pow(0.0).toLong()
    for (i in string.indices) {
        val charNumber = string[i].code - 96
        result += charNumber * powValue % mod
        powValue = (powValue * 31) % mod
    }

    println(result % mod)
}

 

풀이 과정

• 처음에 powValue를 만들어서 31의 0 제곱으로 초기화해 준다. 이를 계속 반복문을 계속 돌리면서 31을 곱해주면 31의 제곱수가 된다.
• result에 charNumber(문자를 문자의 고유 번호로 바꾼 값)에 powValue를 곱하고 mod로 나눠 나머지를 구한다.

 

문제 해결 과정

• pow를 while 안에서 사용하면 pow값이 계산되고 mod로 나눈 나머지를 구하게 되는데, 31의 50 제곱일 때, kotlin의 long 범위를 한참 넘어가기 때문에 long의 최대 값인 9223372036854775807로 고정되어 버리기 때문에 정확한 값을 구할 수 없게 되어 부분 점수를 받게 된다.

 

B. 영화감독 숌(백준, 1436번)

문제 내용

 

문제 풀이 방법

• 종말에 해당하는 666이 들어간 n번째 영화의 이름을 출력.

 

해결 코드(스포 주의)

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val movieNum = nextInt()
    var movie = 666
    var cnt = 1

    while (cnt != movieNum) {
        // 영화 번호를 1씩 더함
        movie++
        // 영화 번호에 666이 포함되어 있으면 cnt를 1씩 더함.
        if (movie.toString().contains("666")) {
            cnt++
        }
    }

    println(movie)
}

 

풀이 과정

• 영화의 시작을 666으로 시작하고 반복문을 돈다.
• movie의 값을 1씩 더해가면서 movie를 string으로 바꾼 값에 666이 포함되어 있는지 확인한다.
  666이 포함되어 있으면 cnt를 1씩 늘린다.
• cnt가 movieNum과 같아지면 영화 번호를 return 한다.

 

문제 해결 과정

• 처음에 문제 이해가 안 돼서 문제 해설을 찾아보고 해결했다.
• 위의 코드는 최적화 코드가 아니다. 영화감독 숌 문제들이 여러 개 있던데 그 문제에 이 코드를 쓰게 되면 시간 초과가 날 것이다.

 

C. 소트(백준, 1083번)

문제 내용

 

문제 풀이 방법

• 연속된 두 숫자를 s번 교환해서 최대한 내림차순으로 정렬하는 코드 작성.

 

해결 코드(스포 주의)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    readLine()
    var sortList = readLine().split(" ").map { it.toInt() }.toMutableList()
    val sortLimit = readLine().toString().toInt()
    var limitLeft = sortLimit           // 남은 이동 수.
    val logicList = sortList            // 로직 수행 중 변경할 리스트.
    val resultStr = StringBuilder()     // 결과 출력용 string

    // 9 2 8 10인 경우 sortCnt가 10이 있는 index의 위치보다 큰 경우 index만큼 옮기고 sortCnt를 그만큼 올리기.
    // 정렬이 되었으면 그 값을 빼고 그 다음으로 큰 값으로 1번의 과정을 반복함.
    // index의 위치보다 남은 sortCnt가 더 적은 경우 정렬이 안된 데이터를 옮기기.
    while (limitLeft > 0) {
        if (logicList.isEmpty()) break

        val currentMax = logicList.max()
        val currentMaxIndex = logicList.indexOf(currentMax)
        // 남은 이동 수가 현재 최대값의 index보다 크거나 같아야 함.
        if (currentMaxIndex <= limitLeft) {
            logicList.remove(currentMax)
            resultStr.append("$currentMax ")
            limitLeft -= currentMaxIndex
        } else {
            val subList = logicList.subList(0, limitLeft+1)
            val subMax = subList.max()
            val subMaxIndex = subList.indexOf(subMax)

            logicList.remove(subMax)
            resultStr.append("$subMax ")
            limitLeft -= subMaxIndex
        }

        sortList = logicList
    }

    resultStr.append(sortList.joinToString(" "))
    println(resultStr)
}

 

풀이 과정

• 예를 들어 리스트가 3 1 2 4의 형태로 있고 s가 4개 주어질 때, 리스트에서 가장 큰 값인 4를 3번 swap 해서 맨 앞으로 옮길 수 있다. 그러면 리스트가 4 3 1 2가 되고, 남은 s는 1개가 남는다. 4 다음으로 큰 수인 3은 제대로 정렬되어 있으니 넘어가고 3 다음으로 큰 수인 2를 1과 바꿔서 4 3 2 1과 같은 순서로 정렬할 수 있다.
• 남은 이동의 개수를 나타낼 limitLeft 변수를 만들었다.
• while에서 데이터의 값을 변경할 logicList 변수를 만들어 주었다(원본 리스트 데이터 보호).
• 정렬 결과를 출력할 resultStr를 생성한다.
• limitLeft가 0이 될 때까지 반복한다.
  현재 list의 최댓값의 index(currentMaxIndex)가 남은 움직이는 횟수보다 작거나 같으면 최댓값을 맨 앞으로 옮길 수 있다는 뜻이므로 최댓값을 제거하고 result에 추가해 준 다음, 남은 이동에서 최댓값의 index만큼 빼준다.
• 현재 list의 최댓값의 index가 남은 움직이는 횟수보다 큰 경우에는 currnetMax를 맨 앞으로 보낼 수 없기 때문에 limitLeft의 값을 고려해 0부터 limitLeft+1 만큼 자른 리스트(subList)를 새로 만들어 준다. 그리고 subList를 기준으로 최댓값(subMax)과 최댓값의 index(subMaxIndex)를 다시 구해주고, subMax값을 제거하고 result에 subMax 값을 추가한 후에 limitLeft에 subMaxIndex만큼 빼준다.
• 위 2개의 과정을 반복하면 logicList가 비거나 limitLeft가 0이 되는데, 그 상황에 맞게 break를 달아주거나 반복문 종료 조건을 달아주었다.

 

2. 스파르타 코딩 클럽 강의 수강

A. 코틀린 문법 종합반 1주 차

강의 내용 간단 정리

• 프로그래밍이 무엇인지 배움: 프로그래밍은 프로그램을 제작하고 컴퓨터와 소통하는 행위를 뜻한다.
• 안드로이드 개발에서 코틀린을 사용하는 이유를 배움: 적은 노력으로 효율이 좋은 코드를 짤 수 있다.
• ide 세팅에 대해서 공부함
• 유용한 단축키에 대해 배움.

 

3. 개인 공부

A. 바이러스(백준, 2606번)

문제 내용

 

문제 풀이 방법

• 컴퓨터 1이 감염된 컴퓨터일 때, 감염된 컴퓨터와 연결된 컴퓨터도 같이 감염될 때, 1을 제외한 감염된 컴퓨터의 개수를 출력. 

 

해결 코드(스포 주의)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    readLine()      // 컴의 개수.
    val case = readLine().toInt()  // 연결된 컴퓨터 쌍의 수.
    val list = mutableListOf<List<String>>()

    for (i in 0 until case) {
        list.add(readLine().split(" "))
    }

    val infectionList = mutableSetOf("1")
    // 1부터 시작해 target에 포함하는 데이터가 있는가? 있으면 infectionList에 데이터 추가.
    // 1을 포함하는 데이터가 있으면, 1과 연결된 데이터로 값을 변경하고 다시 반복
    var infectTarget = listOf("1")
    while (list.size > 0) {
        // 감염된 컴퓨터들의 리스트
        val infect = mutableListOf<List<String>>()
        // 감염 타겟
        val target = mutableListOf<String>()
        // 이 로직에서 감염된 컴퓨터 리스트를 찾기.
        for (i in list) {
            for (ti in infectTarget.indices) {
                if (i.contains(infectTarget[ti])) {
                    infect.add(i)
                    target.add(if (i[0] != infectTarget[ti]) i[0] else i[1])
                }
            }
        }

        infectTarget = target
        // 감염된 컴퓨터가 없으면 반복 종료
        if (infect.isEmpty()) break

        // 감염 리스트에 감염된 컴 번호 추가 및 추가된 데이터 삭제.
        for (computers in infect) {
            infectionList.addAll(computers)
            list.remove(computers)
        }
    }

    println(infectionList.size - 1)
}

 

풀이 과정

• 연결된 컴퓨터의 개수만큼 list(2중 리스트)에 입력받은 값들을 넣어준다.
• 최종적으로 감염된 컴퓨터 번호를 나타내는 infectionList(Set)를 생성한다(초기값 1).
• 감염된 컴퓨터로부터 전염된 컴퓨터 리스트를 나타내는 infectTarget 변수를 생성한다([1, 2], [1, 5]가 있을 때, infectTarget은 [2, 5]가 된다).
• 첫 번째 2중 반복문에서 infectTarget(target)과 감염된 네트워크(infect)를 구한다.
• infectTarget에 target을 대입하고 감염된 네트워크가 하나도 없으면 반복을 끝낸다.
• 감염 리스트에 감염된 컴퓨터의 번호를 추가한다.
  infectionList가 Set이기 때문에 중복 걱정 없이 addAll로 데이터를 넣을 수 있다.
  추가 완료 후 list에서 감염된 네트워크를 삭제한다.
• 이 과정을 list가 0이 될 때까지 또는 감염된 네트워크가 없어질 때까지 반복한다.

 

문제 해결 과정

• 처음에 문제 해결 방식을 이상하게 잡아서 오답이 났었다.
• 네트워크를 입력받은 그때그때 체크해서 감염된 컴퓨터를 확인했는데, 이런 방식으로 하면 첫 감염 컴퓨터인 1이 포함된 네트워크 입력이 늦게 나올수록 앞에서 입력받았던 데이터들을 활용하지 못해 틀릴 확률이 높아진다.
• 코드를 싹 갈고 지금의 풀이 방식으로 코드를 새로 만들었다.

 

---

 

오늘 공부 내용 정리 및 회고

• 이번 주부터 본격적인 코틀린 문법 공부 및 개인 과제가 나오는 주간이다.
• 착실하게 알고리즘도 풀고, 강의도 수강해 과제를 끝내보도록 하겠다.