본문 바로가기

algorithm60

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. 7. 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. 7. 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. 7. 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. 7. 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. 7. 15.

티스토리툴바