1492. The kth Factor of n
n의 약수 중 k번째 작은 수를 찾는 문제 그냥 모든 약수를 구하고 정렬 후 k번째를 찾으면 된다. 정렬해도 O(n) 이하긴 한데 (O(sqrt(n) log sqrt(n))) 정렬 없이 풀 수 있다. 약수 저장 배열을 2개 두면 된다. 약수를 구할 때 d가 약수이면 배열에 d를 넣고 다른 배열은 n/d를 집어넣으면 각 배열은 정렬이 되어있는 상태이고 k번째…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
284 283 273. Integer to English Words
숫자를 영어로 변환하는 문제. 문제는 매우 쉽지만 아주 지저분하다. 1000씩 끊고 10씩 끊는 등 숫자를 잘게 나누면 그나마 덜 지저분하게 짤 수 있다. 오타 조심..! (Ninety 잘못 쳐서 1번 틀림..)
282 312. Burst Balloons
풍선을 터뜨릴 때 최대 점수를 구하는 문제. 터뜨릴 때는 풍선의 양쪽과 현재 값을 곱한 값이 점수가 된다. 딱 보면 해답이 나오지 않는 DP 문제. 문제를 반대로 생각해봐야 한다. 일단 문제 그대로는 이전 선택이 이후 선택에 영향을 주기 때문에 DP를 적용하기 어렵다. 다만, 풍선을 먼저 터뜨릴 것을 고르는 것이 아니고 마지막에 터뜨릴 것을 고른다고 생각하…
281 517. Super Washing Machines
세탁기에 옷들이 있고 옷들을 한번에 하나씩 이동시킬 수 있을 때 모든 옷의 개수가 같게 만드는 최소 이동 횟수를 구하는 문제. 일단 전체 합이 개수의 배수가 되어야 하니 먼저 예외 처리를 해주고, 모든 세탁기의 옷은 합 / 개수가 되어야 한다. 여기서 간단하게 드는 생각은 가장 큰 값 - (합 / 개수) 하면 답일까? 싶은데 반례가 존재한다. [0,0,2,…
280 279 2. Add Two Numbers
링크드 리스트 형태로 수가 2개 주어질 때 더한 값을 링크드 리스트로 출력하는 문제. 자리수는 계산하기 쉽게 반대로 되어 있다. 간단한 링크드 리스트 구현 문제. 그냥 자리수대로 한 칸 씩 앞으로 가면서 더해주면 된다.
278 3016. Minimum Number of Pushes to Type Word II
주어진 문자열을 키패드로 입력할 때 버튼 누르는 횟수의 최소를 구하는 문제. 키패드는 자유롭게 배치할 수 있다. 간단한 문제. 문자열의 문자들의 개수를 센 뒤, 개수가 많은 문자를 키패드의 앞쪽으로 배치하면 된다.
277 2134. Minimum Swaps to Group All 1's Together II
1을 임의의 0과 swap해서 1이 연속되게 만드는 문제. 단, 배열은 원형이다 한 덩어리로 만든다고 생각해보면 1이 나온 개수만큼 어딘가에 뭉쳐놓는다고 볼 수 있다. 그렇게 되면 슬라이딩 윈도우 방법으로 1이 나온 개수 크기의 윈도우로 배열을 순회하면서 그 윈도우 안의 0의 개수가 swap 횟수가 된다. 원형 처리는 간단하게 배열을 그냥 뒤에 그대로 붙여…
276 2053. Kth Distinct String in an Array
문자열의 배열이 주어질 때 k번째 distinct한 문자열을 찾는 문제 그냥 Counter로 개수 세고 1개인 애들 중 k번째를 리턴하면 된다. easy 문제 풀면 자괴감 드네... (오늘의 문제니깐 푼다... ㅋㅋ)
275 1508. Range Sum of Sorted Subarray Sums
모든 subarray의 합을 정렬한 후 left부터 right 까지 합을 구하는 문제 그냥 문제 그대로 모든 subarray에 대해 합을 구한 후 정렬하면 된다. 당연하게도 합을 구할 때는 prefix sum으로 구해야 시간 안에 들어온다. 시간 복잡도는 정렬 때문에 O(n^2 log(n^2)) sliding window, binary search를 쓰면 …