[코테스터디 3주차] 프로그래머스 소수 만들기, 푸드 파이트 대회, 백준 1920번 : 수 찾기

1. 프로그래머스 소수 만들기

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

파이썬 풀이

# 소수 확인하는 함수
def is_sosu(num):
    if num == 1:
        return False
    elif num == 2:
        return True
    for i in range(2, round(num/2+2)):
        if num % i == 0:
            return False
    return True
    
    
from itertools import combinations
def solution(nums):
    perms = list(combinations(nums, 3))
    sosu = 0
    for perm in perms:
        if is_sosu(sum(perm)) == True:
            sosu += 1
    return sosu

2. 프로그래머스 푸드 파이트 대회

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

def solution(food):
    food_str = '0'
    for i in range(len(food)-1, 0, -1):
        if food[i]%2 == 0: # 짝수면
            cnt = food[i]//2
            food_str = str(i)* cnt + food_str + str(i)* cnt
        else:              # 홀수면
            cnt = int(food[i]/2)
            food_str = str(i)*cnt + food_str + str(i)*cnt

    return food_str

3. 백준 1920번 : 수 찾기

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

문제해설

입력값
첫 번째 줄 (N) : 5
두 번째 줄(A[i]) : 4 1 5 2 3
세 번째 줄 (M) : 5
네 번째 줄 : 1 3 7 9 5

=> 출력값
1이 두 번째 줄에 있으니 1
3이 두 번째 줄에 있으니 1
7이 두 번째 줄에 없으니 0
9가 두 번째 줄에 없으니 0
5가 두 번째 줄에 있으니 1

파이썬 풀이

_ = int(input())
n_list = list(map(int, input().split()))
_ = int(input())
m_list = list(map(int, input().split()))

for n in m_list:
  if n in n_list:
     print(1)
  else: print(0)

이렇게 하니까 시간초과 뜸.. 이진탐색으로 풀어야 겠다.

_ = int(input())
M_list = list(map(int, input().split()))
_ = int(input())
N_list = list(map(int, input().split()))

def binary_search(element, some_list):
    some_list = sorted(some_list)
    start_idx = 0
    end_idx = len(some_list)-1
    while start_idx <= end_idx:
        idx = (start_idx + end_idx)//2
        if element == some_list[idx]:
            return 1
        elif element < some_list[idx]:
            end_idx = idx-1
        else:
            start_idx = idx + 1
    return 0

for n in N_list:
  print(binary_search(n, M_list))

이것도 시간초과 됨... 그래서 좀 찾아봤는데

n = int(input())
n_list = list(map(int, input().split(' ')))
n_list.sort()
m = int(input())
m_list = list(map(int, input().split(' ')))

def binary(target):
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if n_list[mid] == target:
            return True
        if target < n_list[mid]:
            right = mid-1
        elif target > n_list[mid]:
            left = mid + 1
for i in range(m):
    if binary(m_list[i]):
        print(1)
    else:
        print(0)

이렇게 for 문 안에서 if, else로 각각 프린트 해야 시간 초과가 안 난다.