오늘은 25314 문제가 쉬워서 두 문제를 풀어보았다.

25314 코딩은 체육과목 입니다

for문 돌려서 입력받은 값을 4로 나눈 몫만큼 long을 반복해주면 되는....너무나도 간단하고 쉬운 문제....

n = int(input())
result = ""
for i in range(1,int(n/4)+1):
    if i != (n/4):
        result += "long "
    else:
        result += "long int"
print(result)

10815 숫자카드

python3에서 리스트 내에 특정 요소가 존재하는지 bool값으로 반환받을 수 있는 in 을 사용해 풀었다가 시간초과가 계속 떠서 다른 방법을 모색해보았다.

시간초과 이슈는 "이진탐색"으로 풀면 해결할 수 있다는 정보를 얻어

다음과 같이 풀었다.

import sys

n = int(sys.stdin.readline().rstrip('\n'))
n_list = list(map(int,sys.stdin.readline().rstrip('\n').split()))
m = int(sys.stdin.readline().rstrip('\n'))
m_list = list(map(int,sys.stdin.readline().rstrip('\n').split()))

n_list.sort()

for i in m_list:
    start,mid,end=0,(n-1)//2,n-1
    while end-start>1:
        if i < n_list[mid]:
            end = mid
            mid = end - (end-start)//2
        elif i > n_list[mid]:
            start = mid
            mid = start+(end-start)//2
        else:
            print(1, end=" ")
            break;
    if end-start==1:
        if n_list[start]!=i and n_list[end]!=i: print(0, end=" ")
        else : print(1, end=" ")

이진탐색 방식을 이용하더라도 추가로 고려해야 할 점은

리스트 재할당이 이루어지면 비효율적인 시간복잡도를 가지게 된다..!

였다.

처음 이진탐색으로 풀었을 때, 리스트를 인덱스에 따라 슬라이싱해서 함수를 반환하는 재귀함수 형식을 썼었는데, 리스트 재할당 이슈로 계속 시간초과 문제를 마주해야 했다.

한번 할당한 리스트를 계속 사용하는 방향으로 풀기 위해
start, end 인덱스를 만들어서 인덱스에 값을 변경하면서 할당해주는 방식을 이용했다.

마지막에 남는 리스트(list_A[start:end])가 2개가 남는지, 한개가 남는지에 따라 답이 달라질 수 있어, 마지막에는 2개가 남았을 경우 2개를 일일이 매칭해보는 다소 비효율적인 if문을 사용하여 푼 것이 아쉽다...

그치만 풀어서 다행이다..!
더 간단하고 쌈빡한 풀이를 찾아 분석해보아야겠다.