BOJ107 [Kotlin] 백준 16496 : 큰 수 만들기 문제 링크 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 문제 해설 기본적으로는 정렬을 활용한 문제지만 정렬 기준을 어떻게 할지가 관건인 문제라고 볼 수 있다. 수를 이어붙여서 더 큰수를 만들기 위해서는 수를 문자열로 다뤄야 한다. 정렬 기준자체는 굉장히 간단하다. s1과 s2가 있을 때, s1 + s2와 s2 + s1 중 더 큰것이 우선적으로 오도록 정렬하면 된다. 예를 들어 123과 45가 있을 때 12345보다 45123이 더 크기 때문에 [45, 123]으로 정렬할 수.. 2023. 4. 3. [Kotlin] 백준 24389 : 2의 보수 문제 링크 24389번: 2의 보수 컴퓨터는 뺄셈을 처리할 때 내부적으로 2의 보수를 사용한다. 어떤 수의 2의 보수는 해당하는 숫자의 모든 비트를 반전시킨 뒤, 1을 더해 만들 수 있다. 이때, 32비트 기준으로 처음 표현했던 수와 www.acmicpc.net 문제 해설 문제를 보자마자 숏코딩 욕심이 나서 풀어본 문제이다. 컴퓨터가 뺄셈을 처리할 때 2의 보수를 사용하는데, 이로 인해 뺄셈은 2의 보수의 합으로 나타낼 수 있다. 예를 들어 \(10-3\)이라는 식이 있을 때 이는 \(10+(-3)\)으로도 표현할 수 있다. 위의 내용과 종합해보면 \(-3\)이 \(3\)의 2의 보수가 되는 것이다. 즉, 어떤 수 \(n\)의 2의 보수는 \(-n\)과 같다. 두 수의 서로 다른 비트 수는 두 수를 XO.. 2023. 3. 30. [Kotlin] 백준 22252 : 정보 상인 호석 문제 링크 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 해설 HashMap과 우선순위 큐를 사용하면 문제를 수월하게 해결할 수 있다. HashMap의 Key에 정보 고릴라의 이름을, Value에 정보 고릴라가 가진 정보들의 가치가 내림차순으로 정렬된 우선순위 큐를 저장한다. 여기까지 하면 사실상 문제 풀이는 끝난 것이나 다름 없다. 1번 쿼리의 경우에는 Map에 저장되지 않은 정보 고릴라의 이름이 나오면 새로운 우선순위 큐를 생성하여 Map에 저장하고 정보들의 가치를 저장하면 된다. 2번 쿼리의 .. 2023. 3. 23. [Kotlin] 백준 17830 : 이진수씨의 하루 일과 문제 링크 17830번: 이진수씨의 하루 일과 이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은 www.acmicpc.net 문제 해설 주어진 조건에 따라 이진수의 곱셈을 수행했을 때의 최대 자릿수와 최소 자릿수를 구해야한다. 그런데 이진수의 곱셈이라고는 하지만 실제로 곱셈을 수행하게 되면 최대값이 \(2^{2,000,000}\)이 되기 때문에 실제 곱셈을 수행할 수 없다. 설령 BigInteger를 사용하여 계산한다고 해도 값이 너무 크기 때문에 시간초과가 발생한다. 우선 오늘의 이진수를 최대 자릿수로 만들기 위해선 ?가 모두 1이면 된다. 반대로 오늘의 이진.. 2023. 3. 21. [Kotlin] 백준 23757 : 아이들과 선물 상자 문제 링크 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 문제 해설 우선순위 큐를 이용하면 수월하게 해결할 수 있다. 아이들이 선물을 가져갈 땐 선물이 가장 많이 남아있는 상자에서 가져가게 되는데, 우선순위 큐를 내림차순 정렬하도록 선언하면 우선순위 큐의 가장 앞에 있는 값은 항상 가장 많은 선물이 담긴 개수가 된다. 즉, 아이들이 선물을 가져갈 때마다 우선순위 큐의 가장 앞에 있는 값을 추출하여 아이들이 원하는 선물의 개수만큼 뺀 이후에 다시 삽입하는 과정을 반복하면 된다. 문제에서 모든 아이들이 실망하지 않고 선물을 가져갈 수 있는지 여부를 출력해야 한다. 선물이 가장 .. 2023. 3. 20. [Kotlin] 백준 1599 : 민식어 문제 링크 1599번: 민식어 무엇인가를 창조하는 것은 어렵다. 오민식은 지금까지 어려운 다른나라의 언어를 쓰면서 백성들이 고통에 받는 것을 슬퍼하고 새로운 언어를 만들고자 했다. 그는 창조의 고통에 시달리던 중에 www.acmicpc.net 문제 해설 주어진 문자열들을 민식어의 순서에 맞게 정렬해야한다. 주어진 민식어 단어들을 사전순으로 정렬하기 위해 아래와 같이 민식어 단어의 모든 알파벳을 대응하는 순서의 영어 알파벳으로 치환하는 메소드를 작성한다. 이 때, n과 g가 붙어있는 ng의 경우는 무조건 하나의 알파벳으로 생각한다는 조건이 있기 때문에 ng를 가장 먼저 치환한다. private fun String.toMinsik() = this.replace("ng", "L") .replace("a", ".. 2023. 3. 18. [Kotlin] 백준 12871 : 무한 문자열 문제 링크 12871번: 무한 문자열 첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문제 해설 서로 다른 두 문자열을 각각 무한히 이어 붙였을 때 같은 문자열이 되는지 확인하려면 서로 같아질 때까지 계속 이어 붙여서 비교하는 방법이 있다. 문자열의 최대 길이가 50으로 매우 작기 때문에 이 방법으로 거뜬히 해결할 수 있다. s = "abab", t = "ababab"인 경우를 예로 들 수 있다. 이 경우의 풀이 과정은 다음과 같아진다. s의 길이가 t보다 작으므로 s를 한번 이어 붙인다. → s' = "abababab", t = "ababab" t의 길이가 s'보다 작으므로 t를 한번.. 2023. 3. 15. [Kotlin] 백준 1354 : 무한 수열 2 문제 링크 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net 문제 해설 주어진 조건대로 재귀를 돌리면 된다. 다만 주어진 수의 범위가 굉장히 크기 때문에 피보나치 수를 재귀로 구할 때와 동일하게 별도의 Map에 이미 계산한 \(A_i\)를 저장하여 계산 횟수를 줄이는 것이 좋다. Code private val map = HashMap() private var p = 0L private var q = 0L private var x = 0L private var y = 0L fun main() = with(System.`in`.bufferedReader()) { val input = readLine().split(' ').map { it.to.. 2023. 3. 11. 이전 1 2 3 4 5 6 7 8 ··· 14 다음
