코테 모의고사 치는데.. ㅋㅋ 레벨 1만 풀 수 있었다.. 매우 좌절 스러운 상태 같다.
아무튼..앞에 두문제를 25분만에 풀고 3번을 1시간 30분을 붙들고 있다가 그냥 나왔다.
그 3번이 이 문제였다
https://school.programmers.co.kr/learn/courses/30/lessons/42883
아무튼 못 풀었던 거니까 다시 해당 문제를 찾아서 풀었다.
내 문제점은 다음과 같았다
수를 뽑는 기준을 잘못 잡았다
- 그리디
라고 생각하고 문제를 풀려고 했는데 내가 처음 생각했던 기준은 다음과 같았다.
- 제거가 아니라 "뽑아야 하는 개수" 에 초점 맞추기
- 큰 수가 앞에 나와야 한다.
- “개수"???도 뭔가 고려해야 할 것 같은데 → 근데 모르겠어… ( 그래서 일단 고려 안하고 풀어버림)
이렇게 생각하곤 9 → 8 →7 … 이 순으로 number 에서 가장 앞쪽에 등장한 애들을 선택 해 갔다.
그랬더니 문제가 생겼는데
49382 이고, 여기서 3개를 뽑아야 하는 경우9 와 8 을 먼저 뽑고 나니, 다음에 뽑을 수 있는 수는 4가 되어 → 498 이라는 결과가 나오게 된 것이다.
하지만 실제로는 위에서 뽑을 수 있는 최대 수는 982 이다.
현재 방법의 문제점은, 결국, 가장 큰 수부터 먼저 뽑으려고 하다보니 n 개의 수를 뽑는 것은 만족해야해서, 앞서 뽑았던 가장 큰 수 보다 작으면서도, 그 수 보다 앞에 위치한 수를 다음 번에 뽑게 되다보니, 맨 처음부터 가장 큰 수를 뽑은 보람이 없어진다는 것이다….
따라서, 매 수를 뽑을 때 마다, “개수" 또한 고려하는 것이 필요하다고 생각된다.
따라서, 수를 선택할 때면,
- idx ≤ ( len-( 현재 남아 있는, 앞으로 뽑아야 할 개수) ) 여야 한다는 것을 고려하기로 했다. 이를 고려함과 동시에,
- 다음에 뽑는 수는 이번에 뽑은 수의 idx 오른쪽에 위치한 수여야 한다는 것 또한 고려하도록 했다.
결과적으로 뽑아야 하는 각 수는 : (이전에 뽑은 인덱스 위치 + 1 인 위치 ) ~ ( len- n) 범위에서 가장 큰 수
이게 되는 것이다.
그러면 동시에 “앞쪽에 위치하는 최대인 수" 이면서도 “개수" 를 고려할 수 있게 된다.
이렇게 하면, 앞에서 8을 뽑고, 다음에 이 8 "앞" 의 "8보다 작은 수" 를 뽑는 경우가 생기지 않을 수 있다.
"개수" 와 " 큰 수" 두 가지를 동시에 고려하는게 중요했던 문제였다.
class Solution {
private StringBuilder builder = new StringBuilder("");
public String solution(String number, int k) {
String answer = "";
int len = number.length();
int numb = len - k; // numb 개를 뽑으려 한다.
int foundIdx = -1;
while(numb > 0) {
foundIdx = find(number,numb--,foundIdx + 1, len );
builder.append(((char)(number.charAt(foundIdx))));
}
answer = builder.toString();
return answer;
}
// 현재 뽑을 수 있는 가장 큰 수의 Index 를 찾는다
public int find(String number, int n, int idx, int len) {
// idx 부터 시작해서 다음 수를 찾아야합니다
int max = 0;
int maxIdx = idx;
for(int i = idx ; i <= len-n; i++) {
if(max < number.charAt(i)){ // 캐릭터 0,1,2,... 의 유니코드 값은 (작은 값) 0,1,2,....(더 큰값) 순이기 때문에
max = number.charAt(i);
maxIdx = i;
}
}
return maxIdx;
}
}