- 3. Longest Substring Without Repeating Characters sliding window 문제문자열에서 반복이 없는 가장 긴 부분 문자열을 찾는 문제. abcabcbb -> abcabcdab -> abcdabcdb -> abcd 오른쪽으로 진행하면서 문자를 하나씩 확인한다.만약 이번에 읽은 문자가 앞에 나왔던 문자와 중복된다면(set에 들어있다면), 현재 들고있는 부분문자열에서 중복된 문자와 그 앞의 모든 문자를 버려야 한다. ex> abcd be 일 경우, b를 두번 만날 경우, 부분문자열에서 b와 그 앞의 문자(a)까지 모두 버려야 한다.이를 위해서는 현재 윈도우 안에 어떤 문자가 있는지 들고있는 set이나 map이 필요하다. 그 앞의 문자를 모두 버려야 하므로, j를 0에서 시작하면서 하나씩 왼쪽으로 탐색하지 않고, size부터 시작해서 오른쪽으로 탐색하게끔 .. 2026.07.18
- 1. Two sum 전체탐색으로 풀면 쉽지만 시간복잡도가 높기 때문에 전체탐색 말고 다른 방법을 써야한다. 1. 최초 풀이(전체탐색) : 시간복잡도 O(n^2)모든 값을 다 순회한다. 단, 순서는 상관없으므로, 순열이 아닌 조합의 경우의 수만큼 탐색한다. public static int[] twoSum(int[] nums, int target) { for (int i = 0; i Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?2. 정렬 + 슬라이딩 윈도우를 활용한 풀이 : 시간복잡도 O(n log n)정렬을 하게되면 기존의 idx값을 갖고있어야 하기 때문에, Node (값, idx) 라는 클래스를 만들고 .. 2026.07.17
- 54. spiral matrix (medium) BFS를 풀때 사방탐색을 했던 경험이 있다면 쉽게 풀 수 있는 문제.너무 오랜만에 풀어서 dx, dy 방향이 헷갈렸다.. ;; 세로가 M, 가로가 N (1)ㅡㅡㅡㅡㅡ> (4)ㅜㅣㅣ (2)ㅣㅣㅣㅣㅣㅣ(3)ㅡㅡㅡㅣㅣㅗ 1. 우측으로 이동시 : y가 ++2. 아래로 이동시 : x가 ++3. 좌측으로 이동시 : y가 --4. 위쪽으로 이동시 : x가 -- N = 3, M = 4dx = {0, 1, 0, -1}dy = {1, 0, -1, 0} int[] dx = {0, 1, 0, -1}; int[] dy = {1, 0, -1, 0}; boolean[][] visit; public List spiralOrder(int[][] matrix) { List ans = new Arra.. 2026.07.15
- 15. 3sum 배열 내의 3가지 요소의 합이 0이 되는 경우를 찾는 문제.투포인터의 변형문제로, 값 1개를 정해두고, 나머지 두개의 합이 해당 값과 같은지 비교하면 된다.여기까지는 무난하게 풀 수 있으나, Notice that the solution set must not contain duplicate triplets.중복되는 세 쌍이 있으면 안 된다는 추가 조건때문에 시간이 조금 더 걸렸다. 처음에는 Set을 사용해서 중복을 확인하려 했으나, List의 경우 참조값을 저장하기 때문에 값이 전부 동일해도 다른 객체로 인식해서 실패하였다.그다음에는 Map을 사용해보려 했으나 (Map) 동일한 target에 대해 다른 합이 존재할 수 있으므로 이것도 실패하였다.while문을 사용해서, 동일한 target, start, .. 2026.07.15
- 238. Product of Array Except Self Top interview의 medium 난이도 문제 두가지 풀이로 풀어본 문제자기 자신을 제외한 모든 원소들의 곱을 구하는 문제이때 매번 곱의 결과를 구할 경우 O(n^2) 만큼 걸리기 때문에, 첫번째 풀이는매번 구할 경우 O(n^2) 만큼 걸리기 때문에, 왼쪽에서부터의 누적곱과 오른쪽에서의 누적곱 배열을 각각 만들어서정답 배열에 넣는 방식으로 풀었다.배열이 3개 필요하다.public static int[] productExceptSelf(int[] nums) { int size = nums.length; int[] left = new int[size]; int[] right = new int[size]; int[] answer = new int[siz.. 2026.07.15