[프로그래머스] 숫자 게임

Об этом предложении

문제 요약 A팀의 출전 순서는 이미 정해져 있고, B팀은 출전 순서를 자유롭게 정할 수 있다. B팀 선수가 A팀 선수보다 큰 숫자를 낼 때만 1점을 얻는다. B팀이 얻을 수 있는 최대 승점을 구한다. 핵심 아이디어 실제 출전 순서보다 어떤 숫자가 어떤 숫자를 이기는지가 중요하다. 따라서 A와 B를 모두 오름차순 정렬한다. B의 작은 숫자부터 확인하면서, 아직 이기지 않은 A 숫자 중 가장 작은 숫자를 이길 수 있는지 확인한다. B의 숫자 > A의 가장 작은 미매칭 숫자 : 이 A 선수를 이기고 승점을 얻는다. 그렇지 않다: 이 B 선수는 어떤 남은 A 선수도 이길 수 없으므로 승점 없이 넘긴다. 이길 수 있는 B 선수를 더 큰 A 숫자에 쓰면 더 작은 A 숫자를 이길 기회를 잃을 수 있다. 따라서 가능한 가장 작은 A 숫자와 매칭하는 선택이 항상 최적이다. 풀이 과정 A와 B를 오름차순 정렬한다. A에서 아직 이기지 않은 가장 작은 숫자의 인덱스를 a_index 로 둔다. 정렬된 B를 앞에서부터 확인한다. 현재 B 숫자가 A[a_index] 보다 크면 승점을 1 늘리고 a_index 를 다음 A 선수로 옮긴다. 모든 B 선수를 확인한 뒤 승점을 반환한다. Python 코드 def solution(A, B): A.sort() B.sort() score = 0 a_index = 0 for b_number in B: # 현재 B 선수가 가장 작은 미매칭 A 선수를 이길 수 있다. if a_index < len(A) and b_number > A[a_index]: score += 1 a_index += 1 return score 예시 A = [5, 1, 3, 7] -> [1, 3, 5, 7] B = [2, 2, 6, 8] -> [2, 2, 6, 8] B 숫자 이길 A 숫자 승점 2 1 1 2 이길 수 없음 1 6 3 2 8 5 3 따라서 B팀은 최대 3 점을 얻는다. 시간 복잡도 N 을 팀 인원 수라고 하자. A, B 정렬: O(N log N) B 배열 순회: O(N) 시간 복잡도: O(N log N) 공간 복잡도: 정렬 구현에 따라 O(N) 정리 이길 수 있는 B 숫자는 남은 A 숫자 중 가장 작은 수를 이기는 데 사용한다. 이 단순한 그리디 기준을 정렬된 두 배열에 적용하면 B팀의 최대 승점을 구할 수 있다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.39

Уверенность

49%