TIL ... 2주차 day 9 알고리즘 시험 및Comparable과 Comparator - 22.05.19
오늘은 알고리즘 시험을 보며 풀었던 문제를 리뷰하며 찾아봤던 내용들을 정리하려한다.
알고리즘 시험문제의 경우 프로그래머스의 문자열 내 마음대로 정렬하기 문제가 응용되어 출제되었다.
문자열 배열이 함수의 파라미터로 주어지고 문자열 배열안에 있는 문자열 중 중복된 문자열은 제외한 후 프로그래머스의 문제와 같은 조건으로 처리하라는 문제였다.
제출한 코드
class Solution {
public String[] solution(String[] arr, int n) {
Map<String, Integer> tmp = new HashMap<>();
for (String s : arr) {
tmp.put(s, 0);
}
tmp.forEach((strKey, cnt) -> {
for (String s : arr) {
if (s.equals(strKey)) tmp.put(strKey, tmp.get(strKey) + 1);
}
});
List<String> removeArr = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(tmp.get(arr[i]) == 1) removeArr.add(arr[i]);
}
String[] answer = removeArr.toArray(new String[removeArr.size()]);
Arrays.sort(arr, (o1, o2) -> {
if (o1.charAt(n) > o2.charAt(n)) return 1;
else if(o1.charAt(n) < o2.charAt(n)) return -1;
return o1.compareTo(o2);
});
return answer;
}
}제출할 때 결과를 도출해 내는데 시간이 좀 걸리는게 이상하다고 생각했지만 예시로 주어진 답안을 모두 만족해 제출은 일단 하였다.
계속 HashMap을 사용하였는데도 속도가 느린게 왜 그런지 궁금하여 코드를 수정해 보았고 다른 방법의 풀이와 속도를 비교해 보았다.
위의 코드에서 HashMap에 key, value를 지정해주는 방식에서 for문이 한번더 사용되는 것을 바꿔줄 필요가 있었다.
- 접근방법
1) 전달받은 파라미터의 문자열 배열의 문자열을 HashMap의 key로 설정하여 중복을 제거하였고 조건문을 통해 중복의 경우 중복된 key의 value 값을 증가시켜 어떤 문자열이 중복이 되었는지 확인하였다.
2) 새로운 리스트를 생성하여 HashMap 에서 value값이 1인 key값을 새로 생성한 리스트에 저장하여 comparator의 compara()함수의 람다식을 재정의하여 n번째의 character 를 비교하여 정렬하였다.
- 변경 전
Map<String, Integer> tmp = new HashMap<>();
for (String s : arr) {
tmp.put(s, 0);
}
tmp.forEach((strKey, cnt) -> {
for (String s : arr) {
if (s.equals(strKey)) tmp.put(strKey, tmp.get(strKey) + 1);
}
});- 변경 후
Map<String, Integer> tmp = new HashMap<>();
for (String s : arr) {
if(tmp.isEmpty()) tmp.put(s, 1);
else if(tmp.get(s) == null) tmp.put(s, 1);
else tmp.put(s, tmp.get(s) + 1);
}- 전체 코드
class Solution {
public String[] solution(String[] arr, int n) {
Map<String, Integer> tmp = new HashMap<>();
for (String s : arr) {
if(tmp.isEmpty()) tmp.put(s, 1);
else if(tmp.get(s) == null) tmp.put(s, 1);
else tmp.put(s, tmp.get(s) + 1);
}
List<String> removeArr = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(tmp.get(arr[i]) == 1) removeArr.add(arr[i]);
}
String[] answer = removeArr.toArray(new String[removeArr.size()]);
Arrays.sort(arr, (o1, o2) -> {
if (o1.charAt(n) > o2.charAt(n)) return 1;
else if(o1.charAt(n) < o2.charAt(n)) return -1;
return o1.compareTo(o2);
});
return answer;
}
}- 접근방법
1) 처음의 접근 방법과 달리 전달받은 문자열 배열을 조건에 맞게 정렬을 먼저 하였다.
2) 조건에 맞게 정렬된 배열을 for문을 통해 i, i+1 번째의 문자열을 비교하여 같을때 둘다 지워주는 방식으로 중복된 문자열을 처리하였다.
*( 이 방식을 진행할 때 Arrays.asList 관련 에러가 발생 하였는데 이 부분은 이 다음에 기술하겠습니다. )
class SolutionTest {
public String[] solution(String[] arr, int n) {
Arrays.sort(arr, (o1, o2) -> {
if (o1.charAt(n) > o2.charAt(n)) return 1;
else if(o1.charAt(n) < o2.charAt(n)) return -1;
return o1.compareTo(o2);
});
/* Arrays.asList(arr)로 생성한 리스트는 고정되 element를 가지므로 add, remove 와 같은 리스트의 원소를 추가, 제거 할 수 없다.
에러: java.lang.UnsupportedOperationException */
List<String> tmp = new ArrayList<>(Arrays.asList(arr));
for (int i = 0; i < arr.length - 1; i++) {
if(arr[i].equals(arr[i+1])){
tmp.remove(i); // remove시 list의 index가 하나가 줄어들기 때문에
tmp.remove(i);
}
}
return tmp.toArray(new String[tmp.size()]);
}
}위의 두가지 방식에서 문자열을 정렬하는 방식은 같은 방식의 논리구조를 사용하여 HashMap의 속도를 상대적으로 비교 할 수 있지 않을까 하여 test 해보았습니다.
TEST
SolutionTest methodTest = new SolutionTest();
Solution method2 = new Solution();
String[] arr = {"coke", "water", "glass", "dog", "dog", "yogurt", "vitamin"};
int n = 2;
System.out.println("정렬을 먼저한 코드");
long start = System.currentTimeMillis();
System.out.println(Arrays.toString(methodTest.solution(arr, n)));
long end = System.currentTimeMillis();
System.out.println("SDB에서 노드생성까지의 실행시간 : " + (end - start) + "ms");
System.out.println("------------------------------");
System.out.println("HashMap 사용 코드");
start = System.currentTimeMillis();
System.out.println(Arrays.toString(method2.solution(arr, n)));
end = System.currentTimeMillis();
System.out.println("SDB에서 노드생성까지의 실행시간 : " + (end - start) + "ms"); // 초단위로 시간 측정
위 테스트 코드를 진행 하였을때 대략적으로 1번째 방법인 HashMap 사용 결과의 경우 약 1ms 정도 실행시간이 걸렸으며, 2번재 방법은 대략 10ms ~ 22ms의 실행 시간을 얻을 수 있었다.
결론 : 중복 처리가 필요한 경우 HashMap 사용이 속도면에서 유리하다고 생각된다.
아직 많이 배워야 합니다. 혹시나 틀린 부분이 있거나 잘못된 개념을 가지고 글을 작성한게 보이신다면 댓글로 지적해 주시거나 친절하게 알려주시면 감사하겠습니다.
위의 코드를 작성하면서 정렬하는 부분에서 comparable 과 comparator에 대해 공부하게 되었다.
일단 이해한 부분을 최대한 작성하고 참고한 사이트를 기재하겠습니다.
Comparable과 Comparator 모두 Interface 라는 점 Comparable 또는 Comparator 를 사용하기 위해서는 인터페이스 내에 선언된 메소드를 반드시 구현해야한다는 점이다.
Comaparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언되어있어, 사용하기 위해서는 compareTo 메소드를 재정의 오버라이드 해줘야한다.
Comparator를 보면 선언 된 메소드가 많아서 어질할 수 있겠지만, 구현해야하는 메소드는 compare(T o1, T o2) 다.
위 코드에선 문자열 배열의 문자열의 n번째의 character를 비교하여 정렬해야 하는 조건이 있으므로 새로운 조건을 추가하여 익명인터페이스 Comparator를 구현한 Class내 compare()메서드를 오버라이드하여 sort method 호출 시 구현한 Comparator 클래스를 명시하였다.
이때
Arrays.sort(arr, new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
~~~~~~~~~~
~~~~~~~~~~
~~~~~~~~~~
}
}위와 같이 정의 할 수 있으며 이를 람다식으로 인스턴스 생성를 생략하고 compare함수를 재정의하여 사용하였다.
참고 사이트 : https://st-lab.tistory.com/243, https://ifuwanna.tistory.com/232
* 배열을 리스트로 변환하면서 발생한 이슈
List<String> tmp = Arrays.asList(arr);배열이 존재하는 경우 위와같이 배열을 리스트로 변환해 주었다. 그 후 리스트에 element를 삭제하려고 보니 에러가 발생하며 실행이 종료해 버렸다. 에러메시지를 확인해 보니...
java.lang.UnsupportedOperationException 구글링을 통해 확인해본 결과 배열의 크기만큼 리스트가 생성되어 add, remove를 할 수 없다는 내용이였다. 따라서
List<String> tmp = new ArrayList<>(Arrays.asList(arr));이와 같이 새로운 리스트 인스턴스를 만들어 에러를 해결하였다.
