22351 수학은 체육과목 입니다 3

DONGJIN IM·2022년 6월 28일

coding test

코딩 테스트

목록 보기

107/137

문제 이해

A와 B라는 숫자가 존재한다고 가정하자.

이 때 A, A+1, ..., B까지의 숫자를 연속적으로 입력하여 문자열로 쓴 값이 입력으로 주어질 것이다.

이 때 A와 B값을 구하는 문제이다.

(ex) A = 9, B = 12일 때 9,10,11,12이므로 9101112가 입력으로 주어질 것이다.

문제 풀이

문제를 보자마자 Brute-Force 방법밖에 생각나지 않았다.

재귀 함수를 활용해 첫째 값이 A라고 가정하고 이 재귀함수에 A, A+1...을 전달해주어 다음 숫자를 만들 수 있는지 확인하는 것이다.

만약 마지막 문자열까지 연속된 숫자를 만들 수 있다면 A를 출력하면 되고, 마지막 문자열까지 도달하지 못할 경우 A의 자릿수를 하나 더 추가시켜 다음 재귀함수를 실행시켜보면 된다.

코드

Java

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static String s;
	static int real_end;
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		s = sc.next();
		
		for(int i =1;i<4;i++) {
			int k = Integer.parseInt(s.substring(0,i));
            // A는 1이상 999이하의 정수
            // 즉, A가 될 수 있는 자릿수는 1 ~ 3이 될 것이다.
			
			if(rec(k, i)) {
            // rec(k,i) = true : k가 A일 때 문자열을 만들 수 있음
            // 즉, 이 때의 k가 A의 최솟값이므로 답을 출력한 이후 반복문을 종료
				System.out.println(k+" "+real_end);
				break;
			};
		}
	}
	
	
	static boolean rec(int before, int index) {
    // before : 이전 숫자
    // index : 주어진 문자열에서 확인을 시작할 index
    
		if(index>=s.length()) {
        // index가 문자열의 길이를 벗어났기 때문에 정답 후보가 된다.
			real_end = before;
			return true;
		}
        
		int now = before + 1;
        // 현재 도출되어야 할 숫자는 이전 숫자 + 1
		
		int end = (int) Math.log10(now);
        // 현재 도출되어야 할 숫자의 자리수
		
		if(index + end + 1 > s.length()) {
        // 애초에 문자열 길이가 짧아서 현재 검사해야할 숫자를 만들 수 없음
			return false;
		}
		
		int now_sub 
              = Integer.parseInt(s.substring(index, index + end + 1));
              // 현재 index와 자릿수를 활용해 숫자를 도출
		
		if(now_sub==now) {
        // 위에서 도출한 값과 현재 도출되어야 할 값이 같은 경우
        // 다음 숫자를 만들어봐야 하므로 재귀함수를 호출한다.
			return rec(now, index+end+1);
		}
		else {
        // 위에서 도출한 값돠 현재 도출되어야 할 값이 다른 경우
        // 답이 될 수 없는 후보 값이므로 False를 반환함
			return false;
		}
		
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

Python

import math
import sys

sys.setrecursionlimit(10000)
# 재귀함수 한도 횟수 증가시킴

def rec(start:int, before:int, index:int): 
# 위 JAVA와 같은 로직으로 함수 생성
    if index >= len(s):
        print(start, before)
        return True
    
    now = int(before)+1
    end = int(math.log10(now))
    
    if index + end + 1 > len(s):
        return False
    
    now_sub = int(s[index:index+end+1])
    now = int(now)

    if now_sub == now:
        return rec(start, now, index+end+1)
    
    else:
        return False
    
s = input().strip()

for i in range(1,4):
    tmp = s[0:i]
    
    if rec(tmp, tmp, i):
        break