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

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

 

 

1. 코드카타 문제풀이

A. 트럭(백준, S1, 13335번)

문제 내용

 

문제 풀이 방법

• 다리의 길이, 다리의 최대하중이 주어지고 트럭의 무게를 나타낸 숫자들이 입력으로 주어질 때, 모든 트럭들이 다리를 건너는 최단시간을 출력.
• 다리의 길이는 단위길이라고 적혀 있는데, 그냥 다리의 길이가 w라는 뜻이므로 단위길이 때문에 헷갈리는 일이 없도록 하자.
• 최단시간을 출력하려면 다리의 최대 하중에 가장 가깝게 트럭들을 여러 대 보내야 한다(하중이 10이라면 무게가 4인트럭 1대를 보내는 것보다 무게가 4, 5인 트럭 각각 1대씩 보내는 것이 시간 절약에 도움이 된다).
  트럭 1대가 다리를 모두 건너는 시간은 w초가 걸린다(다리의 길이만큼).
• 트럭은 다리로 진입하는 데 1초, 다리를 건너는 데 w초가 걸리면서 다리를 통과하게 된다.
• 다리 길이가 2이고 최대 하중은 10, 트럭이 7, 4, 5, 6이 주어질 때, 다리를 []라고 표현하겠다.
  w만큼의 길이를 가지는 큐를 생성하고, 큐에 있는 값들의 합이 최대 하중보다 크면 0을 넣어주고, 아니면 트럭 값을 넣어준다.
  초반에 큐의 길이가 다리 길이보다 작으면 데이터를 넣는다(빼는 로직은 넣지 않음).

초기 형태
7 4 5 6, []

이동 시작
4 5 6, [7]
4 5 6, [7 0]
5 6, [0 4]
6, [4 5]
6, [5 0]
 , [0 6]
 , [6]
 , []

총 8번의 움직임이 필요함.

• 보면 알다시피 큐(다리)를 순환시키면서 트럭 리스트가 빌 때까지 반복해서 순환시키고,
  리스트가 비면 남은 큐 데이터들은 모두 빼는데 w(다리 길이) 초가 걸리므로 그만큼 더해주면 된다.

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bridge = readLine().split(" ")
    val bridgeWidth = bridge[1].toInt()     // 다리에 동시에 올라갈 수 있는 트럭의 대수.
    val maxWeight = bridge.last().toInt()

    val trucks = readLine().split(" ").map { it.toInt() }.toMutableList()
    var truckWeight = 0     // 다리에 올라간 트럭의 무게를 구하기 위함.
    var moves = 0       // 트럭을 움직인 횟수.
    val bridgeQueue: Queue<Int> = LinkedList()  // 현재 다리에 올라간 트럭(비어 있으면 0)

    while (trucks.isNotEmpty()) {
        // 트럭을 넣고 큐가 다리의 무게를 초과해 다음 트럭을 넣을 수 없으면
        // 큐에 0을 넣어서 다리에 있는 트럭을 다음 트럭에 옮길 수 있도록 한 칸씩 밀어낸다.

        // 처음에 bridgeWidth보다 큐의 길이가 더 작은 경우는 숫자를 넣어준다(maxWeight보다 작을 때까지, 그 외의 경우는 0으로 넣기).
        // 큐의 길이가 bridgeWidth에 도달한 경우는 첫 데이터를 빼고 0 또는 trucks의 0번째 데이터를 넣어준다.
        // 큐의 sum에 trucks의 0번째 데이터를 더한 값이(truckWeight) maxWeight보다 작으면 trucks의 0번째 index를 넣고 아니면 0을 넣기.
        val trucksFirst = trucks.first()
        if (bridgeQueue.size >= bridgeWidth) {
            val remove = bridgeQueue.remove()
            if (remove != 0) truckWeight -= remove

            val addValue = if (truckWeight + trucksFirst <= maxWeight) trucksFirst else 0
            bridgeQueue.add(addValue)

            if (addValue != 0) {
                truckWeight += trucksFirst
                trucks.removeFirst()
            }
        } else {
            val addValue = if (truckWeight + trucksFirst <= maxWeight) trucksFirst else 0
            bridgeQueue.add(addValue)

            if (addValue != 0) {
                truckWeight += trucksFirst
                trucks.removeFirst()
            }
        }

        moves++
    }

    if (bridgeQueue.isNotEmpty()) moves += bridgeWidth
    println(moves)
}

 

풀이 과정

