(백준/자바) 1620번 문제 : 나는야 포켓몬 마스터 이다솜

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net)

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

처음에 HashMap 이용해서 14분 만에 짰는데 시간초과 나왔다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
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));
        StringBuilder sb = new StringBuilder();
    	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=1;i<=N;i++) {
        	map.put(Integer.toString(i), br.readLine());
        }
        for(int i=0;i<M;i++) {
        	String str = br.readLine();
        	if(map.containsKey(str))
        		sb.append(map.get(str)+"\n");
        	if(map.containsValue(str))
        		for(String c : map.keySet())
        			if(map.get(c).equals(str))
        				sb.append(c+"\n");
        }
        System.out.println(sb);
    }
}

이진탐색을 써야하나 싶어서 1시간 걸려서 다시 짰는데 또 또 ! 시간초과가 나왔다 !!! ㅡㅡ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
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));
        StringBuilder sb = new StringBuilder();
    	StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map <Integer,String> map = new HashMap<>();
        List <Integer> key = new ArrayList<>();
        List <String> value = new ArrayList<>();

        for(int i=0;i<N;i++) {
        	String v = br.readLine();
        	map.put(i, v);
        	key.add(i);
        	value.add(v);
        }
        
        Collections.sort(key);
        Collections.sort(value);
        
        for(int i=0;i<M;i++) {
        	String str = br.readLine();
        	
        	int start = 0;
        	int end = N-1;
        	if(value.contains(str)) {
        		int ch = 0;
        		while(start <=end) {
            		int  mid = (start+end) /2;
            		if(value.get(mid).compareTo(str) > 0) end = mid -1;
            		else if(value.get(mid).compareTo(str) < 0) start = mid +1;
            		else if(value.get(mid).compareTo(str) == 0) {
            			for(int c : map.keySet()) {
            				if(map.get(c).equals(str)) {
            					sb.append(c+1+"\n");
            					ch = 1;
                    			break;
            				}
            			}
            		if(ch == 1) break;		
            		}
            			
        		}
        	}
        	else {
        		int ch = 0;
        		while(start <=end) {
            		int  mid = (start+end) /2;

            		if(key.get(mid) < Integer.parseInt(str)) start = mid +1;
            		else if(key.get(mid) >Integer.parseInt(str)) end = mid-1;
            		else if(key.get(mid) == Integer.parseInt(str)) {
            			sb.append(map.get(mid-1)+"\n");
            			ch=1;
            			break;
            		}
            		if(ch==1)break;
        		}
        	}
        }
        System.out.println(sb);
    }
}

뭐가 문제냐 대체

 

-- > 해결

처음 코드에서 key를 포켓몬 이름, value를 포켓몬 번호로 해서 Hashmap에 넣고

list에 이름을 동시에 넣음.

 

그러고 입력되는 문제가 숫자인지 문자열인지 판단해서

숫자이면 : 

 그 숫자인덱스를 가지는 list의 문자열을 출력

문자이면 :

 HashMap에서 문자 키 값을 가지는 value 번호값 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
    	StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map <String,String> map = new HashMap<>();
        List <String> list = new ArrayList<>();
        for(int i=1;i<=N;i++) {
        	String input = br.readLine();
        	map.put(input,Integer.toString(i)); //이름 , 번호 순
        	list.add(input);
        }
        for(int i=0;i<M;i++) {
        	String str = br.readLine();
        	if(str.charAt(0) >= 48 && str.charAt(0) <= 57 ) { //숫자 입력시
        		sb.append(list.get(Integer.parseInt(str)-1)+"\n");
        	}
        	else //이름 입력시 -> 번호 출력
        		sb.append(map.get(str)+"\n");
        }
        System.out.println(sb);
    }
}