본문 바로가기
카테고리 없음

[코딩테스트] 브루트 포스

by 박매트 2024. 5. 3.

모든 경우의 수를 다 해보는 것이다.

ex. 비밀번호가 4자리이고, 숫자로만 이루어져있다면, 0000부터 9999까지 다 입력해보는 것이다.

- 경우의 수는 10,000가지이며, 직접 비밀번호를 입력하는데 10,000초 = 2.7 시간 정도 걸린다.

 

시간 제한을 넘지 않을 것 문제만 할 것!

 

1. 문제의 가능한 경우의 수를 계산해본다..

2. 가능한 모든 방법을 다 만들어본다..

3. 각각의 방법을 이용해 답을 구해본다.

 

시간 복잡도 : O (방법의 수 X 방법 1개의 시간 복잡도)

 

경우의 수

N명의 사람이 한 줄로 서는 경우의 수 : N!

N명의 사람 중에서 대표 두 명을 뽑는 경우의 수 : nC2

N명의 사람 중에서 대표 세 명을 뽑는 경우의 수 : nC3

N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수 : N * (N-1)

 

Q 1. 일곱 난쟁이

아홉 명의 난쟁이 중 일곱 명의 난쟁이를 찾는 문제

일곱 난쟁이의 키의 합은 100이다.

 

답

fun main() {
    val n = 9
	val a = IntArray(n) {readLine()!!.toInt()}
	a.sort()
	val total = a.sum()

    for (i in 0 until n){
        for (j in i+1 until n){
            if (total - a[i]- a[j]==100){
                for (k in 0 until n){
                    if (i==k || j==k) continue
                    println(a[k])
                }
                return 
            }
        }
    }
}

 

IntArray(n) => 길이가 n인 int형 배열 생성.

 

Q 2. 사탕 게임

  • NXN 크기의 테이블에 사탕이 있다.
  • 인접한 두 칸을 고르고, 사탕을 교환한다. -> 방법의 수는 N^2 개수가 있다. 칸의 개수 : N^2 
  • 그 다음, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제 -> O(N^2)
  • 총 시간 복잡도 : O(N^4)

답

import java.io.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val c = Array(n) { br.readLine().toCharArray() }

    fun checkCurMaxNum(): Int {
        var maxCnt = 1
        for (i in 0 until n) {
            // 가로 확인
            var cnt = 1
            for (j in 1 until n) {
                if (c[i][j] == c[i][j - 1]) {
                    cnt++
                } else {
                    cnt = 1
                }
                maxCnt = maxOf(cnt, maxCnt)
            }
            // 세로 확인
            cnt = 1
            for (j in 1 until n) {
                if (c[j][i] == c[j - 1][i]) {
                    cnt++
                } else {
                    cnt = 1
                }
                maxCnt = maxOf(cnt, maxCnt)
            }
        }
        return maxCnt
    }

    var result = 1
    for (i in 0 until n) {
        for (j in 0 until n - 1) {
            // 오른쪽과 swap
            if (j + 1 < n && c[i][j] != c[i][j + 1]) {
                c[i][j] = c[i][j + 1].also { c[i][j + 1] = c[i][j] } // swap
                result = maxOf(result, checkCurMaxNum())
                c[i][j] = c[i][j + 1].also { c[i][j + 1] = c[i][j] } // 되돌리기
            }
            // 아래쪽과 swap
            if (i + 1 < n && c[i][j] != c[i + 1][j]) {
                c[i][j] = c[i + 1][j].also { c[i + 1][j] = c[i][j] } // swap
                result = maxOf(result, checkCurMaxNum())
                c[i][j] = c[i + 1][j].also { c[i + 1][j] = c[i][j] } // 되돌리기
            }
        }
    }

    println(result)
}

 

알게된 점 - 값 Swap

c[i][j] = c[i][j + 1].also { c[i][j + 1] = c[i][j] }

 

값을 swap을 할 때, 사용한다.

 

단계 

  1. c[i][j + 1]의 값을 also 블록으로 전달합니다. 이 값이 also 블록 내에서 it으로 사용됩니다. (여기서는 직접 it을 사용하지 않았지만, also 블록에 전달된 객체가 it으로 참조됩니다.)
  2. also 블록 내에서, c[i][j + 1]에 c[i][j]의 값을 할당합니다. 이 시점에서 c[i][j + 1]의 원래 값은 이미 also 블록으로 전달되었기 때문에 사라지지 않습니다.
  3. also 블록의 실행 결과로, c[i][j + 1]의 원래 값(블록 실행 전)이 c[i][j]에 할당됩니다.

결과적으로, c[i][j]와 c[i][j + 1]의 값이 교환됩니다. also 블록을 사용하면, 임시 변수 없이 두 변수의 값을 교환할 수 있어 코드가 더 간결해집니다.

 

