912. Sort an Array
정렬 구현 문제 뭐 별거 없고 그냥 정렬을 구현하면 된다. nlogn 정렬들 중 아무거나 구현하면 되는데 제일 간단하면서 안정적인 merge sort를 구현하였다. 퀵 소트, 힙 소트 등 기억이 잘 안나네 ㅋㅋ
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
264 263 287. Find the Duplicate Number
배열에서 중복된 수를 찾는 문제. 단 배열의 조작은 불가능하고, 공간복잡도는 O(1)이어야 한다. 제약 조건이 없다면 매우 쉬운 문제... 하지만 제약 조건과 follow up을 전부 만족하려면 특별한 알고리즘이 필요하다. 일단 해당 문제를 링크드 리스트로 볼 수 있는데 nums의 값을 인덱스로 해서 다음 리스트로 넘어가는 링크드 리스트로 가정하면 링크드 …
262 57. Insert Interval
구간들이 주어질 때 새로운 구간을 추가하는 문제. 구간들은 겹칠 경우 머지되어야 한다. 약간 그리디 느낌? 겹치지 않은 경우는 그냥 결과 배열에 넣으면 되고 겹치는 경우는 left는 겹치는 구간들의 최소, right는 겹치는 구간들의 최대로 해서 추가하면 된다. 좀 지저분하게 짜긴 했지만 결과도 맞게 나오고 O(n)이라 별 상관 없다.
261 452. Minimum Number of Arrows to Burst Balloons
풍선의 x 좌표 구간이 주어질 때 수직으로 화살을 쏴서 전부 터뜨릴 수 있는 최소한의 화살 개수를 구하는 문제. 그리디로 풀면 된다. 먼저 정렬부터 해주자. 그런 다음 화살을 발사할 범위를 계속 계산하면서 가능한지 판단하면 된다. 좀 더 자세히 설명하면 겹치는 풍선의 범위를 계속 계산해나가면 된다. 풍선의 오른쪽 좌표의 최소값, minRight를 계속 갱신…
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) …