Coding 공부

import sys
input = sys.stdin.readline
def get_prim_number(input_Num):
    last_num = input_Num
    visited = [False for _ in range(last_num+1)]
    visited[0] = True
    visited[1] = True
 
    result = []
    for num in range(2,last_num+1):
        if not visited[num]:
            result.append(num)
            for new_num in range(2*num,last_num+1,num):
                visited[new_num] = True
    return result
N = int(input())
 
arr = list(map(int,input().split()))
result = []
max_num = max(arr)
prim_set = get_prim_number(max_num)
for val in arr:
    if val in prim_set:
        result.append(val)
 
if len(result)>0:
    answer = 1
    result = set(result)
    for prim in result:
        answer*=prim
    print(answer)
else:
    print(-1)

이 문제는 소수를 구하고, 소수가 있으면, SET에 추가를 해주고,

전부 판별을 한 뒤에, 

아무것도 없으면 -1 을,

그리고 최소공배수를 출력해주면 된다.

이 문제에서 많이 틀렸던 이유는

중복되는 소수가 온다는걸 깜빡했었다.

즉 2 2 3 5 7 이라하면, 전체를 그냥 곱하기만 하면, 420이 된다.

그러나 실제 최소공배수는 210이므로,

이러한 점을 주의하기만 하면 되는 문제였다.

def check(num):
    visited_numbers = set()
    visited_numbers.add(num)
    if visited[num] == 1:
        return True
    elif visited[num] == 0:
        return False
 
    while num >= 0:
        temp = 0
        copy_num = num
        while copy_num>0:
            calc_num = copy_num%10
            next_num = copy_num//10
            temp = temp + calc_num**2
            copy_num = next_num
        num = temp
        if temp == 1:
            for vi_num in visited_numbers:
                visited[vi_num] = 1
            return True
        elif temp not in visited_numbers:
            visited_numbers.add(temp)
        else:
            for vi_num in visited_numbers:
                visited[vi_num] = 0
            return False
        
 
 
def find_prime_number(N):
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False
    prime_list = []
    for num in range(2,N+1):
        if numbers[num]:
            prime_list.append(num)
            for not_prime in range(num+num,N+1,num):
                numbers[not_prime] = False
    return prime_list
 
 
 
 
N = int(input())
 
 
prime_numbers = find_prime_number(N)
 
visited = [-1]*1000001
result = []
 
for num in prime_numbers:
    if check(num):
        result.append(num)
for row in result:
    print(row)

import sys
 
input = sys.stdin.readline
def findprimenumber():
    global prime_number
    prime_number[1] = False
    prime_number[0] = False
    for i in range(2,10001):
        if prime_number[i]:
            for j in range(i+i,10001,i):
                prime_number[j] = False
 
 
 
 
 
T = int(input())
prime_number = [True]*10001
findprimenumber()
for _ in range(T):
    A,B = map(int,input().split())
    result = 'Impossible'
    visited = [-1] * 10001
    if A == B:
        print(0)
    else:
        stack = [A]
        cnt = 0
        while stack:
            new_stack = []
            for number in stack:
                number_list = list(map(int,list(str(number))))
                for ind in range(4):
                    if ind == 0:
                        for k in range(1,10):
                            if number_list[ind] != k:
                                new_number = k*1000 + 100*number_list[1] + 10*number_list[2] + number_list[3]
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
                    else:
                        for k in range(10):
                            if number_list[ind] != k:
                                new_number = number - number_list[ind]*(10**(3-ind)) + k*(10**(3-ind))
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = new_stack[:]
            cnt += 1
        print(result)
        
        

문제는 소수를 구하는 것과 BFS를 활용하면 되는 문제였다.

먼저 자신만의 방법으로 문제에서 주어진 10000 까지의 소수를 구한다.

나는 단순하게 반복문을 통해서 구했고, True False로 구분이 되게 해주었다.

이 상황에서 주어진 넘버에서 각자리 수를 변경하면서, 방문하지 않았고 소수일때에 new_stack에 넣어주는 방식으로 했다.

import sys
 
input = sys.stdin.readline
 
 
prime_number = [True]*10000
prime_number[0] = False
prime_number[1] = False
 
for k in range(2,10000):
    if prime_number[k]:
        for j in range(k+k,10000,k):
            prime_number[j] = False
 
T = int(input())
 
for _ in range(T):
    A,B = map(int,input().split())
    if A == B:
        print(0)
    else:
        visited = [True]*10000
        result = 'Impossible'
        stack = [A]
        cnt = 0
        while stack:
            new_stack = set()
            for number in stack:
                for k in [1,10,100,1000]:
                    fall_number = number - (number//k)%10*k
                    for i in range(10):
                        new_number = fall_number + i *k
                        if prime_number[new_number] and visited[new_number] and new_number >= 1000:
                            visited[new_number] = False
                            new_stack.add(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = list(new_stack)[:]
            cnt += 1
        print(result)

 좀 더 깔끔한 방법으로 자리수 변경을 한 방식이다. 주어진 넘버에서 바꾸고 싶은 자리수로 나눈 몫의 10으로 나눈 나머지를 구하면, 해당 자리수를 구할 수 있다. 이 방식을 이용해서, 구현했다.

number_list = [True]*1003002
number_list[0] = False
number_list[1] = False
for number in range(2,1003002):
    if number_list[number]:
        for j in range(number+number,1003002,number):
            number_list[j] = False
 
N = int(input())
flag = False
for find_number in range(N,1003002):
    if number_list[find_number]:
        string_number = str(find_number)
        if len(string_number)%2:
            if len(string_number) != 1:
                a = string_number[:N//2]
                b = string_number[N//2+1::-1]
                if a == b:
                    result = find_number
                    break
            else:
                result = find_number
                break
        else:
            a = string_number[:N//2]
            b = string_number[N//2::-1]
            if a == b:
                result = find_number
                break
    
 
print(result)

소수를 구한뒤 앞뒤로 같은지 확인해주면 되는 문제였다.

그리고 최대 입력값 100만일때 나오는 소수& 팰린드롬 수는 1003001 이므로 거기까지만 돌리면 된다.