본문 바로가기

easy67

[algospot][PICNIC] 소풍 문제 : https://algospot.com/judge/problem/read/PICNIC N이 10으로 아주 작아서 완전탐색을 돌렸다. 인덱스를 0부터 N까지 탐색하면서 현재 탐색중인 인덱스 사람이 친구가 될 수 있는 쌍을 구한 뒤 인덱스를 탐색한다. N = 4 쌍이 가능한 조합 : (0,1) (1,2) (2,3) (3,0) (0,2) (1,3) 라고 한다면 0부터 탐색하면서 0과 쌍이 가능한 조합을 탐색 후, 쌍이 맺어진 사람은 다음번에는 짝을 못이루므로 따로 체크해둔다. 0 : (0,1) -> 1 : 이미 짝이 있음 -> 2 : (2,3) -> 3 : 이미 짝이 있음 -> 4 : 정답 가능 0 : (0,2) -> 1 : (1,3) -> 2 : 이미 짝이 있음 -> 3 : 이미 짝이 있음 -> 4 .. 2019. 5. 28.
[algospot][QUADTREE] 쿼드 트리 뒤집기 문제 : https://www.algospot.com/judge/problem/read/QUADTREE 분할정복 문제. 만약 입력으로 받은 문자열의 길이가 1이라면 이는 압축이 되는 경우가 없을 때이다. (x가 입력에 없음) 이 때는 해당 문자열을 그대로 반환한다. 문자열 길이가 1이 아닌 경우는 첫 번째 문자가 반드시 x가 된다. 입력으로 받은 문자열을 앞에서부터 탐색하면서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분을 배열에 각각 저장한다. 탐색 하면서 나올 수 있는 경우는 총 3가지이다. 탐색 중인 문자(now)가 1. 'w'인 경우 : 배열에 "w" 저장 2. 'b'인 경우 : 배열에 "b" 저장 3. 'x'인 경우 : 탐색 중인 인덱스부터 시작하는 문자열로 다시 왼쪽 위, 오른쪽 위, .. 2019. 5. 24.
[leetcode][1013] Pairs of Songs With Total Durations Divisible by 60 문제 : https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/ map을 이용했다.[30, 20, 150, 100, 40, 60, 60] 이 입력이 주어졌으면 이를 60으로 나눈 값들의 개수를 map에 저장한다. key = 60으로 나눈 나머지. value = 개수즉, 위 예제에서는 [30, 20, 30, 40, 40, 0, 0]을 key, value형태에 맞춰 넣으면{0, 2}, {20, 1}, {30, 2}, {40, 2}가 map에 들어간다.짝이 될 수 있는 것은 20 - 40. 30 쌍이다. 0 쌍의 개수는 2 * 1 = 2. 20 - 40 쌍의 개수는 1 * 2 = 2.30 쌍의 개수는 2 * 1 = 2.. 2019. 3. 17.
[leetcode][1009] Complement of Base 10 Integer 문제 : https://leetcode.com/problems/complement-of-base-10-integer/ 6 - 0 3 - 1 1 - 1 0 - 1 N을 6이라 했을 때, 2진수는 1110이다. 따라서 보수는 0001이 된다. N을 2로 나눈 나머지 값이 0이면 1을 1이면 0을 해당 자리 수 값에 곱해서 정답에 더한다. N이 0인 경우 보수는 1이므로 이 때는 예외처리했다. 시간 복잡도는 O(logN). + N = 5(101) 일 때, 1의 보수를 구해보자. 1000 - 101 = 011 011 - 1 = 010 2진수의 비트수는 log2(N)으로 구할 수 있다. 예를 들어 N = 5(101) 일 때, log2(5) = 2.32193. 이에 +1을 한 뒤 정수로 바꿔주면 3이 된다. 이제 .. 2019. 3. 17.
[leetcode][1005] Maximize Sum Of Array After K Negations 문제 : https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/ 배열을 오름차순 정렬한다.음수이고 K가 양수이면 -1을 곱해서 sum을 더한다(K도 1씩 감소). 그러면서 마지막으로 -1을 곱한 수를 따로 저장해둔다.양수이고 K가 양수이면 K를 2로 나눈 나머지를 구한다. 나머지가 1이라면 양수에 -1을 곱해야 하는데 이때, 마지막으로 -1을 곱한 음수와 비교해야 한다.예를 들어, [-8,-5,-3,-5,-2,3] 이고 K가 6일 때, 마지막으로 -1을 곱한 음수는 -2이고. -1을 곱할 양수를 3이라고 하자.총합은 가장 작은 양수인 3을 음수로 만드는 것보다 -2를 양수로 만드는 것이 더 크다.그러므로 -2는 양수로 만들지 않고 3.. 2019. 3. 16.
[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.

티스토리툴바