오늘은 알고리즘 시험을 보며 풀었던 문제를 리뷰하며 찾아봤던 내용들을 정리하려한다.
알고리즘 시험문제의 경우 프로그래머스의 문자열 내 마음대로 정렬하기 문제가 응용되어 출제되었다.
문자열 배열이 함수의 파라미터로 주어지고 문자열 배열안에 있는 문자열 중 중복된 문자열은 제외한 후 프로그래머스의 문제와 같은 조건으로 처리하라는 문제였다.
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문이 한번더 사용되는 것을 바꿔줄 필요가 있었다.
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;
}
}
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 해보았습니다.
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);
java.lang.UnsupportedOperationException
구글링을 통해 확인해본 결과 배열의 크기만큼 리스트가 생성되어 add, remove를 할 수 없다는 내용이였다. 따라서
List<String> tmp = new ArrayList<>(Arrays.asList(arr));
이와 같이 새로운 리스트 인스턴스를 만들어 에러를 해결하였다.