201. Bitwise AND of Numbers Range
left, right가 주어질 때 [left, right] 사이의 모든 수에 대해 AND 연산을 한 값을 구하는 문제. AND 연산의 특성 상 0이 하나라도 있으면 다 0이 된다. 즉, left, right 둘 간의 prefix를 찾으면 그 뒤로는 전부 0이 될 것이다. 그래서 left, right의 공통 prefix를 찾으면 되는데... 처음에 이걸 좀 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
259 258 787. Cheapest Flights Within K Stops
비행 경로가 그래프로 주어질 때 k번 이하의 노드를 거쳐서 src부터 dst까지 가는 최소 비용을 구하는 문제. 쉬워 보이는데 어려운 문제. 일단 다익스트라로 풀긴 풀었는데 틀리고 시간초과도 나고... 오랜만에 다익스트라 써서 그런지 몰라도 꽤 삽질했다. 일단 최소 비용이므로 다익스트라 돌리면 되는데 문제는 k번 이하를 거쳐야 한다. 그래서 거친 횟수를 저…
257 29. Divide Two Integers
두 정수를 곱하기, 나누기 연산 없이 나눈 몫을 구하는 문제. 뭔가 쉬워 보이는데 어려운 문제이다. 일단 나누기를 다시 생각해보면 여러 번 뺀다고 생각할 수 있다. 즉, 10/3 은 10을 3으로 3번 뺄 수 있으므로 답이 3이 나오게 된다. 하지만 빼는 것을 하나씩 다 하면 시간 초과가 난다. 더 빨리 뺄 수 있는 방법을 찾아야 하는데 이것이 비트 시프트…
256 1685. Sum of Absolute Differences in a Sorted Array
배열이 주어질 때 각 원소와 다른 원소와의 차이의 절대값의 합을 모두 구하는 문제. 문제를 잘 노려보니 뭔가 규칙이 보일 듯 하다. 일단 모든 원소를 다 더해보면 뭔가 나오는데 첫 번째 답은 모든 원소의 합 - 자기 자신 * 배열 길이가 된다. 크기 순으로 정렬이 되어 있으므로 여기부터 시작해보자. 두 번째 원소는 첫 번째 원소보다 큰 만큼 절대값의 합이 …
253 1642. Furthest Building You Can Reach
벽돌의 개수와 사다리의 개수가 주어질 때 빌딩 사이를 가장 멀리 이동할 수 있는 거리를 구하는 문제. 빌딩의 높이가 같거나 낮으면 그냥 이동할 수 있으며, 벽돌은 빌딩 사이의 높이 차이만큼 사용되고 사다리는 높이와 상관없이 한개씩 사용된다. 그리디로 해결할 수 있다. DP로 해봤는데 bricks의 공간?이 너무 넓어서 메모리 초과가 난다... 빌딩 사이의 …
252 1481. Least Number of Unique Integers after K Removals
배열의 수들을 k개 삭제했을 때 unique한 수의 최소 개수를 구하는 문제. 그리디로 풀면 된다. 갯수가 적은 수부터 삭제하면 unique한 수를 최소한으로 줄일 수 있다. map으로 개수를 세고 개수를 기준으로 정렬한 뒤 앞에서부터 제거하면 된다. 에디토리얼 보니 O(n)으로도 되는데 정렬하지 않고 나온 개수를 다시 맵에 넣는 방식으로 하면 O(n)이 …
251 2971. Find Polygon With the Largest Perimeter
주어진 배열의 값의 길이의 선으로 만들 수 있는 도형의 최대 둘레를 구하는 문제. 문제에 답이 있는데 즉, 다른 모든 변의 길이의 합보다 큰 변이 없어야 한다. 정렬한 후 둘레를 하나씩 더해보면서 변의 길이보다 큰지 체크해주면 된다.
250 2149. Rearrange Array Elements by Sign
배열이 있을 때 양수 음수가 번갈아 나오게 하면서 양수 음수의 순서를 유지한 채로 재정렬하는 문제. 너무 쉽다... 일단 처음 풀이는 양수와 음수 배열을 각각 선언 후 하나씩 빼서 최종 배열을 만들었는데 O(2n). 이것보다 더 줄일 수 있다. 일종의 투 포인터로 양수와 음수가 나올 때마다 정답 배열에 끼워넣는 방식으로 넣어주면 된다. O(n)
246 647. Palindromic Substrings
문자열이 주어질 때 palindrome인 substring의 개수를 구하는 문제. 처음 보면 좀 어려워 보이는데 팰린드롬 체크를 좌 우로 한 칸씩 늘려가면서 체크하는 방식으로 생각하면 쉽게 풀린다. 즉, s[left : right] 가 팰린드롬일 때 s[left - 1] == s[right + 1]이면 s[left - 1 : right + 1]도 팰린드롬이…
245 368. Largest Divisible Subset
리스트가 주어질 때 모든 subset이 각각의 배수가 되도록 하는 최대 길이의 subset을 구하는 문제. 일단 순서가 중요하지 않으므로 정렬을 먼저 하자. 그러면 뭔가 보이는데 두 인덱스를 i, j (i < j) 라 했을 때 nums[j] % nums[i] == 0이면 뒤로 이어 붙일 수 있다. 이런식으로 모든 원소에 대해 길다면 이어 붙이는 식으로 이어…