[BOJ/Java] 17219. 비밀번호 찾기

[BOJ/Java] 17219. 비밀번호 찾기

17219번: 비밀번호 찾기

---

문제 해석

이 문제는 주어진 웹사이트 주소에 대응하는 비밀번호를 빠르게 찾는 문제이다. 웹사이트 주소와 비밀번호 쌍이 N개 주어지고, M개의 웹사이트 주소에 대해 해당 비밀번호를 찾아 출력하는 구조이다.

풀이 과정

1. 입력 처리: 사용자로부터 N (웹사이트-비밀번호 쌍의 수)과 M (조회할 웹사이트의 수)을 입력받는다.
2. 해시맵 구성: N개의 웹사이트와 비밀번호 쌍을 읽어 해시맵에 저장한다. 해시맵의 키는 웹사이트 주소, 값은 해당 비밀번호이다.
3. 비밀번호 조회 및 출력: M번에 걸쳐 웹사이트 주소를 입력받고, 해시맵을 통해 해당 주소의 비밀번호를 빠르게 조회하여 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S4.No17219;

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.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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 웹사이트와 비밀번호 쌍의 개수
		int M = Integer.parseInt(st.nextToken()); // 조회할 웹사이트의 개수
		HashMap<String, String> map = new HashMap<>(); // 웹사이트와 비밀번호를 저장할 해시맵

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String s = st.nextToken(); // 웹사이트 주소
			String p = st.nextToken(); // 해당 웹사이트의 비밀번호
			map.put(s, p); // 해시맵에 웹사이트와 비밀번호 저장
		}
		for (int i = 0; i < M; i++) {
			sb.append(map.get(br.readLine())).append("\n"); // 조회하고자 하는 웹사이트의 비밀번호를 출력 문자열에 추가
		}
		bw.write(sb.toString()); // 결과 출력
		bw.flush();
		bw.close();
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 해시맵의 조회 작업이 주를 이루므로 O(1)의 시간 복잡도를 갖는다고 가정할 수 있다. N개의 웹사이트와 비밀번호 쌍을 저장하는 데 O(N)의 시간이 소요되고, M개의 웹사이트를 조회하는 데 O(M)의 시간이 소요된다. 따라서 전체 시간 복잡도는 O(N + M)이다.

느낀점

해시맵을 이용한 데이터 관리와 빠른 조회 기능의 중요성을 이 문제를 통해 다시 한 번 확인할 수 있었다. 또한, 입출력 처리의 최적화가 프로그램의 성능에 크게 기여한다는 점을 경험하였다. 이러한 기술들은 다양한 프로그래밍 문제에서 유용하게 적용될 수 있다.