매일 조금씩

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