easy67 [leetcode][941] Valid Mountain Array 문제 : https://leetcode.com/problems/valid-mountain-array/ 배열 A의 크기가 3미만인 것들은 정답이 될 수 없다. (값이 증가하는 범위와 감소하는 범위가 존재하려면 적어도 3개의 값이 필요하므로)배열의 첫번째 값과 두번째 값을 비교했을 때 증가하지 않는다면 정답이 될 수 없다. (값이 증가하는 범위가 존재하지 않으므로)위 두 경우를 먼저 체크한다. 이후 배열의 연속된 값 2개를 비교하면서 다음을 체크한다.1. A[i-1] == A[i] : 값이 같은 경우 -> 정답이 될 수 없다.2. A[i-1] 이전에 값이 감소하는 경우가 나온경우 정답이 될 수 없다.3. A[i-1] > A[i] : 값이 감소하는 경우 -> 이후부터는.. 2018. 11. 25. [leetcode][746] Min Cost Climbing Stairs 문제 : https://leetcode.com/problems/min-cost-climbing-stairs/ 기본 dp 문제.i 번째 계단으로 갈 수 있는 계단은 i-1, i-2번째 계단이다.따라서 i번째 계단으로 갈 수 있는 최소 비용은 (i-1번째까지 가는 최소 비용 + i번째 계단을 밟는 비용)과 (i-2번째까지 가는 최소 비용 + i번째 계단을 밟는 비용) 중 작은 비용이다.따라서 점화식은 아래와 같다.d[i] = min(d[i-1], d[i-2]); (d[i] = i번째 비용까지 가는데 드는 최소 비용) 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/58c995f1439d437a2eed60bb517cb882 2018. 11. 11. [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][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][53] Maximum Subarray 문제 : https://leetcode.com/problems/maximum-subarray/ 문자열을 앞에서부터 더해간다.더한 값이 양수라면 앞으로의 탐색 값에 더했을 때 더 큰 합을 기대할 수 있다.하지만 음수라면 무슨 수를 더해도 더 작은 합이 나올 것이다.따라서 더한 값이 음수가 나오면 부분합을 0으로 초기화시키고 다시 배열 값을 더해간다.이렇게 구한 부분합들 중 최대값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/157788123006e2e518e352129645b170 2018. 11. 4. [leetcode][929] Unique Email Addresses 문제 : https://leetcode.com/problems/unique-email-addresses/ set을 이용한다.이메일을 앞에서 부터 탐색하면서 '@'가 나오기 전까지 문자는 저장하고 '.'은 무시하면서 이메일을 저장한다. 저장하면서 '+'가 나오면 이후부터 '@'가 나오기 전까지는 무시한다.@이후부터 나오는 도메인은 그대로 저장한다.ex) m.y+name@email.com -> my@email.com 모든 emails 배열을 탐색해서 set을 채웠을 때, set에 있는 이메일 개수가 정답이 된다.시간복잡도는 emails 배열의 크기가 N, emails[i]의 크기가 M이라 했을 때, O(N*M*logN). 소스코드 : https://gist.github.com/fpdjsns/3e2400e0e.. 2018. 10. 28. 이전 1 ··· 8 9 10 11 12 다음