[BOJ] 1620. 나는야 포켓몬 마스터 이다솜 Python, Java

https://www.acmicpc.net/problem/1620

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

 

 

1. 해결방법

이 문제에서 포인트는 시간복잡도이다.

리스트에 대한 시간복잡도와 파이썬의 딕셔너리의 시간복잡도를 이해하는지에 대한 의도가 드러나있다.

리스트의 경우,
자주 쓰이는 append와 pop과 같은 경우에는 O(1)의 시간복잡도를 가지지만, list.index()와 리스트 탐색의 경우에는 O(N)의 시간복잡도를 가진다.
해당 문제는 isdigit() 메서드까지 활용하기 때문에 100000이 기본인 데이터에서 이러한 O(N) 시간 복잡도를 난발하면 시간복잡도에서 아웃이 된다.

딕셔너리는
값을 추가와 탐색과정에서 모두 O(1)의 시간복잡도를 가진다.

시간복잡도에서 우수하지만, 그럼에도 불구하고 리스트를 많이 사용하는 이유는... 아무래도 제공되는 메서드가 많다 보니 리스트를 자주 사용하는 것 같다.

이 문제오 같은 단순 탐색과 같은 경우에는 딕셔너리를 활용해서 시간복잡도를 의식하는 상황도 주시해야겠다.

 

 

 

2. 시간 초과 코드

원인 !
생각없이 리스트로 풀었다가 시간초과가 났다,,,

리스트로 탐색할 경우에는 시간 복잡도가 O(N)이다. 또한, isdigit() 메서드도 O(N)의 시간 복잡도를 가지고 있으므로 100000만개의 포켓몬을 가지고 있을 때, 100000만번이나 탐색을 해야한다는 의미가 된다.

큰일큰일;;;

import sys

input = sys.stdin.readline


N, M = map(int, input().split())

pokets = []
for i in range(N):
    pokets.append(input().strip())

for i in range(M):
    question = input().strip()

    if question.isdigit():
        print(pokets[int(question) - 1])
    else:
        print(pokets.index(question) + 1)

 

 

3. 정답코드 Python

Python dictionary는 hash table을 사용한것으로써, 읽을때 시간복잡도가 O(1)이다.

인덱스의 탐색이 주요가 되는 경우에는 파이썬의 딕셔너리를 사용하면 탐색의 시간을 엄청나게 줄일 수 있다.

import sys

input = sys.stdin.readline


N, M = map(int, input().split())

pokets = {}

for i in range(N):
    poket = input().strip()

    pokets[i + 1] = poket
    pokets[poket] = i + 1

for i in range(M):
    question = input().strip()

    if question.isdigit():
        print(pokets[int(question)])
    else:
        print(pokets[question])

 

4. 정답코드 Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static String poket;
    static String question;

    static HashMap<String, String> pokets = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            poket = br.readLine();
            pokets.put(Integer.toString(i + 1), poket);
            pokets.put(poket, Integer.toString(i + 1));

        }

        for (int i = 0; i < M; i ++) {
            question = br.readLine();

            if (isNumber(question)) {
                System.out.println(pokets.get(question));
            }
            else {
                System.out.println(pokets.get(question));
            }
        }
    }

    public static boolean isNumber(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (! Character.isDigit(s.charAt(i))) {
                return false;
            }
        }
        return true;
    }
}