본문 바로가기

LeetCode

 (40)
[Easy] 226. Invert Binary Tree / 구글 코딩 테스트 기출 문제 이번 문제는 구글 코딩 테스트로 굉장히 유명한 문제이다. 이 문제가 유명해진 데에는 한 가지 이유가 있다. 맥(Mac)을 사용하는 개발자라면 누구나 사용해 봤을 법한 Homebrew (MacOS 패키지 관리자)를 개발한 사람으로 유명한 Max Howell은 2015년 구글과 입사 면접을 보는데, 면접 문제에서 binary tree를 invert하는 문제가 나왔지만 결국 풀지 못해 면접에서 떨어지게 된다. 그 후에 Max Howell은 자신의 트위터에 "구글: 90%의 구글 엔지니어들은 네가 개발한 소프트웨어를 사용하지만, 너는 binary tree invert하는 것도 화이트보드에 풀지 못하기 때문에 꺼져라" 와 같은 글을 올리며 자신은 굉장히 많은 사람들이 사용하는 소프트웨어를 개발했지만 고작 코딩 테..
[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] 973. K Closest Points to Origin (Facebook / Meta) #문제 설명 Leetcode 973번 문제는 x, y축 위의 좌표들이 배열로 주어지고, 정수 k가 주어진다. 이 문제에서는 (0,0) 에 가장 가까운 좌표 k개를 포함한 array를 return하는 문제이다. #문제 풀이 #풀이 1 class Solution{ public int[][] kClosest(int[][] points, int K) { Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]); return Arrays.copyOfRange(points, 0, K); } } 모든 점을 원점까지의 거리에 따라 정렬한 다음 가장 가까운 상위 k개의 점을 얻는 풀이 이다. Time comp..
[Easy] 495. Teemo Attacking #문제 설명 Leetcode 495번은 리그 오브 레전드 캐릭터인 티모를 알고 있으면 이해하기 쉽다. 티모의 e 스킬은 티모가 상대 챔피언에게 평타를 때리면 평타를 때리면, 4초간 독 데미지를 상대에게 입힌다. 이 문제에서는 티모가 e스킬은 찍은 상태에서, 상대에게 평타를 치는 시간을 담은 배열과, 독 데미지의 지속시간이 주어진다 (실제 게임에서는 4초로 고정이지만). 또 한 가지 알아야 할것은 티모가 이미 독 데미지를 입은 상태의 상대에게 평타를 입힌다면, 독 데미지의 지속 시간은 리셋되고 상대는 다시 4초간 독데미지를 입어야한다. 예를 들어 티모가 2분40초에 평타를 입히고, 다시 2분 42초에 평타를 때리면 상대의 독데미지는 2분 46초에 끝날것이다. 이 문제는 주어진 배열과 독 데미지 지속 시간을..
[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] 703. Kth Largest Element in a Stream (아마존 코딩 테스트 기출 문제) #문제 설명 Leetcode 703번문제는 int k 와 정수 array가 주어진다. 또한 이 array는 stream이기때문에 계속 정수들을 array에 추가 시킨다. 이 문제에서는 주어진 array에 여러개의 정수를 add하고, add가 끝난뒤 array에서 k번째로 큰 정수값을 반환시켜주면된다. #문제 풀이 class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { minHeap = new PriorityQueue(); this.k = k; for(int i = 0; i < nums.length;i++){ minHeap.add(nums[i]); if(minHeap.size(..
[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[][..

티스토리툴바