본문 바로가기

자바11

[자바] Leetcode 234 - Palindrome Linked List 최적화된 방법은 아니다. 일단 Linked List를 끝까지 타면서 ArrayList list에 담아주고, 그 list의 양 끝값들을 하나씩 비교해가면서 어긋나는 게 있으면 바로 answer = false를 넣고 나와버린다. Linked List를 순회하는데 걸리는 시간 O(n) + ArrayList의 절반을 순회하는데 걸리는 시간 O(n/2)해서 결국 대략 O(n)이기는 한데, 성능이 하위 70%에 속한다 ㅎ 시간이 빠른 다른 풀이를 보면 두 개의 변수 (fast, slow)를 써서 뭔가를 하는 것 같은데, 이해는 나중에 해야겠다! 처음 제출했을 때, [-129, -129] 케이스에서 Wrong Answer가 나왔다. 일단 잘못 생각했던 점은, 자바를 너무 겉핥기 식으로 했어서 그런지 Integer도 .. 2021. 3. 1.

[자바] Leetcode 100 - Same Tree 어쩌다 면접이 잡혀서 발등에 불떨어진 느낌으로 부랴부랴 문제 푸는중 ㅎ 친구한테 리트코드 추천 받아서 Difficulty Easy단계부터 풀고 있는데, 어렵지는 않다. 하지만 최적화는 정말 끝이 없고, 똑똑한 사람들은 이 세상에 많다는 걸 계속해서 깨닫게 된다. TreeNode 2개를 파라미터로 던져주면 그 2개의 TreeNode들이 동일한지 아니지를 판별하는 메소드를 짜는 문제다. Class TreeNode는 아래처럼 구현되어 있다는 가정하에 메소드 로직만 채우면 된다. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int va.. 2021. 2. 28.

[자바] 백준 2042 - 구간 합 구하기 세그먼트 트리 문제다. 세그먼트 트리는 한 번도 그 어디에서도 들어본 적도 없었는데, 아래 글 읽으니까 어느 정도 이해가 됐다. www.crocus.co.kr/648 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 요청하는 쿼리에 대해 방식이 달라질 수 있으나, 모든 쿼리를 다룰 수 없기에 구간 합에 대한 세그먼트 트리를 정리해 두었습니다. 내용이 길지만 그만큼 자세히 설 www.crocus.co.kr # 세그먼트 트리 - 시간 복잡도 : O(logN) - tree 배열과 array 배열은 다른 데이터다. array 배열은 1부터 N까지의 값이 들어가 있는 배열이라면, tree 배열은 구간합들이 들어가있는 배열이다. 트리의 노드를 각 배열에 대치시킨 것이라고 생각하면 된다.. 2021. 1. 6.

[자바] 백준 4386 - 별자리 만들기 각 별(=노드)의 위치를 좌표평면 상에 주고, 별들 간 거리는 알아서 계산한 다음에, 최소 스패닝 트리를 구하는 문제. n이 최대 100이기 때문에 거리를 구하는 데에는 100x99의 연산이 필요하니까 큰 문제는 없을 것 같은데 좀 귀찮네 ㅎㅎ 게다가 실수값이라 더 귀찮다. 1. 배열을 만들어서 각 별들의 x,y 좌표 담아두기 2. 이중 for문 이용해서 각 별들간 거리 구하고 그 값들은 PriorityQueue에 담아두기 3. PriorityQueue를 while문으로 탐색해서 최소 스패닝 트리값 구하기 DefimalFormat이라는 클래스를 써봤다. 그리고 다른 통과자들 코드를 보니까 PQ 이용하는 것보다는 ArrayList가 더 빠른가보다. /* 2021.01.05(화) */ import java... 2021. 1. 5.

이전 1 2 3 다음

티스토리툴바