kwang2134 님의 블로그

[NeetCode-LeetCode] Single Number - Easy접근MapXOR풀이배열의 원소중 중복이 없는 원소를 찾는 문제이다. 배열의 원소들은 모두 2개씩 존재하나 단 한 개의 원소만 2개가 아닌 1개만 존재한다. 문제를 푸는 것 자체는 쉽기 때문에 여러 가지 방법으로 풀 수 있다.  public int singleNumber(int[] nums) { Map map = new HashMap(); for (int num : nums) { map.merge(num, 1, Integer::sum); } for (Integer i : map.keySet()) { if (map.get(i) == 1) { ..

이전 진행 상황Comment 패키지 Controller 개발Photo 패키지 Controller 개발UserPostCommentPhotoGlobalUser백엔드 통합 테스트가 개발되면서 많은 수정 사항이 생겼습니다. 기본적인 통합 테스트 환경으로 h2 데이터베이스를 메모리 모드로 MySql 모드를 사용한 채 수행하였고 추천/비추천에 사용되는 Redis의 경우 Embedded-Redis를 사용해 진행하였습니다. 그리고 현재 Thymeleaf가 개발되기 전이므로 테스트 환경에선 Thymeleaf 템플릿을 비활성화하여 렌더링 되지 않게 한 뒤 테스트 하였습니다. 변경 사항UserFormController 로그인 예외 처리 추가추가 사항UserControllerTest 추가변경 내용class UserFormCo..

[NeetCode-LeetCode] Kth Largest Element in a Stream - Easy접근힙 (우선순위 큐)풀이스트림에 있는 요소에 K번째로 큰 요소를 반환하는 문제이다. 처음 생성자를 호출하고 원소를 추가하는 add 연산만 구현하면 된다. add 연산 수행 시 요소를 추가하고 K 번째 요소가 어떤 것인지 반환하면 된다. 우선순위 큐의 문제라 적혀있던 만큼 우선순위 큐를 통해 구현하면 간단하게 풀 수 있는 문제이다.class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { this.k = k; minHeap = new P..

[NeetCode-LeetCode] Valid Sudoku - Medium접근브루트 포스풀이Grind75에 있던 문제를 다 풀고 NeetCode로 넘어왔다. NeetCode에서 겹치치 않는 안 풀었던 문제를 위주로 풀어볼 예정이다. 첫 번째 문제로 스도쿠를 검증하는 문제이다. 말 그대로 주어진 스도쿠 판이 스도쿠 규칙을 만족하고 있는지 검사하는 문제이다. 처음 문제를 봤을 때 주어진 스도쿠 판으로 스도쿠를 완성할 수 있는지를 검사하는 문제인 줄 알고 그냥도 완성하기 힘든 스도쿠를 완성할 수 있는지 검사하라니 Medium 난이도가 맞는가 싶어 요구하는 시간 복잡도를 봤더니 n의 제곱이었다. n의 제곱이라는 뜻은 주어진 스도쿠 2차원 배열을 한 번만 방문해서 완성하라는 의미인데 그게 가능한가 싶어 생각해 보..

[Grind75-LeetCode] Largest Rectangle in Histogram - Hard접근스택풀이Grind75의 마지막 문제로 히스토그램에서 가장 큰 사각형의 넓이를 구하는 문제이다. 이렇게 넓이를 구하는 유사한 문제에선 거의 슬라이딩 윈도우나 투 포인터를 사용했었지만 이번 문제는 끝 포인터들의 길이만 체크하는 것이 아니기 때문에 사용하기 어려운 방법이다.  어떻게 보면 더 간단한 방법일 수 있는데 스택을 사용해 푸는 것이다. 스택에 배열을 순회하며 값을 넣는다. 이전 스택에 들어있는 peek 값과 다음 진행에서 현재 인덱스의 값을 비교해 peek 값 보다 현재 인덱스 값이 크다면 스택에 값을 추가한 뒤 넘어가고 현재 인덱스 값이 작다면 스택에서 값을 꺼내 계산해 주면 된다. 쉽게 말해 스..

[Grind75-LeetCode] Merge k Sorted Lists - Hard 접근우선순위 큐분할 정복버킷 정렬풀이ListNode 객체를 정렬된 상태로 병합하는 문제이다. ListNode 객체는 필드로 값과 다음 ListNode의 참조 값을 가지고 있다. 이 문제를 봤을 때 주어진 노드의 순서를 알 맞게 배열해 하나의 ListNode로 만들어라는 말이겠지만 과연 채점 기준으로 객체의 참조값을 비교해 볼까?라는 생각이 들었다. 만약 참조 값을 기준으로 채점하지 않는다면 그냥 값들을 순서에 맞게 새로운 객체를 만든 뒤 반환하면 되기 때문이다. 코드가 복잡하지 않으니 한 번 해봤다. public ListNode mergeKLists(ListNode[] lists) { PriorityQu..

이전 진행 상황PostRepository 수정PostService 수정PostDTO 수정PostMapper 수정Post - Adapters 개발PhotoService 수정PhotoDTO 삭제CommentPhotoCommentComment에 대한 adapters 패키지 아래가 개발되었습니다. fetch join과 관련된 기능들이 추가되고 Service에 존재하는 로직 중 일부가 변경되었습니다. get 요청의 FormController와 Post 요청 Controller가 개발되었습니다.변경 사항CommentRepository 메서드 추가 -> fetch join 메서드 추가CommentService 메서드 추가 및 로직 수정 -> 댓글 생성, 삭제 로직 수정 및 기타 조회 메서드 추가CommentDTO 통..

[Grind75-LeetCode] Maximum Profit in Job Scheduling - Hard접근dp이진 탐색풀이Job 스케줄러를 통해 얻을 수 있는 최대 이득을 구하는 문제이다. 시작 시간이 들어있는 배열, 종료 시간이 들어있는 배열 그리고 이익 값이 들어있는 배열이 주어진다. Job은 비선점 방식으로 수행이 되며 어떤 작업이 끝나는 시간에 다른 작업을 시작할 수 있다. 각 작업의 시간과 이득을 객체로 합쳐 놓고 종료시간을 기준으로 정렬한 뒤 dp와 이진 탐색을 통해 풀면 된다. 풀었던 방법과 성능이 제일 좋았던 코드는 알고리즘 자체는 동일하고 리스트를 사용하냐 배열을 사용하냐 정도의 차이였기 때문에 성능이 제일 좋았던 배열을 사용한 코드를 바로 들고 왔다. class Job { ..

이전 진행 상황UserDTO 수정UserMapper 추가UserFormController 추가UserController 추가Spring Security 관련 클래스 추가Post 페이징 관련 메서드 추가PostPhotoPostPost의 adapters 개발로 인해 많은 것들이 수정되었습니다. 페이징 처리를 위해 존재하던 게시글 목록과 관련된 메서드의 반환 값이 Page로 변경되고 각 타입별 게시글 조회 메서드가 추가되었습니다. Querydsl을 통해 PostQueryRepositoryImpl이 추가되었습니다. 또한 Service의 로직과 Controller 추가로 인해 DTO의 구조 변경 등 많은 사항이 수정되었습니다.변경 내용게시글 목록 조회 관련 메서드 페이징 처리 -> 반환 타입 List 에서 Pag..

[Grind75-LeetCode] Basic Calculator - Hard 접근스택풀이기본적인 계산기를 구현하는 문제로 문자열로 입력받은 수식을 계산한 결과를 반환하면 되는 문제이다. 수식에는 괄호가 포함될 수 있고 - 연산자는 단항 연산자로 사용이 될 수 있다. 즉 +의 경우 +1과 같이 앞에 다른 값 없이 단항 연산자로 사용될 수 없지만 -의 경우 -1과 같이 단항 연산자로 수식에서 사용될 수 있다.  무엇보다 이 문제에서 연산자는 +, - 두 가지만 존재한다. 곱하기 나누기 연산이 존재하지 않다 보니 괄호에 대한 처리만 스택을 통해 천천히 해주면 어렵지 않게 해결이 가능하다. public int calculate(String s) { Stack stack = new Stack()..