greedy31 [leetcode][1029] Two City Scheduling 문제 : https://leetcode.com/problems/two-city-scheduling/ 2N명을 도시 A, B에 각각 N명씩 이동시키려고 한다. 각각 A, B로 이동시키는 비용이 주어질 때 이동시키는 비용의 최소값을 구해라. A아니면 B로 이동시킨다. -> 둘 중 하나는 선택되어야 한다. 하나는 선택되어야 하므로 한 명의 A, B 이동 비용을 비교해야 되고 두 방법 중 이동 비용이 작은쪽으로 이동시켜야 이득이다. 각자 A로 이동시키는 비용 - B로 이동시키는 비용을 구해서 오름차순으로 정렬한다. (B가 A보다 크거나, A비용이 더 크지만 B와의 비용 차이가 별로 나지 않을 수록 앞에 정렬된다.) 앞에서부터 N명은 A로, 그 뒤 N명은 B로 이동시킨다. 시간복잡도는 O(NlogN). 소스코드 .. 2020. 6. 4. [leetcode][45] Jump Game II 문제 : https://leetcode.com/problems/jump-game-ii/ 음수가 아닌 정수 배열이 주어진다. 배열 값은 그 인덱스에서 1번의 점프로 최대 몇 개의 인덱스를 이동할 수 있는지를 의미한다. 즉, arr[3] = 2인 경우 3인덱스에서 4, 5로 이동할 수 있다. (4, 5로 이동할 때 1번 점프로 이동가능을 의미) 0인덱스에서 시작할 때, 최소 몇 번의 점프로 마지막 인덱스까지 도달할 수 있는가. (마지막 인덱스까지 도달할 수 없는 경우는 없다고 한다.) 그리디로 해결가능하다. 0부터 탐색하면서 탐색 중인 인덱스까지 도달하기 위해 필요한 최소 점프횟수(ans), 최대로 이동할 수 있는 인덱스(maxInd), 그리고 임시 최대이동가능 인덱스(tmp)를 구한다. tmp는 임시로 저.. 2020. 4. 26. [Codejam][2020][QR] 3. Parenting Partnering Returns 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9 각 활동의 시작, 종료 시간이 주어지면 Jamie, Cameron이 활동을 나눠서 한다고 하자. 활동 중 다른 활동을 중복으로 수행은 불가능하다. (한 번에 하나의 활동만 가능) 두 사람이 모든 활동을 나눠가질 수 없을 때는 IMPOSSIBLE을 출력하자. 가능하다면 각 활동을 수행하는 사람의 이니셜 배열을 구하자. greedy의 대표 문제. 각 활동들의 시작 시간을 기준으로 오름차순 정렬한다. 정렬하면 활동들의 순서가 뒤섞이므로 배열에 인덱스를 추가하고 정렬한다. Jamie, Cameron 를 순서대로 활동 중인지 체크한다. 이를 위해.. 2020. 4. 18. [Codejam][2020][QR] 2. Nesting Depth 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f 숫자 문자열이 주어질 때, 이를 엄격하게 괄호로 묶어서 반환하라. 이 때, 괄호의 개수는 최소로 하고 숫자는 일의 자리로 판단하라 (ex. 10 은 1과 0으로 인식되지 10으로 인식되진 않는다.) 엄격하게 괄호로 묶는 방법은 숫자만큼 해당 문자를 괄호로 감싸면 된다. example) 0000 -> 0000 101 -> (1)0(1) 111000 -> (111)000 1 -> (1) 1324 -> (1((3)2((4)))) 문자열을 탐색하면서 이전 숫자와 현재 탐색중인 숫자의 차이를 구한다. 1. 이전 숫자가 현재 숫자보자 작다면, (열.. 2020. 4. 18. [Kickstart][2020][Round A] 1. Allocation 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56 N 개의 집이 판매중이고, 각 집의 판매가격이 주어진다. 내가 B 달러를 가지고 있을 때, 최대 몇 채의 집까지 살 수 있는가? 구입할 수 있는 최대 개수의 집을 구하려면 가격이 작은 집들부터 구입하면 된다. -> 그리디 문제이다. 판매 가격을 오름차순 정렬한다. 앞에서부터 탐색하면서 B 달러로 탐색 중인 집을 구입할 수 있다면 정답 +1 을 해주고 B달러에 구입한 집 가격을 빼준다. 탐색 중인 집을 남은 달러로 구입할 수 있다면 판매 가격을 오름차순 정렬했기 때문에 이후에 나올 집들도 구매할 수 없을 것이다. 따라서 탐색을 종료하고.. 2020. 3. 23. [hackerrank] Grid Challenge 문제 : https://www.hackerrank.com/challenges/grid-challenge/problem NxM 배열이 주어지면 각 열이 사전 순 배열이 될 수 있는지 판단하는 문제. 같은 행에 있는 문자들은 순서를 변경할 수 있다. 각 열을 사전순으로 배열한 후 같은 행에 있는 문자들이 사전순으로 정렬되어 있는지 판단하면 된다. 각 열을 사전순으로 배열한다면 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 a1 b2여서 2번째 열이 사전순 배열이 안되어 a2보다 작은 a1을 a2대신 사용한다고 하더라도 b1.. 2020. 2. 22. 이전 1 2 3 4 5 6 다음