문제설명
입력 & 출력
나의 풀이
이번 문제는 듣도 못한 사람 N과 보도 못한 사람 M이 주어질 때 듣도 못한 사람 + 보도 못한 사람 = "듣도보도 못한 사람"을 구하는 문제입니다.
먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, StringTokenizer를 사용하여 N과M을 공백을 기준으로 분리하여 각각 저장해줍니다.
저는 N과 M의 입력을 한 번에 받아서 듣지도 보지도 못한 사람은 vlaue가 2가 형성되도록 구성했습니다.
HashMap을 선언해 주고, N과 M을 입력을 받고, getOrDefault() 메서드를 사용하여 해당하는 이름을 1씩 증가했습니다.
이러면 듣도 보도 못한 사람은 위 실행결과와 같이 value가 2가 형성됩니다.
그리고 keySet() 메서드와 get() 메서드를 사용하여 value가 2 이상인 사람의 이름을 ArrayList에 넣어줍니다.
그리고 ❗️문제에서 요구한 대로 "듣보잡의 수와 그 명단을 사전순으로 출력한다."를 만족하기 위하여 Collections의 sort() 메서드를 사용하여 리스트를 사전순으로 정렬해 줍니다.
마지막으로 리스트의 크기와 이름을 출력하며 마무리해줍니다.
refactoring ✅
전체적인 로직은 "나의 풀이"와 동일하지만 이번 코드는 "나의 풀이"처럼 HashMap이 아니라 HashSet을 사용하고, contains() 메서드를 사용했습니다.
Set에 듣지도 못한 사람을 추가해 주고, ArrayList를 선언한 뒤 Set의 contains() 메서드를 사용하여 보도 못한 사람이 Set에 존재하는지 확인합니다.
만약 Set에 존재한다면 듣도 못하면서 보도 못한 사람 즉 "듣보잡"입니다.
- 1번 ➡️ HashSet
- 2번 ➡️ HahsMap
- 1번 코드에서는 듣도 보도 못한 사람들의 정보를 모두 HashMap에 저장하고, 중복 여부를 확인하면서 추가 작업을 수행합니다.
- 이 때 HashMap의 put, getOrDefault 메서드는 평균적으로 O(1)의 시간 복잡도를 가지므로, 전체 시간 복잡도는 O(N + M)입니다.
- 2번 코드에서는 듣도 못한 사람(N)을 HashSet에 저장하고, 보도 못한 사람(M)을 확인할 때 contains 메서드를 사용합니다.
- HashSet의 contains 메서드도 평균적으로 O(1)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도도 O(N + M)입니다.
두 코드 모두 시간 복잡도 면에서는 유사하며, 특정 상황에서는 HashSet을 사용한 두 번째 코드가 약간 더 빠를 수 있습니다. 이는 HashSet이 내부적으로 해시 함수를 사용하여 더 빠르게 검색할 수 있기 때문입니다.
하지만 이 차이는 입력의 크기가 매우 클 때에만 두드러지며, 보통은 미비한 차이입니다.
참고❗️
[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기
Java로 코딩테스트를 보거나 입력을 사용해야 할 때 Scanner 클래스를 사용하면 편리하지만 속도가 느리다는 단점이 있습니다. 그렇기 때문에 속도가 빠른 BufferReader 클래스를 사용을 하면 시간복
pixx.tistory.com
[JAVA] HashMap 이란 ❓ (1/2)
Java에서 데이터를 효율적으로 저장하고 빠르게 검색하기 위해 다양한 컬렉션 클래스가 제공됩니다. 그중에서도 HashMap은 키-값 쌍을 저장하고 관리하는 데 있어 매우 유용한 데이터 구조
pixx.tistory.com
[JAVA] HashSet 클래스 사용법 (중복 없는 데이터 집합)
자바를 활용하다 보면 중복되지 않는 유일한 값을 저장하고 관리해야 할 때가 있습니다. 이럴 때 사용할 수 있는 클래스가 HashSet입니다. HashSet은 고유한 요소들을 저장하는 데 최적화된 컬렉
pixx.tistory.com
[JAVA] ArrayList 알아보기 (동적 배열)
Java에서는 기본적으로 여러 데이터를 다룰 때 배열을 사용합니다. 그러나 배열은 정적이므로, 한 번 생성되면 크기를 변경할 수 없습니다. 배열은 처리할 데이터의 개수가 정해진 경우에 유용
pixx.tistory.com
'Coding Test > 백준' 카테고리의 다른 글
[백준] 균형잡힌 세상 (Stack, 스택, toCharArray, 4949번, Java) (0) | 2024.07.17 |
---|---|
[백준] 2×n 타일링 2 (동적계획법, DP, 11727번, Java) (0) | 2024.07.16 |
[백준] 색종이 (구현, 2차원 배열, BufferReader, 2563번, Java) (1) | 2024.07.16 |
[백준] 요세푸스 문제 (큐, Queue, BufferReader, 1158번, Java) (0) | 2024.07.15 |
[백준] 영화감독 숌 (브루트 포스, contains, 1436번, Java) (1) | 2024.07.14 |