완주하지 못한 선수 (해시, 정렬)

jundragon·2일 전
0
post-thumbnail

https://programmers.co.kr/learn/courses/30/lessons/42576

행동영역

completion 배열에 없는 participant의 원소를 찾는 문제로 다음의 해법이 있다

방법 1. 해시 사용

participant와 completion을 완전 탐색해서 해시 자료구조에 넣고 카운트 한다

방법 2. 정렬 사용

participant와 completion 배열은 항상 하나의 원소 차이가 난다는 점을 이용해서 두 배열을 정렬하고 순서대로 하나씩 인덱스를 비교해서 답을 찾는다

두 방법 모두 시간복잡도는 O(n)

필요지식

java.util 패키지 사용 지식

  • 정렬 사용법
  • 해시 사용법

코드

나의 풀이

두 배열을 정렬하고 순서대로 값을 비교해서 값이 다르면 반환하였다

다른 풀이

participant 요소를 HashMap에 넣어 카운트 정보를 저장한다
completion 요소를 key로 하여 HashMap에서 하나씩 꺼내면서 카운트를 줄인다

위의 작업 후 HashMap에 값이 0이 아닌 key가 있다면 그 값이 완주하지 못한 선수다

profile
끄적끄적 🐣

0개의 댓글