728x90
내가 힘들었던 것
- 문제를 잘 이해하자.
- 해당 문제는 부모의 형제의 자식들의 수를 정확하게 세는 것이 정답이다.(깊이만 같다고 해서 부모 형제가 아니다.)
- NoSuchElement
- 항상 input 메서드로 입력값을 세팅해주는데 제대로 다 받지도 않고 return을 시켜버려서 해당 예외가 발생했다.
- 메모리를 효율적으로
- 꼭 숫자 자체를 index로 둘 필요없이 다른 배열에 숫자를 저장하는 배열을 두고 해당 index에 들어있는 숫자로 사용하면 된다. 아래 두 코드를 비교해보면 된다.
import java.io.*;
import java.util.*;
public class Main {
public static int[] pArr = new int[1_000_001];
public static int[] arr;
public static int[] childCount = new int[1_000_001];
public static int N, K;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
input(br);
if(N == 0) break;
pro();
}
}
static void pro() {
if(N <= 1 || K == arr[0]) {
System.out.println(0);
return;
}
int p = pArr[K];
if(p == arr[0]){
System.out.println(0);
return;
}
int pp = pArr[p];
int count = 0;
for(int i = 1; i < arr.length; i++){
int cur = arr[i];
if(pArr[cur] == pp && cur != p){
count += childCount[cur];
}
}
System.out.println(count);
}
static void input(BufferedReader br) throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if(N==0) return;
arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0 ; i<N ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i=0 ; i<1_000_001 ; i++){
pArr[i] = 0;
childCount[i] = 0;
}
if(N == 1) return;
int parentIdx = 0;
int p = arr[parentIdx];
childCount[p]++;
pArr[arr[1]] = p;
for(int i=2 ; i<N ; i++){
int c = arr[i];
if(arr[i-1] != c -1) parentIdx++;
p = arr[parentIdx];
childCount[p]++;
pArr[c] = p;
}
}
import java.util.*;
import java.io.*;
public class Main {
public static int N;
public static int K;
public static long result = 0;
public static int[] arr;
public static int[] parents;
public static int[] childCount;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
input(br);
if(N==0) {
break;
}
pro();
System.out.println(result);
}
}
public static void input(BufferedReader br) throws Exception{
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if(N==0) return;
arr = new int[N];
parents = new int[N];
childCount = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
int num = Integer.parseInt(st.nextToken());
arr[i] = num;
}
parents[0] = -1;
int parent = -1;
for (int i = 1; i < N; i++) {
parent++;
childCount[parent]+=1;
parents[i] = parent;
while(i+1 < N && arr[i+1] == arr[i]+1){
i++;
childCount[parent]+=1;
parents[i] = parent;
}
}
}
public static void pro(){
int idx = 0;
while(arr[idx] != K) idx++;
int parent = parents[idx];
if(parent == -1) {
result = 0;
return;
}
int pp = parents[parent];
result = 0;
for(int i=0 ; i<parents.length ; i++){
if(parents[i] == pp && parent != i) result += childCount[i];
}
}
}
1000001 배열을 초기화 해주는 부분이 사라져서 아래 코드가 1908ms -> 908ms로 더 빠르다.
728x90
'coding test > baekjoon' 카테고리의 다른 글
[baekjoon] 1495. 기타리스트 - dp 값 범위 보고 유추해보기 (0) | 2025.05.28 |
---|---|
[baekjoon] 21275 폰 호석만 - 진법 변환 (0) | 2025.05.23 |
[baekjoon] 20168 골목 대장 호석 - 기능성 (0) | 2025.05.22 |