[백준] 17219번 비밀번호 찾기 (Map, JAVA)

 

map을 생각하지 못하고

계속 빙글빙글 제자리 걸음만 한 문제!

 

쉬운 문제였는데 시간이 오래걸렸다.

답 보기를 잘한 문제다!

 

 

---

문제

 

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

17219번: 비밀번호 찾기

 

 

---

 

설계

 

알고리즘 설계 [접근방법] : Map

map.get의 시간복잡도는 O(1)이다.

사이트의 주소가 일치하는 경우가 없으니, map의 key를 사이트 주소로 하고 비밀번호를 value로 하면 풀린다.

 

처음에 사이트와 비밀번호를 각각 담은 list를 2개 생성했다.

찾으려고 하는 사이트의 인덱스를 list.indexOf로 찾고, 비밀번호를 get을 이용해서 찾았는데 시간초과가 발생했다.

검색해보니 indexOf의 시간복잡도는 O(n)이었다.

 

풀이 과정

 1.

n과 m을 입력받는다.

 

2.

map을 생성한 후, key에 사이트 주소를, value값으로는 비밀번호를 저장한다.

 

3.

map.get으로 사이트에 맞는 비밀번호를 얻고, 출력한다.

 

 

 

---

코드

 

import java.io.*;
import java.util.*;

public class Test_17219_비밀번호찾기 {
	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 = 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 site = br.readLine();
			bw.write(map.get(site) + "\n");
		}
		
		bw.flush(); 
	}
}

 

 

(❁´◡`❁)

끝!