[python] 백준 5636. 소수 부분 문자열

https://www.acmicpc.net/problem/5636

 

문제

숫자로 이루어진 문자열이 주어진다. 이때, 부분 문자열 중에서 가장 큰 소수를 찾는 프로그램을 작성하시오.

이 문제에서는 2보다 크거나 같고, 100,000보다 작거나 같은 소수만 소수이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 1,000개를 넘지 않는다.

각 테스트 케이스는 길이가 255를 넘지 않는 숫자 문자열로 이루어져 있다. 입력의 마지막 줄에는 0이 하나 주어진다.

소수 부분 문자열이 최소 하나 이상 존재하는 입력만 주어진다.

출력

각 테스트 케이스에 대해서, 가장 큰 소수 부분 문자열을 출력한다.

---

풀이

다음으로 정리할 코드는

https://jinho-study.tistory.com/1033

백준 알고리즘 5636번 소수 부분 문자열(python)

위 코드를 참고하였다. 사실상 똑같은 코드이므로, 혹시 몰라 출처를 남겨놓는다.

 

def sosu(n):
    li = [1]*(n+1)
    for i in range(2, int(n**0.5)+1):
        if li[i]: #li[i]가 1인 애들만 들어감
            for j in range(i+i, n+1, i): #i의 배수 값들을 확인하는 for문. [2i, 3i, 4i...]로 진행
                li[j] = 0 #그리고 그것에 해당하는 값들은 0으로 바꿔주기
    p = [i for i in range(2, n+1) if li[i]] #li[i]가 1인 값들을 p라는 배열에 넣어줌 (그러니 위 과정으로 소수인 값들만 현재 1임)
    return p

while True:
    s = input()
    if s == '0':
        break
    p = sosu(100000) #문제에서 지정한 범위까지 그냥 싹 구해놓고
    result = 2
    for n in p: #p에 있는 값들을 하나씩 골라서
        if str(n) in s: #만약 그 n의 값이 string 형태로 들어온 s와 같다면
            result = n #result에 저장
    print(result) #마지막에 저장된 값이 가장 크므로 출력

 

혼자 풀 때는 사실 조금 산으로 갔었는데 생각보다 간단한 문제였다. 개인적으로 string에 대한 생각을 다시하게 된 계기였다. 왜냐하면... 나는 일단 

if str(n) in s

가 된다는 점부터 신기하다. 그냥 저렇게만해도 string 값이 된 n과 알아서 비교가 되다니...

나 혼자 코드를 풀어나갈때는 이게 가능할 거란 생각을 못하고...

 

 

 

시간복잡도

일단 원래는 어떻게 했었는지는 시행착오 파트에서 이야기하도록 하고 위 코드의 시간복잡도부터 한 번 생각해보겠다. 흠... 소수를 찾는데 O(k)라고 하고 문자열의 길이를 m이라고 하면 이후에 문자열 s에서 각 소수를 찾는 for문은 O(m) 그렇다면 결과적으로 O(k*m)이 되겠다.

 

 

---

시행착오

물론 이것도 위 에라토스테네스의 체, 그러니 즉 소수 판정 코드만 따오고 나머지를 수정했을때... 맞긴 했다. 시간이 한 두 배 정도 더 걸린다는 것 말고는 딱히 다음 코드도 문제는 없단 뜻이다.

 

그러나 이 코드를 시행착오로 빼둔 것은... string의 특징만 제대로 알고 있었다면 굳이 하지 않아도 될 뻘짓을 했기 때문이다.

import sys
import math
input = sys.stdin.readline

def sosu(n):
    li = [1] * (n + 1)
    for i in range(2, int(n**0.5) + 1):
        if li[i]:  # li[i]가 1인 애들만 들어감
            for j in range(i + i, n + 1, i):  # i의 배수 값들을 확인하는 for문
                li[j] = 0  # 그리고 그것에 해당하는 값들은 0으로 바꿔줌
    p = [i for i in range(2, n + 1) if li[i]]  # li[i]가 1인 값들을 p라는 배열에 넣어줌
    return p

while True:
    n = input().strip()
    if n == '0':
        break
    else:
        num = []
        if len(n) == 1:
            # 고대로 출력
            print(n)
        else:
            for i in range(len(n)):
                for j in range(i + 1, len(n) + 1): 
                    a = n[:i]  # 앞부분 자름
                    b = n[i:j]  # 중간 부분 자름
                    c = n[j:]  # 뒷부분 자름

                    if a and int(a) not in num:
                        num.append(int(a))
                    if b and int(b) not in num:
                        num.append(int(b))
                    if c and int(c) not in num:
                        num.append(int(c))

        num.sort()
        p = sosu(100000)  # 소수 리스트 생성
        result = 2
        for prime in p:
            if prime in num:  # 소수 중에서 num에 있는 것 찾기
                result = prime
        print(result)

나는

1. i, j를 통해 앞부분, 중간부분, 뒷부분을 차례로 조금씩 잘라 num이라는 배열에 없는 값이라면 추가하는 코드를 짰다.

2. 그러고 그런 num을 정렬하고 소수 리스트와 비교하여

3. 소수 중에 num에 있는 것들 중 가장 마지막... 그러니까 가장 큰 값이 result로 들어가 출력되도록 하였다.

 

여기서 i와 j를 이용한 반복문으로 부분부분 잘라 num이라는 배열에 추가하는 것이 str을 사용한다면 굳이 하지 않아도 될.. 뻘짓이라고 생각되어 이쪽으로 빼두었다. 그래도 직접 짠 코드를 올리는 편이 낫겠다 싶기도 해서.

 

 

시간복잡도

이 코드의 시간 복잡도는 n의 길이를 m이라고 하면...

num의 크기가 m의 제곱. 중복 제거 및 리스트 업데이트 시간복잡도가 O(m의 4제곱)

소수를 확인하는데, num의 크기가 m의 제곱이라고 했으니... p의 길이를 k라고 했을때 O(k*m의 제곱)

 

O(m의 4제곱)의 크기가 더 크므로 결론적으로는 이것이 위 코드의 시간복잡도이다.