Algorithms/문제풀이

[LeetCode] Maximum Subarray 풀이

문제 링크https://leetcode.com/problems/maximum-subarray/내 풀이시간 복잡도O(N^2)공간 복잡도O(1)class Solution { public int maxSubArray(int[] nums) { int max = Integer.MIN_VALUE; for (int i = 0; i 최적화시간 복잡도O(N)공간 복잡도O(1)특징브루트 포스 탐색을 통한 코드는 쉽지만 O(N^2)의 시간 복잡도를 가져서 범위가 큰 경우는 부적합하다.Kadane’s Algorithm이라는 알고리즘을 통해 연속된 부분 배열의 합 중 가장 큰 값을 찾는다.Kadane’s Algorithm은 최대 부분합을 효율적으로 구하기 위해, 배열을 한 번 순회하면서 각 요소를..

2024. 9. 25. 00:45

Algorithms/문제풀이

[LeetCode] Number of 1 Bits 풀이

문제 링크https://leetcode.com/problems/number-of-1-bits/내 풀이시간 복잡도O(K)32비트 시스템에서는 O(32), 64비트 시스템에서는 O(64)공간 복잡도O(1)class Solution { public int hammingWeight(int n) { int answer = 0; while (n > 0) { int remainder = n % 2; if (remainder == 1) { answer++; } n /= 2; } return answer; }}최적화시간 복잡도O(K)K는 숫자 n의 2진수에..

2024. 9. 20. 20:00

Algorithms/문제풀이

[LeetCode] Contains Duplicate 풀이

문제 링크https://leetcode.com/problems/contains-duplicate내 풀이시간복잡도Arrays.stream 처리하는데 O(N)Arrays.asList 처리하는데 O(N)HashSet 데이터 주입하는데 O(N)O(N) + O(N) + O(N) = O(3N) = O(N)공간복잡도O(N)class Solution { public boolean containsDuplicate(int[] nums) { Set set = new HashSet(Arrays.asList(Arrays.stream(nums).boxed().toArray(Integer[]::new))); return set.size() != nums.length; }}최적화시간복잡도O(N)공..

2024. 9. 19. 00:15

Algorithms/문제풀이

[LeetCode] Valid Parentheses 풀이

문제 링크https://leetcode.com/problems/valid-parentheses내 풀이시간복잡도O(N)공간복잡도O(N)class Solution { public boolean isValid(String s) { Stack stack = new Stack(); for (char ch : s.toCharArray()) { if (ch == ')' || ch == '}' || ch == ']') { if (stack.isEmpty()) { return false; } char peeked = stack.peek(); ..

2024. 9. 3. 21:36

Algorithms/문제풀이

[LeetCode] Roman to Integer 풀이

문제 링크https://leetcode.com/problems/roman-to-integer/내 풀이시간복잡도O(N)공간복잡도O(1)import java.util.*;class Solution { public int romanToInt(String s) { int result = 0; Map map = new HashMap(); map.put("IV", 4); map.put("IX", 9); map.put("XL", 40); map.put("XC", 90); map.put("CD", 400); map.put("CM", 900); map.put("I", 1); map.put("..

2024. 9. 2. 01:00

Algorithms/문제풀이

[LeetCode] Palindrome Number 풀이

문제 링크https://leetcode.com/problems/palindrome-number포인터 방식시간복잡도 O(N)N자리의 정수를 문자열로 변환하는 O(N)N자리의 정수를 절반만 순회하기 때문에 O(N/2)공간복잡도 O(N)N자리의 정수를 문자열로 변환하는 O(N)class Solution { public boolean isPalindrome(int x) { if (x  리버스 숫자 구하기시간 복잡도 O(log(N))입력받은 정수를 N이라고 하고 그것의 자릿수를 D라고 했을 때, log(N) + 1공간 복잡도 O(1)class Solution { public boolean isPalindrome(int x) { if (x reversed) { ..

2024. 8. 27. 22:00