pinevienna blog

[백준/BOJ/JAVA] 10815 숫자 카드 상근이가 가지고 있는 N개의 카드 중에서 입력받은 M개의 정수와 일치하는 카드가 있는지 판별하여 출력하는 문제 어려울 거 없는 이분탐색 문제다. 하지만 시간초과를 막기 위해 모든 수단(이 pinevienna.tistory.com 10815의 응용문제! left, right, middle 값을 알맞게 조정할 수 없기 때문에 이분 탐색으로는 풀 수 없다. 카운팅 하는 방식으로 해결해야 한다!!! 카드의 개수에 맞게 배열을 초기화하는 게 아닌, arrN[20000001] 로 선언한다. 그리고 [입력된 카드값 + 10000000] 을 인덱스로 가지는 배열방에 +1을 해준다. 비교할 카드값이 입력될 때 arrN[비교할 카드값 + 10000000] 의 값을 String..

도현이의 집 N개에 공유기 C개를 설치할 때, 가장 인접한 두 공유기의 최대 거리를 구하는 문제. (단, 한 집에 하나의 공유기만을 설치할 수 있음) min은 공유기를 설치할 수 있는 가장 짧은 거리인 1, max는 공유기를 설치할 수 있는 가장 긴 거리인 (마지막 집 좌표 - 첫 집 좌표) 이다. middle은 당연히 그 중간값이 된다. 일단 첫 집에 공유기를 하나 설치하고, 그 다음 집들과의 거리를 구해서 middle과 비교한다. middle보다 크거나 같을 경우 해당 집에 공유기를 설치하고 그 집이 새로운 기준이 된다. 이걸 반복하며 공유기를 되는대로 설치한 뒤 설치된 공유기 개수와 설치할 공유기 개수 C를 비교하여 min, max 값을 조정한다. 코드를 보는게 이해가 더 빠를듯~? 1 2 3 4 ..

상근이가 가지고 있는 N개의 카드 중에서 입력받은 M개의 정수와 일치하는 카드가 있는지 판별하여 출력하는 문제 어려울 거 없는 이분탐색 문제다. 하지만 시간초과를 막기 위해 모든 수단(이랄 것 까지 없지만..)을 동원해야 한다. BufferedWriter와 StringBuilder 쓰는 습관을 들여야겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.io.*; import java.util.Arrays; import java.util.StringToke..

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 문제. ( BOJ 1167과 제목까지 똑같은 문제다. 이걸 먼저 푸는게 맞는 듯!! ) [백준/BOJ/JAVA] 1167 트리의 지름 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 문제!! 5 // 트리의 정점의 개수 V 1 3 2 -1 // 정점 번호, 연결된 정점 번호, 연결된 정점까지의 pinevienna.tistory.com 1167번 문제와 마찬가지로 특정한 지점에서 가장 먼 정점을 구하고, 그 정점에서 가장 먼 정점을 찾아 거리를 구하면 되는 문제다. 그래서 코드는 거의 똑같지만 딱 두 곳이 다르다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 문제!! 5 // 트리의 정점의 개수 V 1 3 2 -1 // 정점 번호, 연결된 정점 번호, 연결된 정점까지의 거리, 끝(-1) 2 4 4 -1 3 1 2 4 3 -1 // 연결된 정점이 2개 4 2 4 3 3 5 6 -1 // 연결된 정점이 3개 5 4 6 -1 입력값은 위와 같다. list에 트리 연결 정보를 저장하고, 부모를 제외한 연결 노드들을 타고 들어가며 거리를 재면 된다. 이 때, 대체 어느 노드에서 시작해야 가장 긴 거리를 찾을 수 있을지가 문제인데.. 모든 노드들에서 다 탐색할 필요 없이 임의의 시작점에서 가장 먼 노드 하나를 구하고, 거기서 다시 가장 먼 노드를 찾으면 된다. 참고 블로그