말하는 컴공감자의 텃밭

오늘은 가볍게 풀자면서 골랐던 문제다.. 난이도가 뭐라고 기세등등하게 키보드를 두둘겼다가 한참 혼났다. 쉬운것도 제대로하자 실수하지말자.. 쫌 서브태스크로 문제 배점을 공개한 문제인데... 아직 정렬개념이 확실하게 안잡힌게 분명하다... 보단 사사로운 문제에 시간을 썼다. 순위 이놈 때문에 1시간반을 넘게 썼다. 정리해보자.. 문제 조건이 주루루 있다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 음~ 이해하기 쉽다. 금메달이 가치가 높아(1등만 기억하는 세상) 금메달이 많다면 국가 등수가 올라간다. 단. 동일하다면 1번 국가 2위 -> 3,4번 국가 4위 -> 3번 국가 가 된다. 금메달 은메달 동메달 순으로 Co..

먼저 문제를 잘 읽어보자. 트리의 그래프에 가중치가 있는채로 들어가 있고, 양쪽으로 쫙 당길때 -> 서로 끝과 끝일때 란 얘기. 결국 트리의 리프노드를 찾아서 거리계산하면 되는구나! 라는 접근법에 도달했다. ㅋㅋ 아 시작은 거창하죠 HTML 삽입 미리보기할 수 없는 소스 먼저 코드를 보게되면 bfs 식으로 que를 활용해서 자식 노드가 없다면 리프노드이다! 라는 함수를 짜주었다. 이후 리프노드들을 leaf 리스트에 모아서 dfs를 굴려줬는데,,, 노드가 10,000개 까지라 메모리가 석나가버렸다... (돌아와 줘) 이차원 배열을 사용했기에 뭐 1억.. 써버렸으니 머 어떻게 가지치기를 할까 하다가 인접 리스트로 다시 구현하고, 로직을 수정하고자 했다. 어짜피 우린 가중치가 큰 경로를 찾아야 하므로 루트에서..

뭐 간단하다 트리형식으로 연결되어 있고, 연결된 거리가 주어진다. 이후 N과 M의 거리는 몇이야? 묻는 문제이다. 가볍게 BFS로 풀어줬다. HTML 삽입 미리보기할 수 없는 소스 Node 클래스를 짜서 넣어도 되고, 큐에 배열보단 그냥 따로 dist 변수를 만들어서 해결해도 된다.

입력들이 주루루 주어지고 1이 루트로 기준이 된다. 입력예제 처럼 주어지게 되면. 그림과 같이 입력이 들어온다. 1이 root 가 된다면 이처럼 표기할 수 있겠다. 따라서 각 자리의 부모를 나타내면 2 : 4 3 : 6 4 : 1 5 : 3 6 : 1 7 : 4 이다. Level 별로 나타내는게 문제의 핵심이기때문에 Map에 레벨과 리스트를 넣어 tree를 구성해주었다. static Map tree = new HashMap(); 이후 선언된 tree에 입력을 처리할때 computeIfAbsent를 활용해서 기존 값이 있다면 추가, 없었다면 새로 리스트를 넣어주었다. tree.computeIfAbsent(a, k -> new ArrayList()).add(b); dfs 재귀를 통해서 모든 트리를 찾아 주었..

이진트리 입력이 주어지고, 해당 트리를 전위 중위 후위한 결과를 출력하는 문제이다. 입력에 . 은 자식이 없다는 의미로 받아주면 된다. 트리를 순회할때는 큰 삼각형을 작은 삼각형으로 쪼개서 순회한다고 생각했다. 따라서 재귀함수로 작성하는게 문제의 포인트이다. Node 클래스로 왼쪽과 오른쪽 자식을 관리해 주었고, '.' 입력이 주어질때는 자식에 Null을 주는 방식으로 처리를 했다. 전위 순회의 경우 루트 먼저, 이후 왼 > 오 자식을 순회하고. 중위의 경우 왼쪽 아래까지 쭉 내려갔다가 더이상 자식이 없으면 루트, 오른쪽 자식을 찾는 방식이다. 마지막으로 후위는 왼쪽 아래 탐색 후 오른쪽 아래 탐색. 이후 없다면 부모 노트 체크. 이다. 결론적으로 전위는 출력하고 왼쪽 오른쪽 재귀함수를 호출. 중위는 왼..

