본문 바로가기

알고리즘 문제408

[CodeJam][2017][Round 1B] B. Stable Neigh-bors 문제 : https://code.google.com/codejam/contest/8294486/dashboard#s=p1&a=1 우선은 R, Y, B만 있는 경우를 생각하자.이 때는 두 번에 나눠서 정답을 만들 수 있다.1회차에 R, Y, B를 순서대로 나열한다. (R+Y+B / 2의 오름차순 한 개수만큼만 넣는다. - 반)예를 들어, R 3개, Y 2개, B 1개라고 하면 먼저 3개를 나열한다. ex) RRR그리고 2회차에 만든 정답 문자열 사이사이에 알파벳을 다시 차례대로 넣는다. ex) RYRYRB알파벳 R, Y, B가 (R+Y+B)/2 보다 크다면 2회차 때 연속되게 나올 수 밖에 없기 때문에 정답이 불가능하다. -> IMPOSSIBLE 주의할 점은 R, Y, B를 순서대로 나열하면 안된다는 것이.. 2019. 3. 2.
[leetcode][997] Find the Town Judge 문제 : https://leetcode.com/problems/find-the-town-judge/ 다른 사람한테 믿음을 받은 횟수(?)를 저장한는 배열(cnt라고 하자)을 하나 만든다.trust 배열을 탐색하며 해당 배열을 갱신한다.조건에서 판사는 아무도 믿지 않으므로 다른 사람을 믿는다고 한 사람의 횟수는 -N으로 초기화한다. (절대 정답이 될 수 없게)trust 배열을 탐색하며 cnt 배열을 갱신했으면 cnt 배열을 탐색하면서 요소 값이 N-1인(자기를 제외한 모든 사람의 수) 인덱스가 정답이 될 수 있다.만약 가능한 인덱스가 2번 이상 나오면 정답이 될 수 있는 경우는 유일하다고 했으므로 -1을 반환하고 1번 나오면 그 사람 번호를 반환한다. 시간 복잡도는 O(|trust| + N). 소스코드 :.. 2019. 3. 2.
[Kickstart][2019]2. Mural 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/0000000000058b89 부분합으로 풀었다.벽은 가장자리부터 파괴되고 벽의 총 N개라고 했을 때 최대 (N+1)/2 개의 벽을 칠할 수 있다.즉, 문제를 간단하게 보면 연속되는 (N+1)/2개의 벽을 선택할 때 구할 수 있는 최대 값을 구하는 문제이다.부분합 배열을 sum, (N+1)/2를 cnt라고 했을 때, sum[i] - sum[i-cnt]가 (N+1)/2개의 벽을 선택했을 때의 가치이고. i 범위가 [cnt, N] 일 때 구한 가치 중 최대 값이 정답이 된다.시간 복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns.. 2019. 2. 25.
[Kickstart][2019]1. Number Guessing 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/00000000000588f4 이진탐색으로 풀었다.정답이 될 수 있는 범위의 가장 최소, 최대 값을 가지고 그 중간 값이 정답이 될 수 있는지 확인한다.정답이 될 수 있는 경우 종료하고, 중간 값보다 정답이 작다고 한다면 범위는 최소 ~ 중간 값 -1이 되므로 최대 값을 중간 값 -1 로 갱신한다.중간 값보다 정답이 크다고 한다면 범위는 중간 값 + 1 ~ 최대가 되므로 최소 값을 중간 값 + 1 로 갱신한다.이를 정답을 구할 때까지 혹은 N번 반복한다. 소스코드 : https://gist.github.com/fpdjsns/c129fea086f319e7340126.. 2019. 2. 25.
[CodeJam][2017][Round 1B] A. Steed 2: Cruise Control 문제 : https://code.google.com/codejam/contest/8294486/dashboard N개의 말 정보를 탐색하면서 도착지까지 가는데 드는 시간 중 최대 시간을 구한다.말이 도착지까지 가는데 드는 시간 = (D - K) / S정답은 D / 구한 최대 시간 이다. 자료형은 double로 해야 조건에 맞는다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/bba7e68cc46d3f7e77500d0caecaa74c 2019. 2. 17.
[leetcode][994] Rotting Oranges 문제 : https://leetcode.com/problems/rotting-oranges/ BFS로 풀었다.백준의 토마토와 비슷한 문제. 큐에 x, y, minutes를 저장한다.배열을 한 번씩 탐색하면서 썩은 오렌지인 경우 큐에 (x, y ,0)을 저장한다.그리고 오렌지(fresh + rotten)의 개수를 저장한다. 배열 탐색이 끝나면 큐가 빌때까지 오렌지 썩음을 전염시킨다.큐에서 요소를 빼낼 때 rotten 오렌지의 개수를 구한다.큐의 앞의 요소부터 탐색하면서 상하좌우 배열을 탐색한다. 만약 탐색한 grid 값이 fresh한 오렌지라면 큐에 넣는다. 이 때 minutes는 +1 해준다.큐에서 마지막으로 꺼낸 요소의 minutes가 정답이 된다.만약 총 오렌지 개수와 rotten 오렌지 개수가 같지.. 2019. 2. 17.

티스토리툴바