[Python] HackerRank - Seperate The Numbers

드디어 외주 일이 마무리 되었고 이제 알고리즘 겸 영어로 문제 푸는 연습을 시작해따 ~.~

 

Problem

 

Solving Process

우선 처음 생각했던 과정은

처음부터 뒷 숫자를 검사하는 것이었다.

대충 노트를 하면서 풀었지만 내가 생각해도 너무 복잡한 과정이었고 조건문이 너무 많은 상황이었다.

그래서 다른 방법이 없을까 생각하다

나올 수 있는 경우의 수를 미리 나열하고 검사하자 였다.

 

우선, 메모리 제한을 두기 위해

첫번째 자리수가 될 수 있는 최대 길이는 s의길이 // 2 라는 것과, 

나올 수 있는 s의 길이는 32이므로 만드는 경우의 수 자릿수를 32로 제한했다.

 

def separateNumbers(s):
    s_length = len(s)
    max_first = s_length//2
    possible_list = []
    is_find = -1
    
    for i in range(1, max_first+1):
        first = s[:i]
        sen = ''
        j = 0
        while len(sen + str(int(first) + j)) <= 32:
            sen += str(int(first) + j)
            j += 1
        sen += ('/' + first)
        possible_list.append(sen)
    
    for i in possible_list:
        if s == i[:s_length]:
            is_find = i.split('/')[1]
    
    print('YES ' + is_find if is_find != -1 else 'NO')

하지만, 이 코드에는 단점이 있었다.

우선 첫번째 자릿수를 가져오기 위해 살짝 지저분한 방법을 쓴다는 것과 (/로 구분지어 나중에 split해서 얻어옴)

딱 통과하지 못한 테스트 케이스가 있었는데

 

s = 4294967295 4294967296 429496729
sen = 4294967295 4294967296 4294967297/4294967295

이 같은 경우였다. (보기 편하기 위해 띄어쓰기 추가)

연속된 숫자는 아니기에 False 가 나와야하지만, 이렇게 중간에 끊겼기는 케이스가 있기에 예외처리를 해줘야했다.

 

곰곰히 생각하다보니,

꼭 경우의 수를 다 저장해둘 필요가 없던 것이었다.

sen이라는 변수를 만들때 마다 검사를 해주면 해결 될 일이었다!!1

그렇다면 훨씬 메모리도 절약하고 시간도 빠르게 해결할 수 있었다.

 

Solution

def separateNumbers(s):
    max_first = len(s)//2
    is_find = -1
    
    for i in range(1, max_first+1):
        first = s[:i]
        sen = ''
        j = 0
        while len(sen + str(int(first) + j)) <= 32:
            sen += str(int(first) + j)
            if sen == s:
                is_find = first
                break
            j += 1
    
    print('YES ' + is_find if is_find != -1 else 'NO')

최종 결과물이다.

 

+) 저장을 안하는 형식이면 32자의 제한이 아닌, len(s)의 형식으로 제한을 둘 수 있을 것 같다.

이보다 더 짧게 짤 수 있을 것 같음!!

계속해서 생각해보며 줄여나가 보자~.~

 

+) str(), int()같은 타입변환은 시간 복잡도가 O(logN)이다!