[Medium] 54. Spiral Matrix (Microsoft)
#문제 설명 Leetcode 54번 문제는 m x n matrix 가 주어진다. matrix의 값은 1부터 n까지의 정수로 채워진다. 정수의 순서는 matrix에 나션형 모양으로 나열된다. 우리는 이 matrix를 나선형 (matrix[0][0] 에서 시작해서 오른쪽끝, 맨 아래, 맨 왼쪽, 위로를 matrix의 전체가 커버 될때까지 반복한다). 이 과정에서 각 index를 지날때마다, index에 있는 정수 값들을 list에 add해주면 된다, 그리고 그 list를 return해주면 된다. #문제 풀이 이 문제는 총 네가지 (오른쪽, 아래, 왼쪽, 위) traverse하는 경우가있기때문에, 그 index들을 tracking하는 variable를 만들고, 그 varible들 (matrix index)을 ..
[Medium] 378. Kth Smallest Element in a Sorted Matrix (아마존)
#문제 설명 378번 문제는 정수 k와 n x n 정사각형 matrix가 주어지고, matrix의 각 칸에는 정수들이 담겨있다. 이 문제에서는 matrix안에서 정수 k번째로 작은 정수들을 전부 return해주면 된다. 예를 들어 [[1,5,9], [10,11,13] , [12,13,15]] 라는 2d 매트릭스가 주어지고 정수 k = 4가 주어지면, matrix안의 4번째로 작은 10을 return해주면 된다. #문제 풀이 class Solution { public int kthSmallest(int[][] matrix, int k) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for(int i = 0; i < matr..
[Medium] 53. Maximum Subarray (아마존 코딩 테스트 기출 문제)
#문제 설명 Leetcode 53번 문제는 정수형 배열이 있을 때, 그 배열의 subarray 즉, 부분 배열(주어진 배열의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 문제이다. 여기서 subarray란 주어진 배열에서 끊기지 않고 인접한 원소들의 집합이다. 예를 들어 [1,2,3,4,5]라는 배열에서 subarray는 [1,2], [2,3,4] 등등이 될 수 있다. 하지만 [1,3,5] 같이 인접하지않는 원소들로 구성된 배열은 subarray라고 할 수없다. #문제 풀이 class Solution { public int maxSubArray(int[] nums) { int currSum = 0; int maxSum = Integer.MIN_VALUE; for(int i = 0; i ..
[Easy] 733. Flood Fill (아마존 / 구글 코딩 테스트 기출 문제)
#문제 설명 Leetcode 733번문제는 2d 배열에 x와y, 즉, 시작점이 주어지고, 정수 color가 주어진다. 이 주어진 배열의 시작점에서 시작해 그 지점에서 왼쪽, 오른쪽, 위, 아래의 지점이 시작한 color와 같다면, 그 지점의 color를 주어진 새로운 color로 바꾸는 문제이다. 예를 들어 위에 사진의 2d배열에서 시작점이 가운데 즉 (1,1)이라고 가정하면, 시작점을 주어진 새로운 color 2로 바꾸고, 처음 시작점에서 위 (0,1)로가면 시작점과 같은 color 1이기 때문에 2로 바꾼다, 또 (0,1)의 왼쪽과 오른쪽모두 1이기 때문에 2로 바꾼다. 이 과정을 계속 반복하면 된다. #문제 풀이 class Solution { public int[][] floodFill(int[][..
