본문 바로가기

전체 글

 (119)
[해커랭크] Is This a Binary Search Tree? 문제링크: www.hackerrank.com/challenges/is-binary-search-tree/problem Is This a Binary Search Tree? | HackerRank Given the root of a binary tree, you have to tell if it's a binary search tree. www.hackerrank.com 이진탐색 트리는 왼쪽 서브트리의 모든 값이 노드의 값보다 작고 오른쪽 서브트리의 모든 값은 노드보다 크다 그래서 왼쪽,오른쪽 서브트리의 노드들을 리스트에 담아서 노드의 데이터와 비교하는 방식으로 했다. 해당 내용을 구현하기 위해 어떤 노드의 left와 right를 재귀호출을 통해서 리스트에 담았다. public static boolean ..
[백준] 1450 냅색문제 문제링크: www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 냅색문제랑 상관 없는 문제다. 속았다. 풀이방법을 모르겠어서 문제 분류를 보니 투 포인터였다. 투포인터인 것을 알고도 어떻게 투 포인터로 풀리는지 몰랐다. 다른 사람풀이를 참고해보니 집합을 절반으로 나누는 풀이가 있었다. 한참을 보고서야 이해했다. import java.util.*; import java.io.*; public class Main { public static int n,c; pu..
[해커랭크] Cycle Detection [JAVA] 문제링크: www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem Cycle Detection | HackerRank Given a pointer to the head of a linked list, determine whether the linked list loops back onto itself www.hackerrank.com 처음에 문제를 보고 입력값 범위가 안주어져서 어떻게 풀어야하나 싶었다. 적당한 값으로 갱신하면서 탐색중에 갱신된 그 값을 발견할 경우 싸이클이 있다고 판단해봤는데 통과됐다. 잘못됐다고 생각하고 다른 사람의 풀이를 참고했더니 창의적인 아이디어가 있었다. *잘못된 풀이 // Compl..
[해커랭크] Sparse Arrays [JAVA] 문제링크: www.hackerrank.com/challenges/sparse-arrays/problem Sparse Arrays | HackerRank Determine the number of times a string has previously appeared. www.hackerrank.com 자료구조 학습을 하려는데 자바는 해시관련 함수를 어떻게 쓰는지 파악할 겸 문제를 골랐다. import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution..
[해커랭크] Reverse a doubly linked list [JAVA] 문제링크: www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem Reverse a doubly linked list | HackerRank Given the head node of a doubly linked list, reverse it. www.hackerrank.com 오랜만에 자료구조를 생각하려니까 머리가 아팠다. 해커랭크에 좋은 자료구조 연습 문제들이 있어서 더 풀어보려 한다. 처음에 head에는 쓰레기 데이터가 있고 next부터 출력하는거라 가정하고 문제를 풀었더니 당연히 틀렸다. 출력을 해보니 모든 노드에는 데이터가 있었다. 풀이법을 말로 설명하는 것보다 코드를 보는것이 깔끔하겠다. // Complete the reverse ..
[해커랭크] Roads and Libraries [JAVA] 문제링크: www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 모든 노드들을 잇는 최소한의 간선 개수는 노드의 갯수 -1이다. 그래서 도로를 고쳐서 도서관을 공유하는 비용을 최소한 하려면 도로를 N-1개만 고치면 된다. (MST 구성) 고장난 도로를 탐색해서 노드가 몇개인지 파악하기 위해 dfs 탐색을 했다. 또, N-1개의 도로의 수리비용보다 모든 노드에 도서관을 설치하는 비용이 적..
[백준] 19238 스타트택시[JAVA] 문제링크: www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제를 보자마자 이전에 풀었던 삼성 유형 중 아기상어 문제가 떠올랐다. 일부 조건만 제외하면 똑같이 풀면 된다. 현재 위치에서, 가진 연료로 가장 가까운 손님(여럿 있다면 위쪽일수록, 왼쪽일수록)을 태울 수 있으면 태우고 이동한다. 이동하면 손님을 목적지로 이동한 걸의 2배만큼 연료가 충전되며, 이 과정을 모든 손님을 목적지까지 이동할 수 있으면 남은 연료를, ..
[백준] 9370 미확인도착지[JAVA] 문제링크: www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 처음 아이디어는 start(시작점)에서 양옆 다리 g,h로 가는 최단거리 + 다리길이 + 후보지로 가는 거리가 start(시작점)에서 후보지로 가는 최단거리보다 작거나 같은 경우인 후보지만 채택하는 방식이었다. 이렇게 할 경우 다익스트라를 최소 2번 사용하는 것 같은데, 오랫동안 틀리거나 런타임 에러의 원인을 찾지 못해서 다른 사람의 아이디어를 참고했다. 다리길이를 2배보다 1 작은 홀수로, 나..

티스토리툴바