[Java] LeetCode(Easy) - 771. Jewels and Stones
문제 풀이
이번 771번 문제는 단순하다. 문제에서 주어지는 문자열의 길이도 50자 이하이기 때문에 굉장히 관대하다.
아이디어 도출
- jewels 문자열을 쪼개어 하나씩 보관한다.
- stones 문자열의 각 문자별로 순회하여 앞서 쪼갠 jewels의 문자가 포함되는지 확인한다.
- jewels에서 쪼갠 문자가 포함될 경우 카운트를 증가시킨다.
이번 문제에서 사용한 자료구조는 ArrayList, HashMap 2가지와 문자열 순회시 일반 for문과 foreach문을 활용하였다.
ArrayList와 for문을 활용한 풀이
코드가 간단하기 때문에 코드를 먼저 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int numJewelsInStones(String jewels, String stones) {
ArrayList<Character> list = new ArrayList<>();
int cnt = 0;
for(int i=0; i<jewels.length(); i++) {
list.add(jewels.charAt(i));
}
for(int i=0; i<stones.length(); i++) {
if(list.contains(stones.charAt(i))) cnt++;
}
return cnt;
}
}
jewels 문자열을 쪼개서 담을 ArrayList를 하나 생성하고 카운트를 셀 cnt 변수를 선언한다.
그리고 jewels 각 문자만큼 순회하면서 ArrayList에 담는다. 그러고 stones의 각 문자만큼 순회하면서 ArrayList에 포함된 문자인지 contains 메소드로 확인하여 카운트를 세면 된다.
foreach문으로 변경
위 코드에서 사용한 for문을 foreach문으로 고쳐보았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int numJewelsInStones(String jewels, String stones) {
ArrayList<Character> list = new ArrayList<>();
char[] jewels_arr = jewels.toCharArray();
char[] stones_arr = stones.toCharArray();
int cnt = 0;
for(char c : jewels_arr) {
list.add(c);
}
for(char c : stones_arr) {
if(list.contains(c)) cnt++;
}
return cnt;
}
}
앞에서 본 코드와 동일한 로직이지만 char 타입 변수로 순회하기 위해 입력 문자열 jewels와 stones를 char형 배열을 만들어 사용한다는 차이점이 있다.
ArrayList가 아닌 HashMap 활용
마지막으로 ArrayList가 아닌 HashMap으로 풀어보았다. 주어지는 문자열의 길이가 길어진다면 HashMap이 더 유리할 수 있기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int numJewelsInStones(String jewels, String stones) {
HashMap<Character, Integer> hm = new HashMap<>();
char[] jewels_arr = jewels.toCharArray();
char[] stones_arr = stones.toCharArray();
int cnt = 0;
for(char c : jewels_arr) {
hm.put(c, 0);
}
for(char c : stones_arr) {
if(hm.containsKey(c)) cnt++;
}
return cnt;
}
}
ArrayList와는 다르게 put 메소드로 HashMap에 jewels의 각 문자를 집어넣고 containsKey 메소드로 HashMap 포함여부를 확인한다.
실행 시간 차이
ArrayList보다는 HashMap이 더 빠를 줄 알았으나 오히려 ArrayList가 근소하지만 더 빠른 시간을 보여주었다.
ArrayList
HashMap
왜 HashMap이 더 느린 시간이 걸렸을까?
이유를 찾아보니, ArrayList의 경우 내부적으로 배열을 사용하고 있기 때문에 contains 메소드는 내부적으로 순차 탐색을 수행한다. 이 때, 이 문제에서 요구하는 문자열 길이가 짧기 때문에 한번에 비교할 수 있는 원소들이 많다. 그래서 일반적으로 원소의 개수가 적을 때는 ArrayList의 contains 메소드가 더 빠를 수 있다고 한다.
반면에, HashMap의 경우 내부적으로 해시 테이블을 사용하고 있고, 해시 테이블은 해시 함수를 이용하여 원소를 저장하고 탐색한다. 이 떄, 문자열 길이가 짧아도 해시 함수를 계산하는 과정이 추가적으로 필요하기 때문에 ArrayList에 비해 성능이 떨어질 수 있다고 한다.
하지만, 이는 일반적인 경우이며 상황에 따라 다를 수 있음을 유의해야 한다. 예를 들어, 원소의 개수가 매우 많고 문자열 길이가 짧은 경우에는 HashMap의 containsKey 메소드가 더 빠를 수 있다.
결국 어떤 자료구조를 선택해야 하는지는 문제의 유형 및 데이터의 특성에 따라 달라지기 때문에, 여러 가지 자료구조 성능에 대해서 어느정도 알고 있어야 한다고 느끼게 되었다.
작성 코드 - ArrayList 및 for문 활용
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int numJewelsInStones(String jewels, String stones) {
ArrayList<Character> list = new ArrayList<>();
int cnt = 0;
for(int i=0; i<jewels.length(); i++) {
list.add(jewels.charAt(i));
}
for(int i=0; i<stones.length(); i++) {
if(list.contains(stones.charAt(i))) cnt++;
}
return cnt;
}
}
작성코드 - ArrayList 및 foreach문 활용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int numJewelsInStones(String jewels, String stones) {
ArrayList<Character> list = new ArrayList<>();
char[] jewels_arr = jewels.toCharArray();
char[] stones_arr = stones.toCharArray();
int cnt = 0;
for(char c : jewels_arr) {
list.add(c);
}
for(char c : stones_arr) {
if(list.contains(c)) cnt++;
}
return cnt;
}
}
작성코드 - HashMap 및 foreach 활용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int numJewelsInStones(String jewels, String stones) {
HashMap<Character, Integer> hm = new HashMap<>();
char[] jewels_arr = jewels.toCharArray();
char[] stones_arr = stones.toCharArray();
int cnt = 0;
for(char c : jewels_arr) {
hm.put(c, 0);
}
for(char c : stones_arr) {
if(hm.containsKey(c)) cnt++;
}
return cnt;
}
}
회고
- ArrayList와 HashMap 자료구조의 성능에 대해서 공부할 수 있었고, for문과 foreach문을 사용하는 이유를 알 수 있었다.
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.