매일 조금씩

하.. 이문제.. 방법을 알겠는데슬라이딩 윈도우 알고리즘을 쓰면 된다. 간단히 시작점을 기억하는 방식.흔히 조건을 만족하는 구간의 최대 길이를 구하는 문제에 활용되기 때문에, 이문제에서도 사용하면 된다.윈도우 구간을 넓히면서 조건을 만족하지 않으면 start를 차차 뒤로 민다.근데 이문제에서 이해가 안되는 부분이 있다. start를 뒤로 밀 때, 난 윈도우 구간이 조건을 만족할 때까지 밀었다.그래서 갯수가 가장 많은 알파벳의 갯수를 그때그때 업데이트 해줬다. 근데.. 그렇지 않아도 된다는 챗쥐피티의 답이 있었다.윈도우 구간을 반드시 조건을 만족하도록 만들지 않아도 된다? 왜그럴까.. 시간 복잡도가 생각보다 큰 차이가 없어서 일단 제출은 했지만 이유를 정확이 이해하지 못했다. import java.util..

이 문제는 "슬라이딩 윈도우" 알고리즘이다. 가장 긴 중복하지 않는 구간을 구하는 문제이므로, 각 알파벳을 돌되 시작점을 알고있어야한다.그리고 그 시작점은 업데이트가 될 때, 뒤로만 이동 할 수 있다. 앞으로 땡겨져선 안된다. 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..