[Section04] Python 알고리즘 문제풀이 04~06

Q4. 마구간 정하기(결정알고리즘) : 주어진 N개의 마구간의 좌표에 C마리의 말을 가장 멀리 배치했을 때 가장 짧은 구간 출력

입력 :

N (3<=N<=200,000) C (2<=C<=N)

N개의 좌표

출력 : 가장 짧은 구간

 

[내가 쓴 코드]

def count(mid) :
    num = a[0]  #첫번째 마구간에 말 배치
    cnt = 1
    for i in range(1, n) :
        if a[i] - num >= mid :  #직전 배치된 마구간으로부터 현재 마구간까지의 길이
            cnt += 1
            num = a[i]  #직전 마구간 업데이트
    return cnt

n, c = map(int,input().split())
a = list()

for i in range(n) :
    a.append(int(input()))
    
a.sort()  #좌표 정렬

low = a[0]
high = a[n-1]

while low <= high :
    mid = (low + high) // 2
    if count(mid) >= c :
        res = mid
        low = mid + 1
    else :
        high = mid - 1
        
print(res)

 

[풀이 코드]

def Count(len) :
    cnt = 1
    ep = Line[0]
    
    for i in range(1, n) :
        if Line[i] - ep >= len :
            cnt += 1
            ep = Line[i]
    return cnt

n, c = map(int, input().split())
Lint = []

for _ in rnage(n) :
    tmp = int(input())
    Line.append(tmp)
    
Line.sort()

lt = 1
rt = Line[n-1]

while lt<=rt :
    mid = (lt + rt) // 2
    if Count(mie) >= c :
        res = mid
        lt = mid + 1
    else :
        rt = mid - 1
        
print(res)

 

이번주차에서 가장 힘들었던 문제,,, 풀이랑 똑같은데 lt를 1로 하셨음 왜지?

 

---

Q5. 회의실 배정(그리디) : 하나의 회의실에 주어진 n개의 회의들에 대한 시간표를 작성하려고 함, 회의의 시작시간과 끝시간을 보고 각 회의가 겹치지 않게 하면서 가장 많은 회의를 할 수 있는 최대 회의수를 출력

입력 :

N (1<=n<=100,000)

N개의 회의 시작시간과 끝시간

출력 : 최대 회의수

 

[내가 쓴 코드]

n = int(input())
a = list()

for i in range(n) :  #2차원 배열로 회의 시간 받기
    a.append(list(map(int, input().split())))
    
a.sort(key=lambda a : a[1])  #끝나는 시간 기준으로 오름차순 정렬

end = 0
count = 0

for i in range(n) :
    if a[i][0] >= end :  #직전 회의가 끝나는 시간 이후에 시작하는 회의일 경우
        count += 1  #회의 진행, end 업데이트
        end = a[i][1]
        
print(count)

 

[풀이 코드]

n = int(input())
meeting = []

for i in range(n) :
    s, e = map(int, input().split())
    meeting.append((s, e))  #튜플로 저장함
    
meeting.sort(key=lambda x : (x[1], x[0])) #정렬 우선순위를 1순위 끝시간, 2순위 시작시간으로 정렬

et = 0
cnt = 0

for s, e in meeting :
    if s >= et :
        et = e
        cnt += 1

print(cnt)

key=lambda x : (x[1], x[0]) 이렇게 정렬 우선순위를 지정할 수 있음

 

---

Q5. 씨름 선수(그리디) : N명의 지원자 중에서 다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 선정하여 선정된 씨름 선수의 인원 출력

입력 :

N (5<=n<=50)

N개의 키와 몸무게

출력 : 선정된 씨름 선수 인원

 

[내가 쓴 코드]

n = int(input())
a = list()

for i in range(n) :
    a.append(list(map(int, input().split())))
    
a.sort(reverse=True)  #키가 큰 순으로 정렬

count = 1  #가장 키가 큰 선수 선정

for i in range(1, n) :  #선정된 선수 제외하고 반복
    for j in range(0, i) :  #현재 선수보다 몸무게가 큰 선수가 있는지 확인
        if a[i][1] < a[j][1] :
            break  #있으면 break
    else :  #없을 경우 선정
        count += 1

print(count)

 

 

[풀이 코드]

n = int(input())
body = []

for i in range(n) ;
    a, b = map(int, input().split())
    body.append((a, b))
    
body.sort(reverse=True)

largest = 0
cnt = 0

for x, y in body :
    if y > largest :
        largest = y
        cnt += 1
        
print(cnt)

매 선수마다 이전 선수들과 몸무게를 비교하려고 해서 이중 for문을 썼는데 최대값을 활용하면 for문 하나로 해결이 가능함

 

 

 

 

 

*강의 : 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)