https://www.acmicpc.net/problem/1620
1620번: 나는야 포켓몬 마스터 이다솜
첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면
www.acmicpc.net
문제가 너무 긴 관계로 삽입은 생략한다.
결국엔 영문으로된 포켓몬의 이름을 N개 입력받고 추가로 입력된 M개의 포켓몬 이름 또는 숫자에 매칭되는 포켓몬 이름, 숫자 중 하나를 출력하면 되는 문제이다.
내 코드
\(N\)과 \(M\)은 100,000보다 작거나 같기 때문에 \(O(N)\)의 시간복잡도 내에 풀어야 하는 문제이다.
배열로 풀게된다면 indexOf등의 메서드 사용 시 \(O(N)\)의 시간복잡도가 걸리게 되므로 최대 10만에 반복문과 함께 사용 시 최종적으로 \(O(N^2)\)의 시간복잡도가 발생한다.
그렇기 때문에 HashMap을 사용하게 되었고, String을 키로, Integer를 밸류로 갖는 Map과 반대의 맵을 생성하여 입력 하나를 받으면 두 맵에 저장하도록 설계했다.
참고
참고 코드를 살펴보자.
String을 키와 밸류로 갖는 맵 하나만을 만들었고, 입력으로 숫자가 들어왔을 때 Integer.toString()을 호출해 간단하게 구현하였다.
배워가자
참고 코드 출처 - https://bcp0109.tistory.com/62
'Algorithm' 카테고리의 다른 글
| [Java] 프로그래머스 - 두 큐 합 같게 만들기(lv.2) (1) | 2023.10.20 |
|---|---|
| [Java] 백준 18870 - 좌표 압축 (0) | 2023.04.21 |
| Java 알고리즘 풀이 기능 구현, 메서드 호출 모음 (0) | 2023.03.25 |
| 2018 카카오 신입 공채 1차 코딩 테스트 문제 2. 다트 게임(파이썬) (0) | 2022.12.01 |
| 백준 1010 - 다리 놓기 (0) | 2022.09.16 |
