본문 바로가기

코딩테스트 with PYTHON

(31)
[python] 코딩테스트 대비 - 그리디(역수열) 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys #sys.stdin=open("input.txt", "r") n=int(input()) a=list(map(int, input().split())) seq=[0]*n#정답 배열 for i in range(n): for j in range(n): if(a[i]==0 and seq[j]==0):#배열 값이 0이고, 역수열 값도 0이라면 seq[j]=i+1#삽입 break elif seq[j]==0:#배열 값이 0이 아닌데, 공간이 남았다면, a[i]-=1#배열 값을 줄이고 다음칸으로 이동 하며 위치 찾기 for x in seq: print(x, end=' ') cs
[python] 코딩테스트 - 그리디(증가수열) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import sys #sys.stdin=open("input.txt", "r") n=int(input()) a=list(map(int, input().split())) lt=0#왼쪽 포인터 rt=n-1#오른쪽 포인터 last=0#마지막으로 추출 된 값 res=""#정답 tmp=[] while ltlast:#왼쪽 자료가 마지막으로 나온 자료보다 크다면, tmp.append((a[lt], 'L'))#왼쪽 추가 if a[rt]>last:#오른쪽 자료가 마지막으로 나온 자료보다 크다면, tmp.append((a[rt], 'R'))#오른쪽 추가 tmp.sort(..
[python] 코딩테스트 대비 - 그리디(시뮬레이션 - 조건에 따른 최소 갯수) 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys from collections import deque #sys.stdin=open("input.txt", "r") n, limit=map(int, input().split()) p=list(map(int, input().split())) p.sort()#몸무게 정렬 p=deque(p)#리스트를 deque 자료구조로 변경 #deque를 사용하는 이유는 list.pop(0)를 하면 #제거된 맨 자료 뒤에 있는 모든 원소들이 한칸씩 당겨지는 연산을 하기 때문 #deque는 가르키는 포인터가 존재해서 포인터만 이동함.(효율적) cnt=0#보트 수 while p:#p가 비어있지 않다면 ..
[python] 코딩테스트 대비 - 그리디(시뮬레이션-높이 맞추기) 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 import sys #sys.stdin=open("input.txt", "r") L=int(input()) a=list(map(int, input().split())) m=int(input()) a.sort()#정렬 인덱스 0이 가장 높은 상태 for _ in range(m):#m번 반복 a[0]+=1#최대 값 1 빼고 a[L-1]-=1#최소 값 1 더하기 a.sort()#그 후 재 정렬 print(a[L-1]-a[0])#답 출력 cs
[python] 코딩테스트 대비 - 그리디 (조건 정렬) 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys #sys.stdin=open("input.txt", "r") 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) cs
[python] 코딩테스트 대비 - 그리디 알고리즘(정해진 시간 최대 배치) 문제) 답안코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys #sys.stdin=open("input.txt", "r") n=int(input()) meeting=[] for i in range(n): a, b=map(int, input().split()) meeting.append((a, b)) meeting.sort(key=lambda x : (x[1], x[0]))#끝나는 시간으로 정렬 et=0 cnt=0 for x, y in meeting: if x>=et:#시작시간이 끝나는 시간 보다 크다면, et=y#끝나는 시간 업데이트 cnt+=1#회의 추가 print(cnt) Colored by Color Scripter cs
[python] 코딩테스트 대비 - 이분검색(일직선에 배치) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import sys #sys.stdin=open("input.txt", "r") def Count(len):#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()) Line=[] for _ in range(n): tmp=int(input()) Line.appen..
[python] 코딩테스트 대비 - 이분검색(최소 길이 구하기) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import sys #sys.stdin=open("input.txt", "r") def Count(capacity):#해당 용량으로 만들 수 있는 dvd 갯수 리턴 cnt=1 sum=0 for x in Music: if sum+x>capacity: cnt+=1 sum=x else: sum+=x return cnt n, m=map(int, input().split()) Music=list(map(int, input().split())) maxx=max(Music)#음악 중 최고 용량 lt=1 rt=sum(Music)#1개 dvd에 모든 노래를 ..