· 문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
· 제한 조건
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
· 입출력 예
| number | K | return |
| 1924 | 2 | 94 |
| 1231234 | 3 | 3234 |
| 4177252841 | 4 | 775841 |
· Thinking 1
음 .... 앞에서부터 범위 정해서 제일 큰 수 가져오고 이래야됨
예를 들어서
4177252841 는 총 10자리, 4개의 수를 제거했을때는 총 6자리
그러면은 뒤에 5개 이상의 수가 남는 수들 중에 제일 작은 수 -> 1부터 5까지
4 1 7 7 2 --> 1
4 7 7 2 5 2 8 4 1
4 7 7 5 2 8 4 1
4 7 7 5 8 4 1
7 7 5 8 4 1
작은수 네개 앞에서부터 지우면 되는거 아냐?
4 1 7 7 2 5 2 8 4 1
4 1 7 7 2 5 -> 1 삭제
4 7 7 2 5 2 -> 앞에 2 삭제
4 7 7 5 2 8 -> 2 삭제
4 7 7 5 8 4 -> 앞에 4 삭제
7 7 5 8 4 1
음 .. 지우는 규칙이 뭘까
1. 가장 작은 수부터 지우기 (x)
2. 자신을 제외하고 뒤의 남은 수들이 필요한 len보다 같거나 많으면 지울 수 있음 .. 그 중에서 자기가 제일 작으면 (x)
3. 자기가 몇번째 자리인지 계산하고 그 뒤에 이렇게..??
· Thinking 2
import java.util.ArrayList;
class Solution {
public String solution(String number, int k) {
String answer = "";
int len = number.length() - k;
ArrayList<Character> temp = new ArrayList<Character>();
for (int i = 0; i < number.length(); i++) {
temp.add(number.charAt(i));
}
System.out.println(temp);
while (temp.size() != len) {
int min = 0;
for (int i = 1; i < len; i++) {
if (temp.get(min) > temp.get(i)) {
min = i;
}
}
temp.remove(min);
System.out.println(temp);
}
for (int i = 0; i < temp.size(); i++) {
answer += temp.get(i);
}
System.out.println(answer);
return answer;
}
}
정확성 : 8.3 / 11번 하나 통과
지금 1942 일때는 92가 나옴..ㅠ
· Thinking 3
음..
4177252841 / 4개 삭제 / 6자리
1. 4177252 -> 1 삭제 ===> 477252841
2. 4772528 -> 2 삭제 ===> 47752841
3. 4775284 -> 2 삭제 ===> 4775841
4177252841
4 1 -> 4 o
1 7 -> 1 x
7 7 -> 7 o
7 2 -> 7 o
2 5 -> 2 x
5 2 -> 5 o
2 8 -> 2 x
8 4 -> 8 o
4 1 -> 4 o
775841
1924
924
바로 앞에서부터 뒤에거랑 비교하고 삭제한 갯수와 삭제해야되는 개수가 같으면 종료
· Thinking 4
import java.util.ArrayList;
class Solution {
public String solution(String number, int k) {
String answer = "";
ArrayList<Character> temp = new ArrayList<Character>();
for (int i = 0; i < number.length(); i++) {
temp.add(number.charAt(i));
}
int cnt = 0;
int i = 0;
while (cnt < k) {
if (temp.get(i) == 0) {
temp.remove(i);
i = 0;
cnt++;
continue;
}
if (temp.get(i) < temp.get(i+1)) {
temp.remove(i);
i = 0;
cnt++;
} else {
i++;
}
}
for (int j = 0; j < temp.size(); j++) {
answer += temp.get(j);
}
return answer;
}
}
정확성 : 75.0 / 9-10(시간초과), 12(런타임에러)
· Thinking 5
1 1 1 일때..
i == i+1 일때
i+1이 마지막 인덱스면 i 삭제
i == i+2 면 i 삭제
중복인 경우 큰 숫자가 앞에 온 경우가 안됨
import java.util.ArrayList;
class Solution {
public String solution(String number, int k) {
String answer = "";
ArrayList<Character> temp = new ArrayList<Character>();
for (int i = 0; i < number.length(); i++) {
temp.add(number.charAt(i));
}
int cnt = 0;
int i = 0;
while (cnt < k) {
if (temp.get(i) == 0) {
temp.remove(i);
i = 0;
cnt++;
continue;
}
if (temp.get(i) < temp.get(i+1)) {
temp.remove(i);
i = 0;
cnt++;
} else {
if (i == number.length()-k-1) {
while (temp.size() != number.length()-k) {
temp.remove(temp.size()-1);
cnt++;
}
}
i++;
}
}
for (int j = 0; j < temp.size(); j++) {
answer += temp.get(j);
}
return answer;
}
}
정확성 : 83.0 / 10(시간초과), 11(실패)
· Thinking 6
다시 기본으로 가서 ..
앞이 계속 커서 인덱스가 계속 남아있는 경우
예를들어 311일때
number.length() : 3, k : 2 -> n-k : 1
필요한 크기가 1임
그러면 음.. 331일때 i가 마지막인덱스까지 왔다는건 i가 가장 작은 값이라는 거임
그래서 i를 죽여
그리고 33이 됐으면 다시 i가 마지막 인덱스라는건 .. 오키오키
import java.util.ArrayList;
class Solution {
public String solution(String number, int k) {
String answer = "";
ArrayList<Character> temp = new ArrayList<Character>();
for (int i = 0; i < number.length(); i++) {
temp.add(number.charAt(i));
}
int cnt = 0;
int i = 0;
while (cnt < k) {
if (temp.get(i) == 0) {
temp.remove(i);
i = 0;
cnt++;
continue;
}
if (i == temp.size()-1) {
temp.remove(i);
i = 0;
cnt++;
continue;
}
if (temp.get(i) < temp.get(i+1)) {
temp.remove(i);
i = 0;
cnt++;
} else {
i++;
}
}
for (int j = 0; j < temp.size(); j++) {
answer += temp.get(j);
}
return answer;
}
}
아직도 9, 10 시간초과가 뜨네..ㅠ
· Thinking 7
시간 단축 위해서 StringBuilder 사용..!
import java.util.ArrayList;
class Solution {
public String solution(String number, int k) {
StringBuilder answer = new StringBuilder();
ArrayList<Character> temp = new ArrayList<Character>();
for (int i = 0; i < number.length(); i++) {
temp.add(number.charAt(i));
}
int cnt = 0;
int i = 0;
while (cnt < k) {
if (i == temp.size()-1) {
temp.remove(i);
i = 0;
cnt++;
continue;
}
if (temp.get(i) < temp.get(i+1)) {
temp.remove(i);
i = 0;
cnt++;
} else {
i++;
}
}
for (int j = 0; j < temp.size(); j++) {
answer.append(temp.get(j));
}
return answer.toString();
}
}
10 시간초과ㅠ....ㅠ
· 완성 코드
class Solution {
public String solution(String number, int k) {
StringBuilder answer = new StringBuilder();
for (int i = 0; i < number.length(); i++) {
answer.append(number.charAt(i));
} // StringBuilder answer = new StringBuilder(number); -> 하면 될 것을.. 굳이..ㅠ
int cnt = 0;
int i = 0;
while (cnt < k) {
if (i == answer.length() - 1) {
answer.deleteCharAt(i);
cnt++;
i = 0;
continue;
}
if (answer.charAt(i) < answer.charAt(i+1)) {
answer.deleteCharAt(i);
cnt++;
i = 0;
} else {
i++;
}
}
return answer.toString();
}
}스트링빌더를 사용해서 처음 풀었다.
스트링만을 사용하여 할 경우 굳이 arraylist를 사용해서 변환하는 것 보다 시간적으로 훨씬 효율적임..
예를 들어 스트링빌더를 사용하기 전에는 테스트케이스 9번이 계속 시간초과 되고, 통과되어도 9800ms로 통과되었는데,
같은 코드에서 9번이 23ms로 엄청나게 시간이 준 것을 확인할 수 있다..... 댑악사건....
· 문제 출처
https://programmers.co.kr/learn/courses/30/lessons/42883
알고리즘 연습 - 큰 수 만들기 | 프로그래머스
programmers.co.kr
댓글