[Baekjoon] 17219 - 비밀번호 찾기

📝 문제

 

 

 

🔑 풀이 과정

class 3 중에서 미해결 문제를 보다가, 이게 왜 class3지? 하면서 풀었던 문제.

 

① 처음에는 2차원 배열, 이중 for문을 사용해서 문제를 풀이했다.

행이 n, 열이 2인 2차원 배열을 생성해서, n[0]에는 사이트의 주소, n[1]에는 비밀번호를 넣어준다.

그 후 사이트 주소를 입력받고, 0부터 N-1까지 배열을 탐색하면서 사이트 주소(n[0])가 같은 것을 찾으면, 그것의 비밀번호(n[1])를 출력하는 방식

 

그러나 시간 초과로 오답처리가 되었다.

이건 생각해보면 당연한건데 N = 10^5, M = 10^5로, 이중 for문을 돌리면 10^10이므로 시간 초과가 난다.

문제 처음 볼 때 시간을 생각을 안 한 것도 아니었는데, 제한시간이 5초인걸 보고 순간 잘못 계산 했었다.

1차 제출 오답 - 시간 초과

 

② 그러면 배열이 아닌 새로운 자료구조를 사용해야 한다.

이것이 Map이다.

Map으로 저장해 준뒤, 사이트 주소를 key로 받아 비밀번호를 value로 받으면 된다.

 

③ 문제의 노트부분에 보면 scanner를 사용하면 시간초과가 날 수 있다며 BufferedReader와 BufferedWriter를 추천한다. 난 이미 후자를 사용하고 있어서 이 부분은 패스.

 

 

🔓 답안

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        Map<String, String> map = new HashMap<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            map.put(st.nextToken(), st.nextToken());
        }

        for(int i = 0; i < M; i++){
            String str = br.readLine();
            String ans = map.get(str);
            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 해시를 사용한 집합과 맵