[JAVA] 백준 1790번 : 수 이어 쓰기 2

 

---

 

• 코드

실패 코드 1 : String으로 특정 순서에 있는 문자를 가져오는 charAt를 통해 가져왔다. 결과는 메모리초과

               이유는 String 클래스 문자열의 최대 가능 길이는 2,147,483,647이기 때문에 뜬 것 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        String number = "";
        int a = 0;
        for(int i=1;i<=N;i++) {
        	number+=i;
        	a += Math.log10(i)+1;
        	if(a>=k)
        		break;
        }
        
        if (a>k)
     	    System.out.println(number.charAt(k-1));
        else
    	    System.out.println("-1");
	}
}

 

실패 코드 2 : String 대신에 ArrayList로 해보았다. 결과는 메모리초과

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        ArrayList<String> list = new ArrayList<>();
        
        int a=0;
        boolean check = false;
        
        for(int i=1;i<=N;i++) {
        	a+=Math.log10(i)+1;
        	list.add(Integer.toString(i));
        	if(a>=k) {
        		check = true;
        		a = k-(a-(int)Math.log10(i)-1)-1;
        		break;
        	}
        }
        
        if(check)
        	System.out.println(list.get(list.size()-1).charAt(a));
        else
        	System.out.println("-1");
	}
}

 

실패 코드 3 : 해당 숫자만 String형태로 가져와서 원하는 숫자 1개를 찾아서 출력한다. 잘나오는 것 같은데 틀렸다고 뜬다.. 왜그러지.. 조금 있다가 다시 풀어봐야겠다...슈벌탱

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
                
        int a=0;
        boolean check = false;
        String temp="";
        
        for(int i=1;i<=N;i++) {
        	a+=Math.log10(i)+1;
        	if(a>=k) {
        		check = true;
        		a = k-(a-(int)Math.log10(i)-1)-1;
        		temp = Integer.toString(i);
        		break;
        	}
        }
        
        if(check)
        	System.out.println(temp.charAt(a));
        else
        	System.out.println("-1");
	}
}

 

 

성공 코드 : 첫번째부터 마지막 수까지 계속하면 메모리초과, 런타임이 뜬다.

               수를 줄이기 위해서 첫번째 while 문에서 9,99,999안에 k가 있는지 판단하면서 length와 처음 입력한

               k의 자리 수 보다 적은 9*11111..꼴의 수를 가져온다.

               while 문을 빠져나온 뒤 k의 자리수 보다 적은 9*111...꼴의 수에 +1을 해줘서 자리 수를 맞춰주고,

               (k-1)/length를 더해줘서 원하는 정확한 int형의 값을 가져온다.

               만약 가지고 온 수가 N보다 높으면 입력한 수보다 높은 수를 출력하기 바랬기 때문에 -1출력

               N보다 작다면 (k-1)%length를 통해 원하는 수의 index값을 가져와서 출력해준다.

               어렵다..

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
		long finalNumber = 0;
		long length = 1;
		long numberOfDigits = 9;

		while (k > length * numberOfDigits) {
			k -= (length * numberOfDigits);
			finalNumber += numberOfDigits;
			
			length++;
			numberOfDigits *=10;
		}
				
		finalNumber = (finalNumber+1)+ (k-1)/length;
		if(finalNumber > N) {
			System.out.println(-1);
		}else {
			int index = (int) ((k-1)%length);
			System.out.println(String.valueOf(finalNumber).charAt(index));
		}
		
        
	}
}