a  , b를 스왑한다고 치면,

a = b.also {b = a} 가 되는 것.

이 순서대로 값을 swap 할 수 있게 된 것이다. also 블록 안에 있는 값이 먼저 실행이 되어 b값이 a로 변하고, 

also 를 마친 다음 변경되기 전 b 값이 a 값으로 되어, a와 b의 값이 swap 된다.

 

fun main() {
    var a = 4
    var b = 5
    println("${a} ,${b}")
    a = b.also {b = a} // a와 b 값 교환
    println("${a} ,${b}")
}

 

 

 

 

날짜 계산

준규가 사는 나라는 E S M 이라는 연도를 사용한다.

E S M 이 주어졌을 때, 이게 몇 년인지 구하는 문제

 

E : 1 ~  15

S : 1 ~ 28

M : 1 ~ 19

 

모든 경우의 수 : 7980이 있다.

 

fun main() {
    val (E, S, M) = readLine()!!.split(" ").map { it.toInt() }
    var year = 1

    while (true) {
        if ((year - E) % 15 == 0 && (year - S) % 28 == 0 && (year - M) % 19 == 0) {
            break
        }
        year++
    }

    println(year)
}

 

 

리모컨

  • TV 채널을 리모컨을 이용해 바꾸는 문제
  • 버튼: 0,1,2,3,4,5,6,7,8,9,+,-
  • 일부 숫자 버튼이 고장났다.
  • 현재 보고 있는 채널 : 100
  • 이동하려고 하는 채널 : N
  • 이 때, 리모컨 버튼을 누르는 횟수를 최소로 하는 문제

예를 들어, 5457에 이동하려면 5457을 눌러 4번만에 이동할 수도 있다...

최소를 구하는 문제에서 중복이 있다는 것은 절대로 최솟값을 만들 수가 없다.

 

따라서 숫자 버튼을 누르고, 그 다음 +나 -중 하나만 연속해서 눌러야 한다.

이동하려고 한느 채널 N

숫자버튼을 눌러서 이동하는 채널 C도 0<c<500,000 면 된다.

 

Step 

1. 이동할 채널 C를 정한다.

2. C에 포함되어있는 숫자 중에 고장난 버튼이 있는지 확인한다.

- 수를 문자열로 바꾼 다음, 한 글자씩 검사하는 방법

- 수를 10으로 계쏙해서 나누면서 하나씩 검사하는 방법

3. 고장난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +나 -버튼을 ㅁ몇 번 눌러야 하는지를 계산한다.

 

* possible을 불가능하면 0, 가능하면 버튼을 눌러야 하는 횟수를 리턴하게 변경

 

꼭 기억해야 할 점은 쵯소값을 구한다는 점이다.

최소를 찾을 때는 의미있는 것 X, 중복되는 것 X어야 한다는 점을 깨닫기.

import kotlin.math.abs

fun possible(c: Int, broken: BooleanArray): Int {
    if (c == 0) {
        return if (broken[0]) 0 else 1
    }
    var len = 0
    var temp = c
    while (temp > 0) {
        if (broken[temp % 10]) return 0
        len++
        temp /= 10
    }
    return len
}

fun main() {
    val n = readLine()!!.toInt() // 이동하려고 하는 채널
    val m = readLine()!!.toInt() // 고장난 버튼의 갯수
    val broken = BooleanArray(10)
    if (m > 0) {
        val brokenButtons = readLine()!!.split(" ").map { it.toInt() } // 고장난 버튼 셋팅
        for (x in brokenButtons) {
            broken[x] = true
        }
    }
    var ans = abs(n - 100) // 정답의 초기값: 수빈이가 100번 채널을 보고 있기 때문
    for (i in n until 1000001) { // n부터 시작하여 가능한 채널까지 확인
        val lenPress = possible(i, broken) // 숫자를 몇 번 눌러야 하는지
        if (lenPress > 0) {
            val press = abs(i - n) // +를 몇 번 눌러야 하는지
            if (ans > lenPress + press) {
                ans = lenPress + press
                break // 가능한 채널을 찾았으므로 더 이상 확인할 필요 없음
            }
        }
    }
    for (i in n downTo 0) { // n부터 시작하여 0까지 내려가며 확인
        val lenPress = possible(i, broken) // 숫자를 몇 번 눌러야 하는지
        if (lenPress > 0) {
            val press = abs(i - n) // -를 몇 번 눌러야 하는지
            if (ans > lenPress + press) {
                ans = lenPress + press
                break // 가능한 채널을 찾았으므로 더 이상 확인할 필요 없음
            }
        }
    }
    println(ans)
}

티스토리툴바