이제 코딩테스트나 알로리즘에서 사용하는 알아두면 좋을 알고리즘에 대해 정리해보려고 한다.
프로그래머스의 코테 준비를 위한 키트와 제미나이한테 물어보니, 정리하면 좋을 만한 개념이 대략 15개가 있던 것 같다.
오늘은 그 중에 첫번째 해시에 대한 문제를 풀어보려고 한다.
프로그래머스의 [완주하지 못한 선수] 라는 문제를 풀것이다.
https://school.programmers.co.kr/learn/courses/30/lessons/42576
HashMap
우선 제미나이의 답변에 따르면 해시는 다음과 같다.
| 1. 해시란 무엇인가? (가장 쉬운 비유) 핵심 컨셉: "데이터를 '찾기 쉽게' 정리해두는 똑똑한 서랍장" 코딩 테스트에서 '해시'라는 단어를 마주치면, Java의 HashMap이나 HashSet을 떠올리면 거의 맞습니다. HashMap은 마치 이름표가 붙어있는 수많은 서랍장과 같습니다. Key: 서랍장에 붙어있는 이름표 (e.g., "leo", "kiki", "eden") Value: 서랍장 안에 들어있는 내용물 (e.g., 각 선수의 등장 횟수 1, 2, 3...) 이 서랍장의 가장 큰 장점은, 내가 "kiki"라는 이름표가 붙은 서랍장을 찾고 싶을 때, 첫 번째 서랍부터 하나씩 열어볼 필요 없이 단 한 번에 그 서랍을 찾아 열 수 있다는 것입니다. 이 '단 한 번에' 찾아내는 속도(평균 시간 복잡도 O(1))가 바로 해시의 핵심입니다. 2. 이 문제에서 왜 해시(HashMap)를 사용해야 할까? 이 문제의 제약 조건 중 **"참가자의 수는 최대 100,000명"**과 **"동명이인이 있을 수 있습니다"**라는 두 가지가 핵심 힌트입니다. 속도 문제 (효율성): 참가자가 100,000명인데, 만약 참가자 한 명을 완주자 명단에서 찾기 위해 매번 100,000번씩 비교한다면? 시간 초과가 뻔합니다. 우리는 훨씬 더 빠른 '검색' 방법이 필요합니다. 동명이인 문제: "leo"라는 선수가 2명 참가하고 1명만 완주했다면, "leo가 완주했는가?"라는 질문만으로는 부족합니다. "참가한 leo 2명 중, 완주한 leo는 1명이니, 남은 leo는 1명이다" 와 같이 이름별로 인원수(개수)를 정확히 세야 합니다. |
즉 다 비교할 필요 없이, 한번에 찾아낼때 도움이 되는 것 같다.
완주하지 못한 선수
import java.util.*;
import java.io.*;
import java.util.stream.*;
import java.math.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Map<String, Integer> map = new HashMap<>();
for (String str : participant) {
map.put(str, map.getOrDefault(str, 0) + 1); // getOrDefault 사용으로 값이 없으면 오류가 아닌 Default 값을 가져오게 하기
}
for (String str : completion) {
map.put(str, map.get(str) - 1); // 완주했으면 빼기
}
Set<String> key = map.keySet(); // 사실 set 안하고 participant 써도 되지만 연습겸
for (String str : key) {
if (map.get(str) != 0) {
answer = str;
break;
}
}
return answer;
}
}
일단 이건 내 풀이 내용이다.
보면 굳이 해시가 아니라, 반복문이나 정렬로 풀수 있을 것 같아 보인다.
하지만 그렇게 하면 시간 복잡도가 커져서, 시간을 줄이기 위해 해시를 사용해야한다.
댓글