[이코다] 정렬 & 이진탐색 실전문제

p.181 정렬 실전문제

def solution():
    n = int(input())
    student = []
    for i in range(n):
        name,grade = input().split()
        student.append([name,int(grade)])
    student =sorted(student,key = lambda x : x[1] )
    for i in student:
        print(i[0],end=' ')
solution()

정말정말 간다한 문젠데 단순한 실수를 해서 기록한다.

배운점

1. 입력 받은 값이 정수인지 문자인지 구분하기

2. sorted를 하고 난 결과는 다시 받기 (sort와 다르다! 정렬한 값을 재할당 해줘야 한다)

 

---

p.182 두 배열의 원소 교체

시간 복잡도 생각 안하고 푼 풀이

def solution():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    for i in range(k):
        minA = min(A)
        maxB = max(B)
        A[A.index(minA)],B[B.index(maxB)]=B[B.index(maxB)],A[A.index(minA)]
    print(A)
    print(sum(A))
solution()

def solution ():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    A.sort()
    B.sort(reverse=True)

    for i in range(k):
        if A[i]<B[i]:
            A[i],B[i]=B[i],A[i]
        else:
            break
    print(sum(A))
solution()

배운점

1. 시간 효율성을  고려한 알고리즘을 구현하자.

2. 조건이 아니면 break해서 다양한 test case의 시간효율을 줄이자

 

 

p.197 부품찾기

 

이진탐색

def solution():
    n = int(input())
    store_part =list(map(int,input().split()))
    m = int(input())
    find_part =list(map(int,input().split()))

    def bin_search(target,data,start,end):
        while start <= end:
            mid = (start+end)//2

            if data[mid]== target:
                return mid
            elif data[mid]<target:
                start = mid+1
            elif data[mid]>target:
                end = mid-1
        return None
    
    for i in range(m):
        result = bin_search(find_part[i],store_part,0,n-1)
        if result != None:
            print('yes',end= ' ')
        else:
            print('no',end= ' ')

 

계수탐색

def solution():
    n = int(input())
    # store_part =list(map(int,input().split()))

    arr = [0]*1000000
    for i in input().split():
        arr[int(i)] = 1

    m = int(input())
    find_part =list(map(int,input().split()))

    for f in find_part:
        if arr[f] ==1:
            print('yes',end= ' ')
        else:
            print('no',end= ' ')

 

p.201 떡볶이 만들기

 

내 풀이

def solution():
    n,m = map(int,input().split())
    high= list(map(int,input().split()))
    def bin_search(target,data,start,end):
        while start<=end:
            mid = (start+end)//2
            pri = data[mid]
            sumRice = sum([d-pri for d in data if d-pri>0])
            
            if sumRice>= target:
                return mid
            else:
                start = mid+1

    high.sort()
    result = bin_search(m,high,0,n-1)
    print(high[result])
solution()

나의 풀이가 다른 풀이와 다른점은

- sort를 해서 바로 mid를 return 하면 된다든 점

- sumRice라는 배열에 넣어두고 합을 구했는데 굳이 배열에 넣지 않고 total 에 더해두면 된다.