코틀린으로 아래 문자열 관련 문제를 풀다가
계속 메모리 초과가 떠서 그대로 C++로 바꿔서 제출하니 바로 맞았다고 떠버렸다. (내 시간)
최대한 최적화 해본다고 시도해봤는데, 대회 사이트에 들어가보니 테스트 케이스가 많기도하고
메모리 제한이 작아서 아무래도 자바 계열이 메모리를 많이 잡아먹으니 쉽지 않은듯 하다
풀어서 블로그에 기록하려했는데 아쉽게 됐다.. 나중에 시간나면 다시 해봐야될듯
백준 17479 정식당
난이도: 실버3
태그: 구현, 해시를 사용한 맵
풀이 날짜: 2025.05.13
https://www.acmicpc.net/problem/17479
아래 제약들을 유의하고, 가격 변수 타입은 Long 으로 설정하기
- 특별메뉴는 일반메뉴에서 총 20,000원 이상을 주문해야 주문할 수 있다.
- 서비스메뉴는 일반메뉴와 특별메뉴에서 총 50,000원 이상을 주문해야 주문할 수 있다.
- 서비스메뉴는 단 하나만 주문할 수 있다.
var total = 0L
var menu1Total = 0L
var menu2Flag = false
var menu3Cnt = 0
var result = true
fun main() = with(System.`in`.bufferedReader()) {
val (A, B, C) = readLine().split(" ").map { it.toInt() }
val menu1 = buildMap {
repeat(A) {
val (name, cost) = readLine().split(" ")
put(name, cost.toInt())
}
}
val menu2 = buildMap {
repeat(B) {
val (name, cost) = readLine().split(" ")
put(name, cost.toInt())
}
}
val menu3 = buildMap {
repeat(C) {
val name = readLine()
put(name, 0)
}
}
val N = readLine().toInt()
repeat(N) {
val menu = readLine()
when {
menu in menu1 -> {
total += menu1[menu]!!
menu1Total += menu1[menu]!!
}
menu in menu2 -> {
total += menu2[menu]!!
menu2Flag = true
}
menu in menu3 -> {
menu3Cnt++
}
}
}
if (menu1Total < 20000 && menu2Flag) result = false
if (total < 50000 && menu3Cnt > 0) result = false
if (menu3Cnt > 1) result = false
println(if (result == true) "Okay" else "No")
}코틀린에서 배운점
- 리펙토링
- 아래와 같이 코틀린스럽게? when()과 내부의 in을 사용해서 리펙토링 할 수 있었다.
- 이전 코드보다 조건문이 단순화되고 가독성이 향상 되었다.
- buildMap
- map을 초기화할 때 buildMap을 사용하여 블록 내부에서 repeat으로 입력을 받아 생성할 수 있었다
- 찾아보니 블록 내부에서는 MutableMap을 제공하여 put()을 통해 값을 추가하고,
- 최종적으로 Map(immutable)으로 반환한다고 한다.
- https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.collections/build-map.html
백준 3111 검열
난이도: 플레4
태그: 구현, 문자열, 덱
풀이 날짜: 2025.05.14
https://www.acmicpc.net/problem/3111
1년전에 C++로 풀었던 문제를 Kotlin으로 다시 풀어보았다.
문제 조건의 흐름을 보면 앞 -> 뒤 -> 앞 -> 뒤 ... 와 같이 문자열을 처리하고 있다.
따라서 두 개의 Deque를 번갈아 가며 사용하여 문자열의 앞(left)과 뒤(right)에서 진행되는 부분 문자열을 처리하도록 구현하였다.
fun main() = with(System.`in`.bufferedReader()) {
val target = readLine()
val original = readLine()
val left = ArrayDeque<Char>()
val right = ArrayDeque<Char>()
var low = 0
var high = original.length - 1
var flag = false // A가 등장해서 삭제되었는지
while (low <= high) {
// 왼쪽에서 오른쪽 처리
if (!flag) {
left.addLast(original[low++])
if (left.size >= target.length) {
if (left.takeLast(target.length).joinToString("") == target) {
repeat(target.length) {
left.removeLast()
flag = true
}
}
}
}
// 오른쪽에서 왼쪽 처리
if (flag && low <= high) {
right.addFirst(original[high--])
if (right.size >= target.length) {
if (right.take(target.length).joinToString("") == target) {
repeat(target.length) {
right.removeFirst()
flag = false // 다시 왼쪽에서 오른쪽으로 처리할 수 있도록 false로 변환
}
}
}
}
}
// 남은 target 제거
val result = StringBuilder(left.joinToString("") + right.joinToString(""))
while (true) {
val idx = result.indexOf(target)
if (idx == -1) break
result.delete(idx, idx + target.length)
}
println(result)
}코틀린에서 배운점
- delete() vs removeRange()
- 둘 다 동일하게 start index 부터 end index - 1 까지의 문자열을 삭제하지만 세부 동작에서 차이점을 가졌다.
- https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.text/remove-range.html
| 항목 | delete() | removeRange() |
| 클래스 | StringBuilder | String |
| 반환 값 | 자기 자신 (StringBuilder) | 새로운 문자열 (String) |
| 변경 방식 | 변경 가능 (mutable) | 불변 (immutable, 새 문자열 생성) |
즉, removeRange()는 String 클래스의 메서드로, 호출할 때마다 새로운 문자열 인스턴스를 생성한다. 따라서 반복 횟수가 많아질수록 메모리 할당과 가비지 컬렉션(GC)의 부담이 커질 수 있다.
반면, StringBuilder는 변경 가능한(mutable) 객체로, 내부 버퍼를 재사용하기 때문에 delete() 메서드를 사용하면 메모리 재할당 없이 문자열을 효율적으로 수정할 수 있다.
이러한 이유로 반복적인 문자열 삭제 작업에서는 StringBuilder를 사용하는 것이 더 효율적이므로, 아래와 같이 코드를 수정했다.
백준 4929 수열 걷기
난이도: 실버1
태그: 구현, 누적합
풀이 날짜: 2025.05.14
문제를 요약하면 아래와 같다.
- 오름차순으로 정렬되어 있는 두 수열이 주어지고, 두 수열에 공통으로 들어있는 원소를 교차점으로 간주
- 걷기는 항상 앞으로만 가능
- 교차점에서는 현재 수열을 계속 걷거나, 다른 수열로 갈아탈 수 있음
- 목표: 한쪽 수열의 처음부터 시작하여 방문한 수들의 합이 최대가 되는 경로를 구하기
접근한 방법을 아래의 오른쪽 그림과 같이 그려보았는데, 누적합으로 문제를 해결할 수 있음을 인지할 수 있다.
추가로, 처음과 마지막에 대한 구간 별 누적합 값을 구하기 위해서 몇가지 조정을 해주었다.
아래 코드에서와 같이 누적합 배열의 0번째 인덱스를 비우고 첫번째 인덱스부터 각 수열의 누적합을 담아준다.
그리고 마지막에 대한 누적합을 구하기 위해서, 두 수열의 교차점에 해당하는 각 인덱스를 담는 idxList의 가장 마지막에 각 두 수열의 마지막 인덱스 쌍을 넣어줌으로써 해결할 수 있다.
즉, 아래의 빨간색 지점이 적용되어 구간 별 누적합을 편하게 구할 수 있다.
const val MAX = 10005
val psum1 = IntArray(MAX)
val psum2 = IntArray(MAX)
fun main() = with(System.`in`.bufferedReader()){
while (true) {
val line = readLine() ?: break
if (line == "0") return
val arr1 = line.split(" ").drop(1).map { it.toInt() }
val arr2 = readLine().split(" ").drop(1).map { it.toInt() }
val idxList = mutableListOf<Pair<Int, Int>>()
val valueToIndexArr2 = arr2.withIndex().associate { it.value to it.index }
for ((idx1, value) in arr1.withIndex()) {
val idx2 = valueToIndexArr2[value]
if (idx2 != null) {
idxList.add(Pair(idx1, idx2))
}
}
idxList.add(Pair(arr1.size - 1, arr2.size - 1))
repeat(arr1.size) {
psum1[it + 1] = (psum1[it] + arr1[it])
}
repeat(arr2.size) {
psum2[it + 1] = (psum2[it] + arr2[it])
}
var prev1 = 0
var prev2 = 0
var result = 0
for (i in 0 until idxList.size) {
val sum1 = psum1[idxList[i].first + 1] - psum1[prev1]
val sum2 = psum2[idxList[i].second + 1] - psum2[prev2]
result += maxOf(sum1, sum2)
prev1 = idxList[i].first + 1
prev2 = idxList[i].second + 1
}
psum1.fill(0)
psum2.fill(0)
println(result)
}
}코틀린에서 배운점
- arr2.withIndex().associate { it.value to it.index }
- withIndex()를 호출하면 IndexedValue(index, value) 형태의 시퀀스가 만들어진다.
- ex) arr2 = [1, 4, 7]이면
- arr2.withIndex() 결과는: [IndexedValue(0, 1), IndexedValue(1, 4), IndexedValue(2, 7)]
- associate는 (key, value) 쌍으로 이루어진 Map을 만드는 함수이다.
- 결과적으로 arr2의 원소 값을 key, 그 인덱스를 value로 갖는 Map<Int, Int>을 만들게 된다.
- withIndex()를 호출하면 IndexedValue(index, value) 형태의 시퀀스가 만들어진다.
계속 작성중.....
