매일 조금씩

이 문제는 "슬라이딩 윈도우" 알고리즘이다. 가장 긴 중복하지 않는 구간을 구하는 문제이므로, 각 알파벳을 돌되 시작점을 알고있어야한다.그리고 그 시작점은 업데이트가 될 때, 뒤로만 이동 할 수 있다. 앞으로 땡겨져선 안된다. class Solution { public int lengthOfLongestSubstring(String s) { if (s.length() check = new HashMap(); int start = 0; // 시작 인덱스 int res = 0; // 최대 길이 for (int i = 0; i

matrix 문제는 일반적인 그래프 문제와 비슷하게 출제될수도 있다.그러나 그래프 알고리즘을 요구하지 않고,matrix 그 자체로, '구현' 하듯이,matrix를 반전 시키거나 일정한 규칙에 의해 값들을 이동시켜야하는 경우도 있다. 따라서 matrix 관련 문제가 나오면 그래프(dfs, bfs) 알고리즘으로 풀 수 있는 문제인지를 먼저 파악한 후, 그게 아니라면 문제에서 요구하는 matrix 특징을 파악하고 접근하는 것이 중요하다.

DFS를 다시 한번 제대로 복습할 수 있었던 문제다.문제의 핵심은 다음과 같다.주어진 목표 단어의 첫 알파벳과 일치하는 알파벳 칸을 발견하면 dfs 시작한번 사용된 알파벳 칸은 재사용 안됨. Ex) "abca" 일 때, 처음 'a'때 방문한 칸을 마지막 'a' 때 재방문 할 수 없음.따라서, 방문 체크 필요.방문 체크는 해당 dfs 뎁스에서만 유효함. (다른 칸에서 dfs로 탐색이 시작되면 모든 칸은 방문되지 않은 상태여야 함)따라서, 백트래킹 처리 필요 [방문 체크]처음엔 방문 체크를 Set 객체를 사용해서 했는데 시간이 좀 오래걸려서주어진 그래프 객체 board[row][col]를 업데이트하며 체크했다.그랬더니 확연히 빨라졌다.시간복잡도는 O(1)로 같겠지만,아무래도 Set은 추가적인 메모리를 요구하..

주어진 matrix를 보고, 특징 파악을 먼저 해야한다.처음 파악한 특징은 문제에 언급된 대로 90도 회전한 형태가 된다는건데..이를 그대로 코드로 짜기란 복잡하고 어렵다.따라서 '회전' 보다는 '스왑', '대칭이동' 과 같은 동작으로 특징을 파악해야한다. 그럼 칸들을 가운데 가로선을 기준으로 대칭이동 시킨 다음,(0,0) -> (n,n)으로 향하는 대각선을 기준으로 한번더 대칭이동 시킨 형태라는 것을 알 수 있다. 다음은 그 방식으로 풀어낸 코드이다. class Solution { public void rotate(int[][] matrix) { int edgeLength = matrix.length; int top = 0; int bottom = edg..

칸을 이동하는 방향이 (0,0)에서 시작해서오른쪽 -> 아래쪽 -> 왼쪽 -> 위쪽 -> (반복)이라는 특징이 있다.그래서 방향 벡터를 순서에 맞게 만들어서 구현했다. class Solution { public List spiralOrder(int[][] matrix) { List res = new ArrayList(); int m = matrix.length; int n = matrix[0].length; int row = 0; int col = 0; int[] dr = {0,1,0,-1}; int[] dc = {1,0,-1,0}; int arrow = 0; int c..

위 문제를 Set을 사용하여 공간 복잡도 O(m+n)으로 풀고,별도 객체 생성 없이 O(1)로도 풀어보았다. O(1)로 풀기 위해선 이 문제의 특징을 잘 알아야한다.0인 곳의 모든 행과 열을 0으로 바꾸는 문제이기 때문에,첫번째 행, 첫번째 열만 돌면서 해당하는 행과 열에 0이 있는지 체크하고 0으로 바꿔두면 된다. 시간 복잡도는 두가지 방법 모두 O(m x n) 이다.1. 공간 복잡도 O(m+n)class Solution { public void setZeroes(int[][] matrix) { Set zRow = new HashSet(); Set zCol = new HashSet(); for(int row = 0; row   2. 공간복잡도 O..