[실버4] BOJ17219 비밀번호 찾기

요구사항 정의

• 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.
• N개 주소의 메모장이 있을 때, 사이트 주소를 M개만큼 입력하면 그에 해당하는 비밀번호를 출력하라
• 입력은 N개((1 ≤ N ≤ 100,000)만큼 공백을 기준으로 주소|비밀번호

문제 분석

• 시간 제한 : 5초, 최대 N: 100,000 → O(N^2)부터는 불가
• 주소를 key로 갖고 비밀번호를 value로 갖는 HashMap에 저장하기
  → key를 넣었을 때 value가 조회되는 시간복잡도 O(1)

손으로 풀기

1. N번만큼 반복 : br.readline().split(” “) → [0]번의 요소를 HashMap에 key로 [1] 요소를 value로 저장
2. M번만큼 반복 : 1)번에서 저장한 HashMap에서 br.readLine()한 것을 조회

Code

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

public class BOJ17219 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        HashMap<String,String> myHash = new HashMap<>();

        for(int i=0;i<N;i++){
            String[] urlAndPassword = br.readLine().split(" ");
            myHash.put(urlAndPassword[0], urlAndPassword[1]);
        }

        for(int i=0;i<M;i++){
            String searchUrl = br.readLine();
            System.out.println(myHash.get(searchUrl));
        }

    }
}