https://www.acmicpc.net/problem/1946 이번에도 그리디 문제다.바로 전 문제인 회의실 배정 문제와 거의 비슷한 문제라고 볼 수 있다. 그리고 문제 설명이 살짝 헷갈렸던 문제기도 하다.지원자의 (서류심사 성적, 면접시험 성적)이 주어지는데, 둘 중 적어도 하나가 다른 지원자보다 떨어지지 않는 사람만이 선발 될 수 있다.즉, A라는 인원의 (서류심사 성적, 면접시험 성적)이 임의의 인원 B의 (서류심사 성적, 면접시험 성적)보다 둘 다 떨어지는 경우가 하나라도 있다면, A는 뽑힐 수가 없는 것이다. 결국 정렬이 필요하다.문제를 풀다 보니 그리디는 정렬과 항상 붙어 있는 느낌이다. 서류심사 성적 기준으로 오름차순 정렬한다.그리고 면접시험 성적을 반복문을 돌면서 비교하면 된다. 만약..
정렬
26_카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 happenundo.tistory.com
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 카드 비교 횟수가 최소가 되는 총 비교횟수를 출력하면 되는 문제다. 처음에 문제를 읽고, 이게 골드4문제라고? 라는 생각이 들었다. 그래서 5분만에 구현하고 제출하니 바로 시간 초과가 떴다. 문제를 자세히 읽어보니 입력 크기가 최대 100,000개 이므로 단순 비교로는 O(N^2)이라서 당연히 시간 초과가 뜬다. 그래서 계속 고민을 해봤다. 고민하다 보니, 이런 규칙이 나왔다. 매번 합칠 카드 묶음을 정할 때, 카드 묶음 리스트 중 가장 작은 값 ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 실패율 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 happenundo.tistory.com 풀었던 문제다. 정렬 + 구현 문제. # 실패율 def solution1(N, stages): result = [] # (스테이지 번호, 실패율)을 저장하고 있는 리스트 challenge = [0] * (N+2) # 각 스테이지별 도전 중인 사용자의 숫자를 저..
24_안테나 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 중앙값이 답 happenundo.tistory.com
18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 중앙값이 답이다. 나는 평균값을 구해서 틀렸다. 아이디어가 중요한 문제. 풀이 코드 # 18310번: 안테나 import sys input = sys.stdin.readline n = int(input()) house = list(map(int, input().rstrip().split())) house.sort() # 정렬한 후 print(house[(n-1)//2]) # 중앙값 출력
23_국영수 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 happenundo.tistory.com
10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 파이썬 lambda 함수와 정렬을 사용하면 되는 문제. 입력이 최대 100,000개이므로 sys 라이브러리를 사용하면 시간이 확 줄어든다. 풀이 코드 # 10825번: 국영수 import sys input = sys.stdin.readline n = int(input()) student = [] # (학생이름, 국어점수, 영어점수, 수학점수) for _ in range(n): name, a, b, c = input().rstrip().spli..
