알고리즘 문제/Leetcode283 [leetcode][933] Number of Recent Calls 문제 : https://leetcode.com/problems/number-of-recent-calls 조건에 t는 점점 커진다고 적혀있다.따라서 한 번 범위에 포함되지 않는 핑은 앞으로도 계속 포함되지 않을 것이다.최소 범위는 t - 3000인데 t가 계속 커질 것이므로 t-3000도 계속 커질 것임.따라서 한 번 ping < t - 3000 가 된 ping은 앞으로도 최소 범위 t -3000 이전 값이 된다. 큐를 이용한다.ping 함수에서 받는 t를 큐에 저장한다.큐의 앞에서부터 t - 3000 보다 작은 것은 제외 시킨다. 다 제외 시켰을 때 큐의 크기를 반환시킨다. 시간복잡도는 O(N) 일 듯. N은 입력에서 받는 ping 함수 개수. 소스코드 : https://gist.github.com/fp.. 2018. 11. 9. [leetcode][920] Number of Music Playlists 문제 : https://leetcode.com/problems/number-of-music-playlists/ DP로 풀었다.dp[N][L] = N개의 노래로 L개의 노래가 있는 플레이 리스트를 만드는 경우의 수. 만약 i개의 노래로 j개의 노래가 있는 플레이 리스트를 만들었다고 할 때(dp[i][j]) 다음에 추가하는 노래는 플레이리스트에 없는 노래거나 플레이리스트에 이미 있는 노래. 이렇게 2가지 경우가 있다. 플레이리스트에 없는 노래를 추가한다면 만들어지는 dp배열은 dp[i+1][j+1]이다. (노래가 하나 추가되고 플레이리스트도 하나 느므로)dp[i][j]가 추가될 수 있는 노래의 개수(N - i = 전체 - 이미 들은 노래)만큼 추가되므로 dp[i+1][j+1] += dp[i][j] * (N .. 2018. 11. 6. [leetcode][66] Plus One 문제 : https://leetcode.com/problems/plus-one/ 가산기를 만들어보자.carry(올림수) 변수를 하나 두고 1로 세팅한다. 원래는 0으로 시작하지만 1을 더하는 값을 구하는 것이기 때문에 1을 세팅한다.배열의 뒤에서부터 carry와 수를 더해가면서 정답 배열의 뒤에서부터 채운다.carry는 더한 값에 / 10한 값이다. (10을 넘겨야만 다음 수에 1을 더해주므로)정답 배열에 들어가는 수는 더한 값에 % 10을 한 값이다.배열을 모두 탐색이 끝났을 때(배열을 전부 탐색해도 되고 carry가 0이 나올때까지만 탐색해도 됨) carry가 1이라면 정답 배열의 가장 앞에 1을 추가해준다. 시간 복잡도는 O(N). 소스 코드 : https://gist.github.com/fpdjs.. 2018. 11. 5. [leetcode][918] Maximum Sum Circular Subarray 문제 : https://leetcode.com/problems/maximum-sum-circular-subarray/ 최대 부분 문자열과 최소 부분 문자열을 구한다.최대 부분 문자열의 합과 배열의 모든 총합 - 최소 부분 문자열 중에 큰 값이 정답이 된다.모든 수가 음수인 경우는 음수 중에 가장 큰 값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/fa784f6bf9e9296b8670fc07759ff466 2018. 11. 5. [leetcode][53] Maximum Subarray 문제 : https://leetcode.com/problems/maximum-subarray/ 문자열을 앞에서부터 더해간다.더한 값이 양수라면 앞으로의 탐색 값에 더했을 때 더 큰 합을 기대할 수 있다.하지만 음수라면 무슨 수를 더해도 더 작은 합이 나올 것이다.따라서 더한 값이 음수가 나오면 부분합을 0으로 초기화시키고 다시 배열 값을 더해간다.이렇게 구한 부분합들 중 최대값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/157788123006e2e518e352129645b170 2018. 11. 4. [leetcode][91] Decode Ways 문제 : https://leetcode.com/problems/decode-ways/ DP로 풀었다.알파벳이 될 가능성이 있는 수는 한자리 수(1~9)이거나 두 자리 수(10~26)다.문자열을 앞에서부터 탐색하면서 한자리 수와 현재 탐색중인 문자보다 하나 작은 문자를 합쳐서 두 자리 수를 구해 이들이 알파벳이 될 수 있는지 체크한다. ex) "12" -> 1, 2, 12 체크.탐색 중인 문자열 인덱스를 ind라 하고 ind번째 문자열까지 만들 수 있는 알파벳문자열의 경우의 수를 저장하는 d[ind] 배열을 만든다. 한 자리 수가 숫자가 될 수 있는 경우 ind-1 번째 문자열까지 만들 수 있는 알파벳 배열의 수(d[ind-1])를 d[ind]에 더한다. (d[ind-1]로 만들 수 있는 알파벳 문자열 뒤.. 2018. 11. 2. 이전 1 ··· 43 44 45 46 47 48 다음