S E P H ' S

코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 풀이 1. A의 최솟값이 B의 최댓값 보다 크면 B팀은 절대 못 이김 2. A를 역순으로 정렬. 3. B의 큰 값부터 비교하기 위해 heapq 사용 import heapq def solution(A, B): if min(A) > max(B): return 0 A.sort(reverse=True) B = [-i for i in B] heapq.heapify(B) cnt = 0 for a in A: if a >= abs(B[0]): continue e..

코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 풀이 1. 첫 번째를 뜯거나 안뜯거나로 시작. 2. table[i]를 i번째 인덱스 까지의 얻을 수 있는 최댓값이라고 정의하면 1) i-1 번째를 뗐을 경우 = i번째는 뗄 수 없다. i-1 번째 까지의 값 그대로 2) i-1 번째를 떼지 않았을 경우 = i-2 번째 까지의 값, + sticker[i] 3. 초항은 1) i-1번째를 뗐을 경우 table[0], table[1] = sticker[0], table[0] 이고 마지막 인덱스 확인 안함..

코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 1. n이 works 전체 합보다 크면 0 2. python heapq(java의 priority queue) 사용 3. 최대 힙을 만들기 위해 -1로 works 치환 import heapq def solution(n, works): if n >= sum(works): return 0 works = [-i for i in works] heapq.heapify(works) for _ in range(n): w = heapq.heappop(wor..

코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 풀이 1. 제한사항에서 n은 20이하의 자연수라고 되어있다. 시간 복잡도가 n! 인 permutations를 사용하면 제한시간 초과로 풀지 못하는 테스트 케이스가 발생한다. 2. 수학적 응용과 문제의 규칙을 이용해서 풀어야함. 3. 문제에서 처럼 k를 5라고 했을때, k 이전에 있는 배열의 개수는 4. 이 중에 1로 시작하는 경우 2개, 2로 시작하는 경우 2개이다. 즉, n = 3일때, 하나를 골랐을 때 나머지를 고를 수 있는 경우의 수와 같다...