kwang2134 님의 블로그

[Programmers] 전화번호 목록 - LV 2접근완전 탐색해시Trie풀이전화번호가 들어있는 배열이 주어지고 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 없다면 true를 반환하는 문제이다. [119, 119552]와 같은 번호가 주어졌을 때 119가 다른 번호인 119552의 접두어이기 때문에 false를 반환해야 한다.완전 탐색 단순하게 하나씩 다 비교해 보는 방법이다. 전화번호를 길이순으로 정렬해 준 뒤 짧은 번호들을 접두어로 보고 긴 번호들에 하나씩 전부 비교해 보는 방법이다.  public boolean solution(String[] phone_book) { Arrays.sort(phone_book, Comparator.comparingInt(String::..

[Programmers] 무인도 여행 - LV 2접근dfs풀이무인도 여행이라는 문제로 좌표가 주어지고 X 가 적혀있는 곳은 바다 숫자가 적혀있는 곳은 무인도로 숫자는 해당 땅에서 숫자 일수만큼 버틸 수 있는 식량이 존재한다는 뜻이다. 연결된 섬들에서 머무를 수 있는 일수를 모두 구한 뒤 배열에 담아 오름차순으로 반환하는 문제이다.  유사한 문제를 많이 풀었기 때문에 제일 먼저 생각나는 bfs, dfs로 풀었다. 이 문제는 모든 위치를 탐색하기만 하면 되기 때문에 dfs, bfs 중 아무거나 사용해도 큰 상관이 없어 재귀를 이용한 dfs로 풀었다. LeetCode에서 문제를 풀다 보니 재귀로 해결한 코드와 큐나 스택을 직접 사용한 코드의 속도 차이를 보니 자연스럽게 재귀로 해결이 가능하다면 시도해 보는 것..

[Programmers] 호텔 대실 - LV 2접근그리디풀이오랜만의 프로그래머스 문제이다. 호텔 대실이라는 문제로 대실에 대한 시작 시간과 종료 시간이 주어지고 모든 예약 처리를 위해 최소 몇 개의 방이 필요한 지 구하는 문제이다. 특이 사항으로 대실이 종료된 후 청소 시간이 존재하기 때문에 종료 후 10분간은 청소를 위해 대실이 제한된다.  public int solution(String[][] book_time) { Arrays.sort(book_time, (a,b) -> a[0].compareTo(b[0])); PriorityQueue endTimeQueue = new PriorityQueue(); int result = 1;우선 예약 관리를..

[NeetCode-LeetCode] Set Matrix Zeroes - Medium접근수학(?)풀이행렬에 0이 있는 위치의 행과 열 모든 숫자를 0으로 만드는 문제이다. 0이 있는 위치가 [3,4]이라면 3행에 있는 모든 숫자와 4열에 있는 모든 숫자를 0으로 만드는 것이다. 이 문제에 주어진 추가 질문으로는 O(mn)의 공간 복잡도로 푸는 건 대체적으로 좋지 않은 방법이고 개선하여 O(m+n)의 공간 복잡도로 풀 순 있지만 최선의 방법은 아니다 그렇다면 상수 공간 복잡도로 해결을 해보라는 말인데 상수 공간 복잡도로 해결하려면 추가적인 배열을 사용하지 않아야 한다는 소리다. public void setZeroes(int[][] matrix) { int m = matrix.length;..

[NeetCode-LeetCode] Rotate Image - Medium접근행렬 회전풀이n x n 배열의 원소들을 90도로 회전한 결과를 반환하는 문제이다. 원소를 그대로 오른쪽 90도로 돌린 상태로 만들면 되는데 추가 적인 공간을 할당하지 않고 주어진 배열을 조작해서 변경해야 한다. 수학과 공간 지각 문제다 보니 조금 만나기 싫은 유형의 문제였다. public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i 90도로 회전하는 방법은 행렬을 전치한 뒤에 각 행을 뒤집게 되면 90도로 전환이 된다고 한다. 위는 행렬을 전치하는 과정으로 행과 열의 위치를 바꾸는 것이다.  for (int i = 0..

[NeetCode-LeetCode] Non-overlapping Intervals - Medium접근그리디풀이구간이 주어지고 겹치는 구간을 제거해 총 제거된 구간이 몇 개인지 구하는 문제이다. 아래와 같은 구간이 주어질 때intervals = [[1,2],[2,3],[3,4],[1,3]][1,2]와 [2,3]은 2라는 구간이 접하긴 하지만 접하는 경계면은 겹치지 않는 것으로 넘어가게 되나 [1,2]와 [2,3]을 합친 구간인 [1,3]이 뒤에 존재하기 때문에 두 구간 중 겹치는 한 구간을 제거해야 하는데 문제에서 요구하는 것은 겹치는 구간을 제거하는 최소의 비용을 원하기 때문에 [1,2], [2,3]이 제거되는 것이 아닌 [1,3]이 제거되는 것이다. public int eraseOverlapInt..

[NeetCode-LeetCode] Jump Game - Medium접근dfsgreedy풀이배열이 주어지고 각 인덱스에는 점프할 수 있는 최댓값이 들어있다. 첫 인덱스에서 시작해 마지막 인덱스에 도달할 수 있는지 검사하는 문제이다. 인덱스의 값이 3이라면 1,2,3 세 가지 경우로 점프를 할 수 있다. 가장 간단하게 생각하면 dfs를 사용해 모든 경우를 수행해 도달이 가능한지 보면 된다. 이 문제는 그리디를 사용해 해결하는 문제로 dfs로 모든 경우를 탐색했을 때와 그리디를 사용했을 때의 성능 차이를 보려고 한다. public boolean canJump(int[] nums) { boolean[] visited = new boolean[nums.length]; ret..

[NeetCode-LeetCode] Longest Common Subsequence - Medium접근dp풀이가장 긴 공통 부분 수열의 길이를 구하는 문제이다. 바로 전에 풀었던 문제와 유사한 형태로 이번에는 숫자가 들어있는 배열이 아닌 문자열을 비교하여 구해야 한다. 예시를 보면 text1 = "abcde", text2 = "ace"라는 입력이 주어졌을 때 가장 긴 공통 부분 수열은 "ace"로 길이인 3이 정답이 된다. text1에서 순서대로 부분 수열을 만들었을 때 "ace"를 만들 수 있기 때문이다. 2차원 dp 카테고리의 문제인 만큼 dp를 사용해 풀면 된다. public int longestCommonSubsequence(String text1, String text2) { ..

[NeetCode-LeetCode] Longest Increasing Subsequence - Medium접근이진 탐색풀이가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 그냥 증가하는 수열이 아니라 strictly increasing subsequence로 엄격한(?) 증가하는 부분 수열이다. 문제만 보고 이해가 잘 안 갔었는데nums = [0,1,0,3,2,3]위와 같은 배열이 있을 때 일반적인 증가하는 수열은 [0,1], [0,3], [2,3] 이렇게 최대 길이가 2인 부분 수열만 존재한다. 그러나 엄격하게 증가하게 증가하는 부분 수열의 경우 원소들을 증가하는 형태에 맞춰 삽입하여 수열을 만든다고 생각하면 된다. 예를 들어 [0,1]이라는 부분 수열이 만들어지고 그다음 0이 왔을 때 해당 원소..

기능 수행 테스트테스트 데이터를 넣어두고 구현한 기능들이 잘 작동하는지 테스트한 영상입니다. 탭 전환 & 페이징게시글 탭 전환과 페이징 기능 테스트입니다.탭 전환 & 페이징검색 검색 기능에 대한 테스트입니다.검색로그인로그인 기능에 대한 테스트입니다.로그인회원가입 & 마이페이지회원가입 기능과 마이페이지 기능에 대한 테스트입니다. 회원가입 & 마이페이지게시글 작성 & 수정 & 삭제게시글 작성, 수정, 삭제에 관한 테스트입니다.게시글 작성 & 수정 & 삭제게시글 추천게시글 추천에 대한 테스트입니다. 게시글 추천관리자관리자 페이지에 대한 테스트입니다.관리자