[백준] 19637 IF문 좀 대신 써줘 - Java

문제 - IF문 좀 대신 써줘

 

난이드 - 실버 3

 

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

19637번: IF문 좀 대신 써줘

---

문제 설명

입력

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

 

출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

 

예제 입력

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

 

예제 출력

WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG

 

---

접근 방법

- 시간 제한이 1초라 반복문을 2개 이상으로 풀면 안될 것 같다 -> 완전 탐색이 아니라 이분탐색으로 시간을 줄여야 할 것 같다

- N과 M은 범위가 (1 ≤ N ≤ 10^5) 이기 때문에 int형으로 선언해줘도 될 것 같다

- 처음에 전투력과 캐릭터 이름이 한쌍으로 나오기 때문에 hashmap 에 넣을까 하다 그럴 문제는 아닌 것 같아서 객체로 만들어줘서 저장 하였다

- 각각 값을 받으면 저장해둔 캐릭터 리스트로 이 값이 어디에 포함되는지 탐색해야 겠다

- 최소를 0 index로 하고 최대를 list size - 1 index로 잡아줬다

 

---

코드 작성

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    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());
        List<Character> list = new ArrayList<>();


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list.add(new Character(st.nextToken(), Integer.parseInt(st.nextToken())));
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(br.readLine());

            int left = 0;
            int right = N - 1;

            while (left <= right) {
                int mid = (left + right) / 2;

                if (list.get(mid).getPower() < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            bw.write(list.get(left).getPowerName() + "\n");
        }
        bw.flush();
    }
}

class Character {
    private final String powerName;
    private final int power;

    public Character(String powerName, int power) {
        this.powerName = powerName;
        this.power = power;
    }

    public String getPowerName() {
        return powerName;
    }

    public int getPower() {
        return power;
    }
}

 

---

풀고 느낀점

 

1. 이 문제는 일반적인 이분 탐색 문제 인 것 같다

2. 이 문제는 처음에 캐릭터의 파워와 이름을 어떤식으로 저장할지도 고민 해봐야 한다 (2차원 배열, map, 객체) 등등으로..