문제 설명
여러분은 여러 단어들로 구성된 사전을 가지고 있습니다. 이 사전에서 특정 단어가 있는지 여부를 확인하고,
그 단어의 의미를 출력하는 프로그램을 만들어야 합니다.
입력으로는 사전의 단어 리스트와 사용자가 입력한 단어가 주어집니다. 만약 사용자가 입력한 단어가
사전에 없으면 “단어를 찾을 수 없습니다.”라는 메시지를 출력해야 합니다.
입력 사항
- 첫 번째 줄에는 정수
N이 주어집니다 (1 ≤ N ≤ 100,000). - 다음
N개의 줄에는 사전의 단어들이 주어집니다. - 마지막 줄에는 사용자가 검색할 단어가 주어집니다.
출력 사항
사용자가 입력한 단어의 의미를 출력하되, 단어가 사전에 없으면 “단어를 찾을 수 없습니다.”라고 출력합니다.
예시
입력: 5 apple banana grape orange pear grape 출력: "grape": 포도
입력: 5 apple banana grape orange pear watermelon 출력: 단어를 찾을 수 없습니다.
문제 해결 전략
이 문제는 단어의 검색을 수행해야 하므로, 효율적인 데이터 구조를 선택하는 것이 핵심입니다.
해시맵(HashMap)을 사용하면 평균적으로 O(1)의 시간 복잡도로 단어를 검색할 수 있습니다.
따라서 사전을 해시맵에 저장한 다음, 사용자로부터 입력받은 단어를 해시맵에서 검색하여
의미를 출력하는 방식으로 문제를 해결할 수 있습니다.
자바 코드 구현
아래는 위의 문제를 해결하기 위한 자바 코드입니다. 이 코드는 해시맵을 사용하여 사전을 구현하고,
사용자 입력을 처리합니다.
import java.util.HashMap;
import java.util.Scanner;
public class DictionarySearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 사전의 단어 수 입력
int N = scanner.nextInt();
scanner.nextLine(); // 개행 문자 제거
// 해시맵 초기화
HashMap dictionary = new HashMap<>();
// 사전 단어와 의미 입력
for (int i = 0; i < N; i++) {
String word = scanner.nextLine(); // 단어 입력
String meaning = scanner.nextLine(); // 의미 입력
dictionary.put(word, meaning);
}
// 검색할 단어 입력
String searchWord = scanner.nextLine();
// 단어 검색 및 출력
if (dictionary.containsKey(searchWord)) {
System.out.println("\"" + searchWord + "\": " + dictionary.get(searchWord));
} else {
System.out.println("단어를 찾을 수 없습니다.");
}
scanner.close();
}
}
코드 설명
1. Scanner 클래스를 이용해 사용자 입력을 처리하고, HashMap을 사용해 사전을 저장합니다.
2. 먼저 사전의 크기 N을 입력받고, 입력한 만큼 반복하여 단어와 그 의미를 해시맵에 추가합니다.
3. 다음으로 사용자가 검색할 단어를 입력받아, 해시맵에 해당 단어가 있는지 확인합니다.
4. 만약 단어가 존재하면 그 의미를 출력하고, 존재하지 않으면 “단어를 찾을 수 없습니다.”라는 메시지를 출력합니다.
복잡도 분석
– 시간 복잡도: 단어를 해시맵에 추가하는 데 O(1), 검색하는 데 O(1)입니다. 전체적으로 O(N)입니다.
– 공간 복잡도: 해시맵에 N개의 단어와 각각의 의미를 저장하므로 O(N)입니다.
마무리
이번 글에서는 자바를 이용해 사전에서 특정 단어를 찾는 알고리즘 문제를 함께 살펴보았습니다.
해시맵을 사용하여 효율적으로 단어를 검색하는 방법을 배웠고, 문제 해결 과정을 통해 코딩테스트에서
어떤 접근 방식을 취해야 하는지에 대한 통찰을 얻었기를 바랍니다.
앞으로의 코딩테스트에서 이와 같은 문제를 만났을 때 자신감을 가지고 해결할 수 있기를 바랍니다.