452. Minimum Number of Arrows to Burst Balloons
풍선의 x 좌표 구간이 주어질 때 수직으로 화살을 쏴서 전부 터뜨릴 수 있는 최소한의 화살 개수를 구하는 문제. 그리디로 풀면 된다. 먼저 정렬부터 해주자. 그런 다음 화살을 발사할 범위를 계속 계산하면서 가능한지 판단하면 된다. 좀 더 자세히 설명하면 겹치는 풍선의 범위를 계속 계산해나가면 된다. 풍선의 오른쪽 좌표의 최소값, minRight를 계속 갱신…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
261 260 525. Contiguous Array
배열에서 0과 1의 숫자가 같이 나오는 부분 배열을 구하는 문제 지금까지 0과 1이 나온 카운트를 트래킹 해주면서 같은 카운트가 나왔다면 그때 0과 1이 같은 개수로 나온 배열이 된다. 말로 하니 어려운데 에디토리얼 그림을 보면 이해하기 쉽다. [0 0 1 0 0 0 1 1] 에 대한 카운트에 따른 그림이고 A, B, C 지점을 찍었을 때 해당 구간은 0과…
259 201. Bitwise AND of Numbers Range
left, right가 주어질 때 [left, right] 사이의 모든 수에 대해 AND 연산을 한 값을 구하는 문제. AND 연산의 특성 상 0이 하나라도 있으면 다 0이 된다. 즉, left, right 둘 간의 prefix를 찾으면 그 뒤로는 전부 0이 될 것이다. 그래서 left, right의 공통 prefix를 찾으면 되는데... 처음에 이걸 좀 …
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
배열이 주어질 때 각 원소와 다른 원소와의 차이의 절대값의 합을 모두 구하는 문제. 문제를 잘 노려보니 뭔가 규칙이 보일 듯 하다. 일단 모든 원소를 다 더해보면 뭔가 나오는데 첫 번째 답은 모든 원소의 합 - 자기 자신 * 배열 길이가 된다. 크기 순으로 정렬이 되어 있으므로 여기부터 시작해보자. 두 번째 원소는 첫 번째 원소보다 큰 만큼 절대값의 합이 …
255 231. Power of Two
n이 주어질 때 2의 제곱 (2^x) 인지 판단하는 문제. 단순 반복문은 너무 쉬우니 follow up 방식으로 해보자. 비트 연산을 쓰면 된다. 2의 제곱이라는 것은 비트로 나타냈을 때 ...0001000... 이런 꼴로 나오는 수인데 1을 뺐을 때 ...0000111... 처럼 1 자리 뒤가 전부 1로 바뀐다. 이 성질을 이용하면 n & (n - 1) …
254 2402. Meeting Rooms III
미팅룸이 n개 있고 미팅 시간이 주어졌을 때 가장 미팅이 많이 한 룸을 구하는 문제. 미팅이 가능한 방이 여러개 있을 경우 가장 작은 번호의 방이 선택되며 현재 가능한 방이 없다면 가장 빠른 방을 사용한다. 그리디 방식으로 가능하다. 일종의 스케줄링 + 구현 문제라고 봐도 될 듯. 문제에 나온 그대로 작은 방부터 탐색하면서 미팅이 가능하면 미팅을 하면 된다…
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)이 …