1620번: 나는야 포켓몬 마스터 이다솜

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면

www.acmicpc.net

 

Language: Java

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());
 
        Map<String, Integer> map = new HashMap<>();
        List<String> list = new ArrayList<>();
 
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            map.put(s, i);
            list.add(s);
        }
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < M; i++) {
            String s = null;
            try {
                s = br.readLine();
                int num = Integer.valueOf(s);
                sb.append(list.get(num - 1)).append("\n");
            } catch (NumberFormatException nfe) {
                sb.append(map.get(s)).append("\n");
            }
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
}
 
 

🤔 해설

1. sb.append(list.get(num - 1)).append("\n");

    - 입력값을 숫자로 바꿔서 nfe가 발생하지 않으면 list에서 String 출력

2. catch (NumberFormatException nfe) { ... }

    - 입력값을 숫자로 바꿔서 nfe가 발생하면 map에서 value 출력

 

😮  외의 풀이

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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
 
public class Main {
 
    static StringBuilder sb;
 
    static Map<Integer, String> mapIntStr;
    static Map<String, Integer> mapStrInt;
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] NM = br.readLine().split(" ");
 
        int N = Integer.valueOf(NM[0]);
        int M = Integer.valueOf(NM[1]);
 
        mapIntStr = new HashMap<>();
        mapStrInt = new HashMap<>();
 
        for (int i = 1; i <= N; i++) {
            String name = br.readLine();
            mapIntStr.put(i, name);
            mapStrInt.put(name, i);
        }
 
        sb = new StringBuilder();
 
        for (int i = 1; i <= M; i++) {
            String str = br.readLine();
            result(str);
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
 
    public static void result(String str) {
        if (Character.isDigit(str.charAt(0))) {
            sb.append(mapIntStr.get(Integer.parseInt(str)) + "\n");
        } else {
            sb.append(mapStrInt.get(str) + "\n");
        }
    }
 
}
 
 

1. String[] NM = br.readLine().split(" ");

    - BufferedReader의 split 사용

2. mapIntStr, mapStrInt

    - Key-Value 타입을 달리해서 map에 각각 저장

3. if (Character.isDigit(str.charAt(0))) { ... }

    - Character 함수 중 숫자 판별 함수 사용

    - 1번째 글자만으로도 숫자인지 판별할 수 있으므로 charAt에 0 대입

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[백준] 1620 : 나는야 포켓몬 마스터 이다솜 (JAVA/자바)

BOJ 1620 : 나는야 포켓몬 마스터 이다솜 - https://www.acmicpc.net/problem/1620입력으로 주어지는 포켓몬 정보를 잘 저장해두고, 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가

velog.io

 

 

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

 

Language: Java

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.valueOf(st.nextToken());
        int[] arr = new int[N + 1];
 
        arr[0= 0;
 
        if (N >= 1) {
            arr[1= 1;
 
            for (int i = 2; i <= N; i++) {
                arr[i] = arr[i - 1+ arr[i - 2];
            }
        }
 
        bw.write(arr[N] + "");
 
        bw.flush();
        bw.close();
 
    }
}
 
 

🤔 해설

1. if (N >= 1) { ... }

    - N=0일 때, arr[1]을 입력하면 ArrayIndexOutofBoundsException이 발생하므로 조건문에서 처리

2. arr[i] = arr[i - 1] + arr[i - 2];

    - Fn = Fn-1 + Fn-2 (n ≥ 2)

 

😮  외의 풀이

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
 
        bw.write(fibonacci(N) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static long fibonacci(int N) {
        if(N==0return N;
        if(N==1return N;
        
        return fibonacci(N-2+ fibonacci(N-1);
        
    }
}
 
 

1. fibonacci(int N)

    - 재귀호출 사용

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[백준] 10870번 : 피보나치 수 5 - JAVA [자바]

 

st-lab.tistory.com

 

 

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

 

Language: Java

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());
 
        int[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        StringBuilder sb = new StringBuilder();
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.valueOf(st.nextToken()) - 1;
            int end = Integer.valueOf(st.nextToken()) - 1;
            int sum = 0;
            for (int j = start; j <= end; j++) {
                sum += arr[j];
            }
            sb.append(sum).append("\n");
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
}
 
 

🚨 시간 초과

- while (M-- > 0) { for(...){ ... } }

    - 2중 반벅문으로 인한 시간 초과

 

😮 찾아본 풀이

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());
 
        int[] arr = new int[N+1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i - 1+ Integer.parseInt(st.nextToken());
        }
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken());
            int sum = arr[end] - arr[start];
            bw.write(sum + "\n");
        }
 
        bw.flush();
        bw.close();
 
    }
}
 
 

1. arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());

    - 배열에 누적 합을 저장

2. int sum = arr[end] - arr[start];

    - 구간 합을 누적 합에서 계산

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[JAVA/백준] 11659번: 구간 합 구하기 4

PS & 개발 기록

iamheesoo.github.io

 

 

27433번: 팩토리얼 2

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

www.acmicpc.net

 

Language: Java

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.valueOf(br.readLine());
 
        long sum = 1;
        while (n-- > 0) {
            sum *= (n + 1);
        }
 
        bw.write(sum + "");
 
        bw.flush();
        bw.close();
 
    }
}
 
 

🤔 해설

1. sum *= (n + 1);

    - num--, 후위 연산자에 의해 n 값이 감소된 상태로 계산되므로 +1

 

😮  외의 풀이

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.valueOf(st.nextToken());
 
        bw.write(factorial(N) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static long factorial(long N) {
 
        if (N <= 1)
            return 1;
 
        return N * factorial(N - 1);
    }
}
 
 

1. factorial(long N)

    - 재귀호출 사용

    - 매개변수 N에서 직접 계산하므로 처음부터 타입을 long으로 입력받음

 

 

 

🔗 소스 코드
GitHub

 

 

11050번: 이항 계수 1

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\))

www.acmicpc.net

 

Language: Java

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.valueOf(st.nextToken());
        int b = Integer.valueOf(st.nextToken());
 
        int top = 1;
        int btm = 1;
        
        int cnt = b;
        while(cnt-->0) {
            top *= a;
            a--;
            btm *= b;
            b--;
        }
        
        bw.write((top/btm)+"");
 
        bw.flush();
        bw.close();
 
    }
}
 
 

🤔 해설

* 이항계수: n개의 원소에서 k개의 원소를 뽑아내는 경우의 수

nCk = n! / (n-k)! * k!

1. while(cnt-->0){ ... }

    - 분모의 개수는 분자의 시작값과 동일하므로 cnt동안 반복

 

😮  외의 풀이

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        int result = factorial(N) / (factorial(N - K) * factorial(K));
 
        bw.write(result + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int factorial(int i) {
        if (i <= 1)
            return 1;
 
        return i * factorial(i - 1);
    }
}
 
 

1. public static int factorial(int i) { ... }

    - 재귀 호출을 통한 팩토리얼 구현

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        bw.write(pascalsT(N, K) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int pascalsT(int N, int K) {
        if(N==| K==0)
            return 1;
        
        return pascalsT(N-1, K-1+ pascalsT(N-1, K);
    }
}
 
 

* 파스칼의 삼각형 법칙

n+1Cr+1 = nCr + nCr+1

n번째 행의 r번째 수 (nCr)는 (n-1)번째 행의 (r-1)번째 수 (n-1Cr-1)과 (n-1)번째 행의 r번째 수 (n-1Cr)의 합과 같다.

 

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
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        dp = new int[N + 1][K + 1];
 
        bw.write(pascalsT(N, K) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int pascalsT(int N, int K) {
 
        // Memoization
        if (dp[N][K] > 0)
            return dp[N][K];
 
        if (N == K | K == 0)
            return dp[N][K] = 1;
 
        return dp[N][K] = pascalsT(N - 1, K - 1+ pascalsT(N - 1, K);
    }
}
 
 

* Memoization 활용

Memoization은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 알고리즘 [접근 방법] 이항 계수(Binomial coefficient) 문제 자체는 매

st-lab.tistory.com