백준 14658번
https://www.acmicpc.net/problem/14658

문제

---

생각하기

---

• 부르트포스 문제이다.
  • 별이 떨어지는 좌표에 트램펄린을 모두 설치해보면서 어느 지점에 트램펄린을 설치했을 때 가장 많은 별을 튕겨낼 수 있는지 찾으면된다.

동작

private fun find() {
    for (i in 0 until K) { // x고정
        val startX = dropArr[i].x
        val endX = dropArr[i].x + L

        for (j in 0 until K) { // y고정
            val startY = dropArr[j].y
            val endY = dropArr[j].y + L
            var count = 0
            for (k in 0 until K) {
                // x좌표를 가장 끝 부분에서 +L 까지 옮겨가면서 트램벌린을 옮김
                if (dropArr[k].x in startX..endX) {
                    if (dropArr[k].y in startY..endY) {
                        count++
                    }
                }

                ans = max(ans, count)
            }
        }
    }
} // End of find()

x좌표와 y좌표를 따로 분리해서 반복하며 트램펄린을 시작점으로 설치해보면서 어느 지점에 설치했을 때 최대값을 얻을 수 있는지 알 수 있다.

궁금증

문제를 풀고나서 새로운 방법을 생각했는데 x좌표와 y좌표를 고정해두고 x와 y를 기준으로 트램펄린을 설치하는데, 이럴 경우 중복되는 좌표가 생길 수 있다고 판단해서 HashSet에 좌표를 저장해서 중복되는 좌표를 제거하는 부분이 좌표의 양 자체가 많아졌을 때 훨씬 효율적이라고 판단해서 다시 풀었다.

private fun find() {
    xSet.forEach { x ->
        val endX = x + L
        ySet.forEach { y ->
            val endY = y + L
            var count = 0
            dropArr.forEach {
                if (it.x in x..endX) {
                    if (it.y in y..endY) {
                        count++
                    }
                }

                ans = max(ans, count)
            }
        }
    }
} // End of find()

하지만 실제로 실행했을때는 그냥 중복을 허용하는 배열이 더 시간이 빨랐는데 아마 컴파일시간이나 내가 생각하는 테스트케이스의 차이로 인해 그렇지 않을까 생각했다.

결과

Set사용

코드

---

Kotlin

import java.io.*
import java.util.*
import kotlin.math.max

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var K = 0
private var L = 0
private var ans = Int.MIN_VALUE

private data class Coordinate(var x: Int, var y: Int)
private lateinit var dropArr: Array<Coordinate>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    find()

    sb.append(K - ans)
    return sb.toString()
} // End of solve()

private fun find() {
    for (i in 0 until K) { // x고정
        val startX = dropArr[i].x
        val endX = dropArr[i].x + L

        for (j in 0 until K) { // y고정
            val startY = dropArr[j].y
            val endY = dropArr[j].y + L
            var count = 0
            for (k in 0 until K) {
                // x좌표를 가장 끝 부분에서 +L 까지 옮겨가면서 트램벌린을 옮김
                if (dropArr[k].x in startX..endX) {
                    if (dropArr[k].y in startY..endY) {
                        count++
                    }
                }

                ans = max(ans, count)
            }
        }
    }
} // End of find()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt() // 별똥별이 떨어지는 가로길이
        M = nextToken().toInt() // 세로길이
        L = nextToken().toInt() // 트램펄린의 한변의 길이
        K = nextToken().toInt() // 별똥별의 수
    }

    dropArr = Array(K) { Coordinate(0, 0) }

    // 떨어지는 별똥별의 위치의 좌표
    for (i in 0 until K) {
        StringTokenizer(br.readLine()).run {
            val x = nextToken().toInt()
            val y = nextToken().toInt()
            dropArr[i] = Coordinate(x, y)
        }
    }
} // End of input()

HashSet 사용

import java.io.*
import java.util.*
import kotlin.math.max

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var K = 0
private var L = 0
private var ans = Int.MIN_VALUE

private lateinit var xSet: HashSet<Int>
private lateinit var ySet: HashSet<Int>

private data class Coordinate(var x: Int, var y: Int)

private lateinit var dropArr: Array<Coordinate>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    find()

    sb.append(K - ans)
    return sb.toString()
} // End of solve()

private fun find() {
    xSet.forEach { x ->
        val endX = x + L
        ySet.forEach { y ->
            val endY = y + L
            var count = 0
            dropArr.forEach {
                if (it.x in x..endX) {
                    if (it.y in y..endY) {
                        count++
                    }
                }

                ans = max(ans, count)
            }
        }
    }
} // End of find()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt() // 별똥별이 떨어지는 가로길이
        M = nextToken().toInt() // 세로길이
        L = nextToken().toInt() // 트램펄린의 한변의 길이
        K = nextToken().toInt() // 별똥별의 수
    }

    dropArr = Array(K) { Coordinate(0, 0) }
    xSet = HashSet()
    ySet = HashSet()

    // 떨어지는 별똥별의 위치의 좌표
    for (i in 0 until K) {
        StringTokenizer(br.readLine()).run {
            val x = nextToken().toInt()
            val y = nextToken().toInt()

            xSet.add(x)
            ySet.add(y)
            dropArr[i] = Coordinate(x, y)
        }
    }
} // End of input()