11일차 리뷰

2019/02/12 - [프로그래밍/알고리즘] - 10일차 리뷰

흠... 앞에 정렬하는건 개념적인게 필요했었는데 뒷부분은 딱히 어려웠던게 없었다.

그나마 좀 자바에서 정리할만한 내용만 정리해본다.

step9 정렬해보기

---

2108번

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

(첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.)

내 풀이 : https://github.com/gnidoc327/one-day-one-problem/commit/31898e39fe9cd77f894079207b35ed6a082fedf3

문제는 어렵지 않았다.

단지 내가 테스트 코드를 어떻게 구성했는지를 정리하자면

TDD를 공부했을때 삼각측량에 대해 배웠던건 활용했다.

삼각측량

일단 삼각측량이란 원래는 수평을 계산하기 위해서 사용하는 방식인데

TDD에서는 약간 귀납적으로 테스트를 증명하기 위해서 사용한다.

예를 들어서 a + b 가 맞는지를 증명할때 보통은 귀납적인 방식으로

0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 2, 1 + 0 = 1 정도만 테스트해도 될 것이다.

왜냐하면 0 + 1이되면 0 + 2도 되고 순서가 바뀌어도 되고 1 + 1이 되면 2 + 2도 될테니깐

그럼 모든 숫자에 대해서 a + b가 맞다는걸 증명할 수 있는 것 아니겠는가!

이렇게 TDD에서는 삼각측량 방식으로 작은 유닛(단위)마다 이런 귀납적인 테스트를 한다.

그래서 나는?

테스트케이스인 코드부터 보여주면 아래와같이 5개로 테스트했다.

(검사할때 assert도 써서 검사하면 좋지만 아직은 그럴만한 문제가 없어서 일단 테스트했다.)

// test code
int[] arr = {1, 3, 8, -2, 2};
int[] arr = {4000};
int[] arr = {-1, -2, -3, -1, -2};
int[] arr = new int[500000];
for (int i = 0; i < 500000; i++) {
    arr[i] = i % 4000;
}

1,2,3번은 문제 예시고

4번은 계산 시간이나 스택오버플로우 여부를 확인하기 위해서 최대로 입력값을 넣은 것이다.

원래라면 절대값의 최소값인 {0}과 정수형 배열인 {1,2,3} 등 다양한 케이스를 넣어야하지만

이미 기본 예시로도 충분한 테스트 케이스를 구성하고 있고

입력값의 최소는 사실 -4000이고 정수형 배열은 아래에 최대 입력에서 테스트를 하기 때문에 중복되어 제거했다.

보통 일할때는

일할때는 정상/비정상 범위를 모두 확인한다.

위의 예제라면 -4001, 4001, 4000, 0, -4000 등을 포함해서 테스트를 했을 것이다.

왜냐면 비정상 범위도 확인을 해봐야하기 때문이다.

(문제에서 안한 이유는 알고리즘 사이트에서 굳이 4001, -4001 값을 사용하지 않을 것 써있기 때문에 테스트하지 않았다)

(대표적인 예로 API에서 파라미터로 null이나 space만 들어오는 경우도 은근 많다. 이런 것도 테스트해야된다.)

하지만 입력수에 대해서는 500001개를 테스트하진 않을 것 같다. 

이건 보통 알고리즘 문제에서만 채점을 위해서 쓰는 limit 이라서 고려하지 않을 것이다.

---

1181번

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

string 배열 정렬을 오버라이딩이 필요한 부분이라서 난 쉽게 풀려고 ArrayList를 사용했다.

ArrayList에서 sort함수는 오버라이딩을 위한 Comparator 선언이 필요하기 때문이다.

주 언어가 java가 아니다보니 딱 생각나는게 이거라서 임시 객체를 사용해서 풀었다.

arrayList.sort(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        if (o1.length() != o2.length()) {
            return o1.length() - o2.length();
        }
 
        return o1.compareTo(o2);
    }
});

사실 임시 객체 쓰는게 사실 되게 안좋은 습관인데 알고리즘 문제라서 그냥 사용했다.

개선하려면 java 8부터 람다가 지원되서 임시객체를 쓰지 않고 이렇게 바꿀 수 있다.

arrayList.sort((o1, o2) -> {
    if (o1.length() != o2.length()) {
        return o1.length() - o2.length();
    }
 
    return o1.compareTo(o2);
});

자바에서 gc 때문에 잘쓰지않는 방식이 임시객체 생성이다.

ArrayList도 clear 함수 대신 객체를 새로 생성해서 사용하는게 더 빠른데 clear를 쓰는 이유도 이러하다.

임시객체도 결국 객체(인스턴스)이기 때문에 gc에서 지워야하는데

문제는 만약에 내가 푼 solve라는 함수가 100번 불리면 임시객체도 100개가 생성된다는 것이다.

그렇다면 저 한번쓰고 버려질 임시객체는 gc에서 지워져야되는데 지워지기 전까지

불필요하게 메모리에 떠있다는 것이다.

메모리가 부족하면 gc가 알아서 동작하는데 이때 gc를 동작시키기 위해서 프로세스가 모두 멈추게된다.

(유저 입장에서는 렉이 걸린 것 같겠지) 

그러니 gc가 동작하지 않도록 메모리를 효율적으로 사용하려면 임시객체 사용은 최대한 피해야한다.

비슷한 메모리 최적화 문제(string)

java에서 string 처리할때도 string, stringBuilder, stringBuffer 3가지 방식이 존재하는 것도 그러하다.

string은 immutable 불변의 객체라서 "1" + "2" + "3"를 하면 new String이 5번 호출된다.

("1", "2", "3" 각 1번씩에 +하면서 생성되는 "12", "123" 2번 = 총 5번)

그래서 replace, append을 할거라면 꼭 stringBuilder나 stringBuffer를 사용해야된다.

면접때 java string 관련해서 물어보면 대부분 저 질문이더라...

근데 stringBuffer는 멀티스레딩을 해봤는지를 물어보는 걸텐데 보통 학생들이 이런거 따로 공부 안하면 모르지 않나?

결론

아무튼 문제를 푸는거에서 끝나지 않고 여기저기서 배운 상식을 엮어서 푼다는건 쉽지 않은 것 같다.

오늘 3문제를 풀었는데 문제 자체는 딱히 어려운게 없어서 조금 아쉽긴 하다.

오늘은 약속도 없으니 다른 것도 공부해봐야겠다.