✔️ 문제 설명
문제
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.
세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.
세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.
남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)
입력
첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.
출력
가능한 N 중에 최솟값을 출력한다.
예제 입력 1 복사
1234
예제 출력 1 복사
4
예제 입력 2 복사
234092
예제 출력 2 복사
20
예제 입력 3 복사
999909
예제 출력 3 복사
49
예제 입력 4 복사
82340329923
예제 출력 4 복사
43
예제 입력 5 복사
32098221
예제 출력 5 복사
61
예제 입력 6 복사
1111111
예제 출력 6 복사
14
예제 입력 7 복사
00000000000000000000000000000000000000000000000000000000000000000000000
예제 출력 7 복사
400
예제 입력 8 복사
345029834023049820394802334909240982039842039483294792934790209
예제 출력 8 복사
279
✔️ 문제 풀이
반복문의 limit을 30000으로 둔 이유는 문제에서 최대 3000자리라고 주어졌는데, 모든 수가 0일 경우 최대 숫자의 경우인 3000*10 = 30000을 넘을 수 없기 때문이다.
import java.awt.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
class Main{
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int j = 0;
int findNum = 0;
while(findNum++ <= 30000){
String temp = String.valueOf(findNum);
for(int i = 0; i< temp.length(); i++){
if(temp.charAt(i) == str.charAt(j))
j++;
if(j == str.length())
{
System.out.println(findNum);
return;
}
}
}
}
}
[틀린 코드]
테스트 코드는 맞는데 자꾸 4프로 쯤에서 틀렸다.
생각해보니, 틀린게 맞았다..
num %10 == ch 이 부분에서 num 의 끝자리 수부터(예를 들어 123 이란 숫자가 있으면 3->2->1) 확인을 하게된다.
그렇게 되면 첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수 중에 321 이 있으면 13, 22, 31 이런식으로 숫자가 증가되어야 하는데
num의 끝자리 수부터 확인을 하게 되므로 숫자가 증가되지 않고 모든 숫자가 num 안에 포함 되어 있다는 판단을 내려 틀리게 계산하게 되는것이다.
틀렸다고 뜨면 이 부분에 대해서 생각해보면 좋을 것 같다..!
import java.awt.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
class Main{
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int num;
int j = 0;
int findNum = 0;
int ch;
for(int i = 1; i <= 30000; i++){
num = i;
while(num > 0){
if(j == str.length()) break;
ch = str.charAt(j) - '0';
if( num % 10 == ch) {
findNum = i;
j++;
}
num /= 10;
}
}
while(findNum++ <= 30000){
String temp = String.valueOf(findNum);
for(int i = 0; i< temp.length(); i++){
if(temp.charAt(i) == str.charAt(j))
j++;
if(j == str.length())
{
System.out.println(findNum);
return;
}
}
}
}
}