알고리즘 - 이현주 작성
01. 폰켓몬
문제 설명
홍 박사의 연구실에 있는 총 N마리의 폰켓몬 중 N/2마리를 가져갈 수 있다.
같은 종류의 폰켓몬은 같은 번호를 가진다.
N마리 폰켓몬 종류 번호가 담긴 배열 nums가 매개변수로 주어진다. → 폰켓몬 종류가 나열된 배열 nums(중복O)
이때, 최대한 다양한 종류의 폰켓몬을 포함하여 N/2마리를 선택하는 방법을 찾고 그때의 폰켓몬 종류 번호 개수를 반환하는 solution 함수를 찾아야 한다.
→ N/2개를 선택할 때 최대한 다양한 번호를 몇 개 선택 가능한지 알아내야 한다.
입출력 예
nums | result |
[3,1,2,3] | 2 |
[3,3,3,2,2,4] | 3 |
[3,3,3,2,2,2] | 2 |
포켓몬 종류, 포켓몬 수를 구별하여 생각하기nums | 중복 제거 | 포켓몬 종류
(pokemon.size) | 데려가는
포켓몬 수 (=N/2) | N/2마리를 선택하는 경우의 수 | result |
[3,1,2,3] | [1, 2, 3] | 3종류 | 2마리 | (1) 1, 2
(2) 1, 3(i)
(3) 1, 3(ii)
(4) 2, 3(i)
(5) 2, 3(ii)
(6) 3(i), 3(ii) | 2종류 |
[3,3,3,2,2,4] | [3, 2, 4] | 3종류 | 3마리 | … | 3종류 |
[3,3,3,2,2,2] | [3, 2] | 2종류 | 3마리 | … | 2종류 |
HashSet
1.
중복을 허용하지 않는다.
2.
저장 순서를 유지하지 않는다.
코드
public int solution(int[] nums) {
Set<Integer> pokemon =new HashSet<>();
//1: 중복 제거
for(int num : nums) {
pokemon.add(num);
}
//2: 가져갈 수 있는 포켓몬의 수
// [3,1,2,3] -> 2
int pick = nums.length/ 2;
//3: pokemon 종류가 가져갈 수 있는 포켓몬 수보다 많으면, pick 리턴
if(pick < pokemon.size()) {
return pick;
}
//4: 가져갈 수 있는 포켓몬 수 = 중복 제거한 포켓몬 종류의 수
int answer = pokemon.size();
return answer;
}
Java
복사
02. 전화번호 목록
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우 false를 반환
그렇지 않으면 true를 반환
입출력 예
phone_book | result |
["119", "97674223", "1195524421"] | false |
["123","456","789"] | true |
["12","123","1235","567","88"] | false |
사용 메소드
•
substring() : 문자열을 잘라 반환하는 메소드
example
•
contains() : Set에 객체가 존재하는지 여부를 반환하는 메소드
example
코드
public boolean solution(String[] phone_book) {
boolean answer = true;
HashSet<String> hashSet = new HashSet<>();
//1: hashSet에 넣어주기
for (String num : phone_book) {
hashSet.add(num);
}
//2: hashSet의 한 번호를 첫 인덱스부터 다음 인덱스, 그 다음 인덱스.. 끝 인덱스까지 잘라서
//hashSet이 동일한 element를 가지고 있는지 확인
for (String num: hashSet) {
for (int i = 1; i < num.length(); i++) {
String prefix = num.substring(0, i);
if(hashSet.contains(prefix)) {
return false;
}
}
}
return answer;
}
Java
복사
