하루 코테 3개 풀기 - 5일차

1. 소수 나열하기(백준1929)

Q.정수를 입력 했을 때, 그 정수 이하의 소수를 반환하시오

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수없는 1보다 큰 자연수이다.

def find_prime_list_under_number(x) :
    prime_list=[]
    
    #2~20까지 찾아서 소수인가? 소수라면 위의 prime_list 배열에 넣어라
    
    for n in range(2, x +1) : # 2 ~ n까지의 숫자들이 n에 들어가는 것을 반복한다.
        #n이라는 숫자가 소수인지 아닌지를 알기 위해서는 자신과 1 외의 나머지를 가질 수 없다. 를 활용한다.
        for i in range(2,n) :  #n을 포함하지 않은 2~n 의 자연수들의 나눔
         if n % i == 0 :  #나눴을때 0이 나오면 소수가 아니기 때문에 break 로 중단한다.
             break
         else:
             prime_list.append(n)

 근데 이러면 모든 수를 검사해서 해야 하기 때문에 범위를 줄여야한다.

https://imdona.tistory.com/25

백준 1929[소수 구하기] : 파이썬 & 시간초과 해결방법 & 소수 판정, 에라토스테네스의 체

N, M = map(int, input("두 값을 입력하세요:").split())

def find(N,M):
    for i in range(N, M+1):
        if i > 1 :
            for x in range(2 , int(i ** 0.5) + 1) :
                if i%x == 0 :
                    break
            else :
                print(i)
                
                
find(N,M)

 

2.문자열 뒤집기(백준1439)

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

 

#수가 0일때 앞의 1일 때와 0 으로 바꾸는 경우
#앞의 수가 0일때 0으로 바꾸는 방법

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0
    
    if string[0] == '1' :
        count_to_all_zero += 1
    elif string[0] == '0':
        count_to_all_one += 1
    
    for i in range(len(string) - 1) :
        if string[i] != string[i+1] :
            if string[i+1] == "1" :
                count_to_all_zero += 1
            if string[i+1] == "0" :
                count_to_all_one += 1
    print (count_to_all_zero, count_to_all_one)    
    return min(count_to_all_zero, count_to_all_one)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)

print(result)

 

구글링 하다가 찾은 쉬운 방법.

S = input()
count = 0
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        count += 1
print((count + 1) // 2)

 

 

 

3. 가장 많이 받는 선물  (프로그래머스 LV.1)

def solution(friends, gifts):
    answer = 0
    array = {k: {j:0 for j in friends if j != k} for k in friends}
    given_a = {k: 0 for k in friends}
    target_a = {k : 0 for k in friends}
    
    for items in gifts :
        send, target = items.split()
        array[send][target] += 1
        given_a[send] +=1
        target_a[target] +=1
    
    #이제다음달 얼마나 . 더받을지 보기
    for k, kk in array.items():
        count1 = 0
        for kk , aa in array[k].items():
            if array[k][kk] > array[kk][k] :
                count1 += 1
            elif array[k][kk] == array[kk][k] :
                if given_a[k] - target_a[k] > given_a[kk] - target_a[kk] :
                    count1 += 1
                    
        answer = max(answer, count1)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/258712

프로그래머스

 

ㅠㅠ..

참고한 풀이 법

https://zzzini-5.tistory.com/267