Algorithm116 [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] 코틀린으로 정렬 관련 문제를 풀 때 사용하는 배열이나 리스트를 정렬하는 메소드의 종류 및 각 메소드의 차이 목차 개요 기본적으로 코틀린에서는 배열도 객체로 취급되어 sort()와 같은 메소드를 사용할 수 있다. 그런데 이들 메소드들은 종류에 따라 약간의 차이가 있고, 메소드를 호출한 객체의 타입과 메소드의 종류에 따라 성능도 차이난다. 백준 - 수 정렬하기 5 문제를 푸는데 그냥 단순한 정렬 문제라고 생각했다가 정렬 메소드의 종류에 따라 TLE가 나기도 했고 AC가 나오기도 했다. 이들 메소드들 사이에 무슨 차이가 있길래 무엇을 쓰느냐에 따라 결과가 다르게 나타나는지 궁금해서 내부 구조를 확인해봤는데 생각보다 많은 차이가 있었다. Kotlin 정렬 메소드의 종류 코틀린에서 배열이나 리스트를 정렬하는 메소드는 작동 방식과 결과 타입에 따른 3가지, 정렬 방법에 따른 3가지로 구분할 수 있다. 작동 방식과 결과 .. 2023. 3. 31. [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. 이전 1 2 3 4 5 6 7 8 ··· 15 다음
