자바

13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net > 의식의 흐름 dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과 옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공 > 풀이 과정 1. 원생의 수(N), 조의 개수(K)를 입력 받는다. 2. 모든 원생의 키를 배열(heights)에 저장한다. 3. 옆 원생과의 키 차이를 배열(gap)에 저장한다. 4. 배열 gap을 오름차순으로 정렬한 후 `N-K`..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net > 의식의 흐름 연산자가 +, -만으로 이루어져 있으니까 -를 기준으로 각각의 합을 구해서 빼면 최소가 나오지 않을까.. > 풀이 과정 1. 식을 입력 받는다. 2. i번째 문자(ch)가 숫자인지 아닌지 판단한다. 숫자인 경우 num에 담아둔다. num *= 10; num += Integer.parseInt(Character.toString(ch)); 문자인 경우 '-' 전까지 나온 수들의 합을 구한 후 deque에 담아둔다. 3. 문자열 길이만큼 2번 반..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net > 의식의 흐름 트리 만들구 후위 순회하면 되겠징,,, > 풀이 과정 1. 첫번째 입력값을 루트노드로 지정한다. 2. 이후 입력값들에 대해 루트노드를 기준으로 트리를 생성한다. 왼쪽, 오른쪽 Node를 담는 Node 클래스 이용 3. 입력 없을 때까지 2번 과정 반복한다. while((input=br.readLine()) != null && !input.isEmpty()){ // 2번 과정 } 4. 후위 순회 후 결과 출력한다. 후위 순회 시, 왼쪽..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net > 의식의 흐름 > 풀이 과정 1. 연결된 노드 담기 2. 1번 노트부터 시작 (트리의 루트를 1이라고 정했기 때문) 3. 현재 노드(nowIdx)와 연결된 노드들의 부모 설정하기 (parents[]) 4. 2번 노드부터 부모 출력 > 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; imp..

14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net > 의식의 흐름 간선은 끊으면 어떤 경우여도 그래프가 2개로 나뉘니까 yes일거고 정점은 다른 정점 한 개랑 연결된 애만 아니면 되겠지..? > 풀이 과정 1. 각 정점에 대해 연결된 정점 번호를 담을 ArrayList 생성 ArrayList links = new ArrayList(); for(int i=0;i 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net > 의식의 흐름 시간 제한이 6초인 것을 보고 시간이 너무 널널한데? 생각했다가 T(테스트케이스의 수) 범위가 없는 것을 보고 PriorityQueue 2개를 쓰면 위험할 수도 있겠다는 생각을 했다. PriorityQueue 하나만 쓰는 방법을 생각하다가 TreeSet + PriorityQueue -> TreeMap 순으로 코드를 계속 수정했다,, > 시간복잡도 # PriorityQueue - 삽입, 삭제 : O(logN) # Treemap - 삽입, 삭제 ..

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net > 의식의 흐름 해시맵 써서 정렬하고 어찌저찌,, > 풀이 1. HashMap(key = 종 이름, value = 입력된 횟수)을 이용하여 종 이름이 몇 번 입력되었는지 저장한다. 2. 1번 과정을 입력 끝날 때까지 반복 // 입력 끝날 때까지 반복 while((type=br.readLine())!=null && !type.isEmpty()){ //... } 3. HashMap의 키값들(종 이름)을 사전순으로 정렬한다. 4. 정렬된 순서대로 해당 종이..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net > 의식의 흐름 priority queue와 deque을 같이 쓰면 괜찮지 않을까?라는 생각과 함께 시도했으나 시간 초과,,, 시간복잡도가 괜찮은줄 알았는데 "priority queue의 remove(Object o) 시간복잡도 = O(N)" 이었고 결과적으로 O(N*N)의 시간복잡도를 가지게 되어 시간 초과가 난 것이었다. 어떻게 하면 시간복잡도를 줄일 수 있을까 고민고민했지만 결국 포기하고 풀이를 찾아봤당😅 > 풀이 ** deq..