📍 큰 수 만들기
💡 문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
⚠️ 제한사항
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
✅ 풀이
👆 첫 번째 풀이 (실패)
- 주어진 배열 중 k개의 원소를 제외한 가장 큰 숫자를 구해야 한다.
- 배치 순서도 원본 배열과 같아야 한다.
- 즉, 두 번째 자리수는 원본 배열에서의 위치가 첫 번째 자리수보다 앞에 위치할 수 없다.
- 가장 큰 수를 구하려면 앞자리 수가 커야 한다.
- 물론 모든 자리 수가 고를 수 있는 배열들 중에서 가장 최대값이어야 한다.
- k개의 원소를 제외해야 되므로, 최대값은 배열의 뒤에서 최소한 k개 만큼을 남겨두고 구해야한다.
- 그래야 구해야 할 자릿수만큼을 "보장"할 수 있다.
- ex.
number=123456, k=3- 총 자릿수가 3자리인 수를 구해야 한다.
- 두 번째 자리수는 첫 번째 자리수보다 앞에 올 수 없다.
- 따라서 첫 번째 자리수는 1234 중에서 최대값을 구해야 한다.
- 그래야 두 번째, 세 번째 자리수를 5와 6으로 설정해 총 자릿수가 3자리인 수를 구할 수 있다.
- 문자열의 잦은 변경이 일어나는 경우 StringBuilder를 사용해야 처리 속도가 빠르다.
위와 같은 방식을 적용해서 풀었는데.. 음.. 시간 초과가 발생했다.
class Solution {
fun solution(number: String, k: Int): String {
var answer = StringBuilder()
var from = 0
// number 뒤에서 k 만큼의 길이를 남겨두고, 최댓값을 구한다.
(0 until number.length-k).map { i ->
var max = '0'
(from..i+k).map { j ->
if (max < number[j]) {
max = number[j]
from = j + 1
}
}
answer.append(max)
}
return answer.toString()
}
}✌️ 두 번째 풀이 (성공)
사실 다른 사람 풀이 중 for 문을 map으로 바꿔 풀었던 거라서 참고한 풀이대로 변경했더니 성공했다.
왜...?
도대체 왜 바꾼 건 루프를 for 문을 이용하냐 map을 이용하냐 뿐인데 성능 차이가 나는 것일까!! 나는 너무 궁금했다.
그래서 구글에 kotlin for vs. map, kotlin for map, kotlin loop, ... 등등을 찾아봤지만 유의미한 결과는 없었다. 내가 뭔가를 놓치고 있는 것 같아서 튜터님 찬스로 답을 알게되었다!
바로 for 문은 그저 "순회만" 하지만, map은 각각의 원소에 대해 "코드를 실행시킨 리스트를 반환"하기 때문에 이번 풀이에서는 불필요한 사용이었다는 것이다.
분명 알고 있던 개념이었는데 풀이 시간에 영향이 갈 줄은 몰랐다. 앞으로 그냥 순회만 필요한 경우에는 repeat이나 for문을 사용하도록 해야겠다.
⭐ for vs. forEach
단순 반복에는 for 문의 효율이 더 좋다.
forEach는 람다 형식으로 함수를 계속 호출하는 형태라서 성능 저하가 발생한다고 한다.
class Solution {
fun solution(number: String, k: Int): String {
var answer = StringBuilder()
var from = 0
// number 뒤에서 k 만큼의 길이를 남겨두고, 최댓값을 구한다.
for(i in 0 until number.length - k){
var max = '0'
for(j in from..i + k){
if(max < number[j]){
max = number[j]
from = j+1
}
}
answer.append(max)
}
return answer.toString()
}
}🔥 다른 사람의 풀이
사실 참고할 풀이를 찾아볼 때 Stack 자료구조를 이용한 풀이가 압도적으로 많았다. 그러나 나 홍머병 김태영, 뭔가뭔가 남들이 많이 안 푼 풀이로 푸는 게 더 재밌어서 스택을 사용한 풀이는 일단 거르고 봤다. 그래도 많은 사람들이 사용한데에는 이유가 있으니까 알아보긴 해야한다.
이 문제의 분류는 현재 상황에서 지금 당장 좋은 것만 고르는 그리디 알고리즘이다. 이 알고리즘으로 모든 문제에 대해서 최적의 해를 구할 수는 없지만, 보통 이걸 사용해야 하는 문제라면 최적의 해를 구할 수 있게 문제가 출제된다. 보통의 경우이니, 정말 그리디 알고리즘을 사용해도 되는 문제인지 판단할 수 있어야 한다.
문제로 돌아와서, 스택을 어떤 식으로 활용했는지 알아보자.
- number를 순회한다.
- 스택이 비어있지 않고, 스택의 최근 값이 현재 순회 중인 값보다 작고, 제거해야할 수가 있다면..
- 조건이 false가 될 때까지 스택의 최근 값을 pop하고 제거해야할 수를 1 줄인다.
- 조건을 만족하지 못했거나, while문을 탈출하면 현재 순회 중인 값을 스택에 push한다.
- 스택이 비어있지 않고, 스택의 최근 값이 현재 순회 중인 값보다 작고, 제거해야할 수가 있다면..
- 만약 number를 모두 순회했는데도 제거해야할 수가 남아있다면
- 남은 수 만큼을 pop한다.
- 스택의 순서는
[가장 최대값, 그 다음 최대값, 그 다음다음 최대값, ...]순서이기 때문에 늦게 들어온만큼 작은 수이다. - 따라서 pop을 하는 것이다.
- 이후엔 스택을 배열로 변환하고, 다시 문자열로 변환해 반환한다.
import java.util.*
class Solution {
fun solution(number: String, k: Int): String {
var answer = ""
var kCnt = k
val numberStack : Stack<Char> = Stack()
var numArray = CharArray(number.length-k)
number.forEach {
while (!numberStack.isEmpty()&&numberStack.peek()<it&&kCnt!=0){
numberStack.pop()
kCnt--
}
numberStack.push(it)
}
for (i in 0 until kCnt){
numberStack.pop()
}
numberStack.forEachIndexed { index, c ->
numArray[index] = c
}
return String(numArray)
}
}💭 후기
그래도 고등학생 때는 수학을 열심히 했던 것 같은데 몇 년 안하다 보니까 초등학생보다도 수학을 못하는 것 같다. 물론 이번 문제는 수학보다는 알고리즘에 가까웠지만.. 문득 내가 코드 통역사 같다는 생각을 했다. 코드를 한글로 옮겨적는.. 통역사... 일단 냅다 화이팅 중이다. 화이팅하다 보면 실력이 느는 날이 오겠지.