• trucks(트럭 리스트)가 빌 때까지 반복한다.
  우선 계산에 필요한 첫 번째 truck 데이터(trucksFirst)를 불러온다.
  bridgeQueue의 size가 bridgeWidth보다 크거나 같은 경우 순환을 해주어야 한다.
  첫 번째 데이터를 삭제하고(첫 번째 데이터가 0이 아니면 truckWeight(다리에 있는 트럭들의 합)에서 remove 된 값만큼 빼준다.)
  새로운 데이터를 넣는다(truckWeight에 truckFirst를 더한 값이 maxWeight(다리 최대 하중) 보다 작거나 같으면 truckFirst를 큐에 넣어준다).
  addValue가 0이 아니면 새로운 트럭이 다리에 진입했다는 뜻이므로 trucks의 첫 번째 데이터를 지워주고 truckWeight에 trucksFirst를 더해준다.
• bridgeQueue가 비어있지 않다면 moves에 bridgeWidth만큼 더해준다.

 

문제 해결 과정

• 큐를 순환시키는 것에 다양한 조건들이 붙어서 코드 가독성이 떨어진다. 그래서 많이 헷갈린다.
• 문제를 보고 로직을 깨닫는데 시간이 오래 걸렸다. 로직을 알기만 하면 구현은 어렵지 않다.

 

B. 정사각형(백준, S3, 1485번)

문제 내용

 

문제 풀이 방법

• 테스트 케이스 1개당 좌표 4개가 주어질 때, 정사각형이 될 수 있는 경우 1을 아니면 0을 출력.
• 정사각형이 될 수 있는 경우는 각 변과 대각선의 길이를 비교한다(6개).
  각 변의 길이와 대각선의 길이 6개가 모두 같은 경우.
  각 변의 길이 4개가 모두 같고 대각선의 길이 2개가 같은 경우.

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val pointList = mutableListOf<List<Int>>()

        for (j in 0 until 4) {
            pointList.add(readLine().split(" ").map { it.toInt() })
        }

        // 각 점간의 거리 게산(대각선 포함)
        val distanceList = mutableListOf<Double>()
        var a: Long = (pointList[0][0] - pointList[1][0]).toLong()
        var b: Long = (pointList[0][1] - pointList[1][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))
        a = (pointList[0][0] - pointList[2][0]).toLong()
        b = (pointList[0][1] - pointList[2][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))
        a = (pointList[0][0] - pointList[3][0]).toLong()
        b = (pointList[0][1] - pointList[3][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))
        a = (pointList[1][0] - pointList[2][0]).toLong()
        b = (pointList[1][1] - pointList[2][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))
        a = (pointList[1][0] - pointList[3][0]).toLong()
        b = (pointList[1][1] - pointList[3][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))
        a = (pointList[2][0] - pointList[3][0]).toLong()
        b = (pointList[2][1] - pointList[3][1]).toLong()
        distanceList.add(sqrt((a * a + b * b).toDouble()))

        // distanceList에서 중복 제거 값이 1이면 정사각형
        // distanceList에서 대각선 길이가 다르면 정사각형 아님.
        // distanceList에서 중복제거 했을 때, 결과가 3개이상 나오면 정사각형 아님.
        val distanceSet = distanceList.toSet()
        when (distanceSet.size) {
            1 -> println(1)
            2 -> println(1)
            else -> println(0)
        }
    }
}

 

풀이 과정

• case 만큼 반복해 좌표를 입력받아 pointList에 저장한다.
  그다음 대각선 2개, 변 4개의 길이를 구해야 하는데 일단 일일이 하나하나 구해주었다.
  점 A부터 시작해 A에서 B, C, D로, B에서 C, D로, C에서 D로 통하는 선의 길이를 구해준다. 

진행 순서

• 선의 길이는 피타고라스 공식을 이용해 구해준다.
  피타고라스 공식으로 구한 선의 길이는 정확성을 위해 Double로 distanceList에 저장한다.
• distanceList에서 중복을 제거한 결과가 1 또는 2면 정사각형의 조건을 만족하므로 1을 출력하고 그 외의 경우는 0을 출력한다.

 

문제 해결 과정

• 처음에 로직을 짤 때는 위 진행 순서 사진과 같은 기울어져 있는 정사각형을 구별하지 못해 1%에서 실패가 났다.
  정확한 해결 방법(변과 대각선의 길이를 구하는 방법)을 찾아서 구현해 해결하였다.
• 변과 대각선의 길이를 구하는 코드의 가독성이 많이 떨어진다. 당시에는 어떻게 각 좌표 간의 거리를 중복 없이 구해야 할지 모르겠어서 무지성 들이박기식으로 코드를 짰다.

 

---

 

오늘 공부 내용 정리 및 회고

• 오늘은 주어진 시간 동안 문제를 많이 해결하지 못했다. 문제 하나하나를 푸느라 시간을 많이 잡아먹은 것 같다.
• 현재 콘솔 계산기 과제를 완료해 제출해 놓은 상태이다. lv.4에 해당하는 의존성 역전 법칙에 대해 자세히 공부해 보아야겠다. 마무리 스크럼 후 갑자기 헷갈려졌다(?)