구간중에 가장 사람이 많이 겹치는곳을 찾고, 그 구간이 여러 장소에서 겹친다면 알파뱃 순으로 정렬. 정해진 장소에서 여러 시간대가 사람이 많다면 가장 빠른 시간대로 출력한다. >> 이 규칙들을 제대로 안읽고 모든 구간에서 가장 긴 구간 찾고,,, 세그먼트 나누고 2시간은 걸린거 같다. 막상 다 작성하니까 가장 빠른이라 훨씬 쉽게 해결됐다... 해시 + 정렬 쓖쓖.. 해시맵에 배열을 넣어서 구간 범위를 증가시켜 주었고, MAX 값을 가진 장소를 리스트에 넣어서 구간을 체크해주었다. HTML 삽입 미리보기할 수 없는 소스

문제가 간단하다. 문제를 잘 읽으면 N 을 반 쪼개서 1차이로 나누는 로직이 존재합니다이 홀수면 N-1/2 랑 N-1/2 로 나누고, 짝수면 반반 가져가게 되는데 이런 과정을 모두 Set에 담아줍니다. 그리고~ 여기에 M이 포함되면 Yes 해주면 꿑 꿑 꿑 만약 130이 N 이라면 요로코롬.. 주루루 저장이 된다. 규칙이 존재하는데 홀수가 나타나는 순간 두 갈래로 갈라진다. 짝수라면 반반 이고 중복 저장 안하니까 1개씩 저장된다. 코드로 보잡 HTML 삽입 미리보기할 수 없는 소스

먼저 쿼리 개수가 주어진다. 이후로 1 또는 2의 쿼리 값이 주어지고, 고릴라의 이름. 정보의 개수 정보의 가치 가 주어진다. 문제를 한 20분 읽은거 같다. Cpp 5 10 4 2 8 2 라길래 5도 정보에 포함인줄 .... 이렇게 되겠다. 여기서 가장 큰 값만 가져오기 때문에 정렬이 필요한데 우선순위 큐를 활용했다. 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것. 힙(Heap)으로 정렬하기에 시간 복잡도는 추출 삽입 모두 O(logn) 이다. 그리고 Map 을 편하게 쓰기위해 처음보는 메서드를 써봤는데 간단하게 key에 valuye가 존재하면 가져와서 사용하고, 없으면 새로 만들어주는 메서드다. computeIfAbsent(K key, Fu..

공유기를 설치하는 개수는 정해져 있고, 집 사이의 거리를 최대로 하고 싶은 도현이다. 처음에는 뭘.. 탐색해야 하나 어지러웠다 처음과 끝쪽에 배치하는게 가장 멀지 않나..? 이런 생각만 갖고 있다가. 기준을 1번으로 잡고, 이후부터 거리를 늘려나가며 주어진 개수를 채운다면 거리를 더 벌리자! 못 채웠다면 이전 거리가 최대 거리일 것이다. HTML 삽입 미리보기할 수 없는 소스 이분탐색... 이분탐색....이분탐색...........

룰은 뭐 동일하다, 뱀을 타면 해당 숫자로 내려가고, 사다리면 해당 위치로 올라간다. 위치에 사다리나 뱀으로 이동하는 위치 값을 넣어두고, 해당하는 위치로 간다면 이동해주자. BFS를 통해 탐색하고, 큐에 배열을 넣어 주사위 횟수를 저장해주었다. 이후 최소값을 출력해주면 끝. HTML 삽입 미리보기할 수 없는 소스 한방에 풀려서 기분이 좋았던.. 홍홍홍