프로그래머스 [120823] 성능 개선

항해99 12기 과정을 진행하면서 같은 반 동료들과 함께 프로그래머스 Lv0단계 문제를 하루에 5~6정도 정해서 풀어보고 함께 코드리뷰하는  알고리즘 릴레이를 진행하고 있다. 그 과정 중 오늘 프로그래머스 120823문제를 풀면서 실행시간이 평소 문제들에서 접할 수 없었다 어마무시한 시간이 나왔으며, 가볍게 풀고 넘어갈 수 있는 문제에서 성능 관련 이슈를 기존에 학습했던 부분들을 리마인드도 하고 한번 간단하게라도 줄여볼 수 있는 방법들을 찾아보면서 해결해보려고  한다.

 

문제정의)

"*"의 높이와 너비를 1이라고 했을 때, "*"을 이용해 직각 이등변 삼각형을 그리려고합니다.
정수 n 이 주어지면 높이와 너비가 n 인 직각 이등변 삼각형을 출력하도록 코드를 작성해보세요.

 

그냥 쉽게 정리하면 표준입력으로 콘솔에서 정수 값(n)을 받아서 1-> n개까지 *을 1씩 늘리면서 라인단위로 찍는 문제이다. 이러한 문제는 보통 반복문 그 중에 중첩 반복문을 배울 때 등장하는 당골 문제이다.  

 

다음으로 해당 문제를 정의하면서 발견한 부분이다. 아래 제한사항이다.

제한사항 : 1 ≤ n ≤ 10

 

입력으로 1->10까지만 가능하다고 한다. 이것을 굳이 적은 이유는 이후에 보게 될 수행시간 때문이다. 즉, 테스트로 입력될 값은 많아야 10이며 10줄의 라인을 출력할 것이다. 

 

아래에서는 실제 프로그래머스에서  동작한 테스트 결과(1<=n<=10)와 인텔리제이에서 수를 확장하여 n = [1000,5000]으로 설정 후 알고리즘에 따른 성능을 체크해보고자 한다.

 

---

방법 1) 간단하게 중첩 반복문으로 처리

// 시간은 단순 해당문제 제약조건을 넘어 더 큰 값을 받을 시 성능을 체크하기 위함
public static void main(String[] args)  {
    Scanner sc  = new Scanner(System.in);
    int n = sc.nextInt();
    long start = System.currentTimeMillis(); // 시작시간
    for(int i = 1; i <= n ;i++){
        for (int j = 1; j <= i ; j++){
            System.out.print("*");
        }
        System.out.println();
    }
	System.out.println(System.currentTimeMillis()-start+"ms"); // 작업 수행 후 총 시간
}

프로그래머스 결과 / n=1000 , n = 5000

문제를 풀 당시에는 이렇게 중첩으로 풀지 않았기에 사실 생각보다 프로그래머스에서 수행시간이 빨라서 당황스러웠다....

 

---

방법 2) 반복문 + String.repeat(n) 활용

public static void main(String[] args)  {
    Scanner sc  = new Scanner(System.in);
    int n = sc.nextInt();
    long start = System.currentTimeMillis();
    for(int i = 1; i <= n ;i++){
        System.out.println("*".repeat(i));
    }
    System.out.println(System.currentTimeMillis()-start+"ms");
}

프로그래머스 결과 / n=1000 , n = 5000

프로그래머스에서 풀 때는 값도 작고 크게 차이는 없는 듯했다. 그러나 인텔리제이에서 풀 때는 엄청나게 시간이 줄어든 것을 확인할 수 있다. 이 부분은 시간 복잡도가 중첩 반복문의 경우는 O(n^2) / 단일반복문의 경우 O(n)이기에  n값이 커짐에 따라 상상도 안되는 차이가 발생하는 것을 가시적으로 확인해 볼 수 있었다.

 

사실상 프로그래머스 결과는 사실상 이 시점부터  큰 의미가 없지 않을까 싶다...

 

---

방법 3) Stringbuilder(StringBuffer) 활용

public static void main(String[] args)  {
    Scanner sc  = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    int n = sc.nextInt();

    long start = System.currentTimeMillis();
    for(int i = 1; i <= n ;i++){
        sb.append("*".repeat(i)+"\n");
    }
    System.out.println(sb.toString());
    System.out.println(System.currentTimeMillis()-start+"ms");
}

프로그래머스 결과 / n=1000 , n = 5000

다음으로는 StringBuilder를 활용해봤다. 해당 방식으로 접근한 이유는 기본적으로 출력을 한다는 것 자체도 사실상은 쓰레드가 동작하면서 화면에 출력하는 일을 하며 그 시간동안에는 다른 작업은 대기상태가 된다. 이러한 부분을 생각해서 반복문을 돌면서 출력을 그때그때 하다보면 전체적으로 프로그램이 모두 수행되기까지 더욱 시간이 걸리는 것이 아닌가? 그럼 바로 출력하지말고 Stringbuilder는 내부적으로 버퍼를 가지고 있어 버퍼에 내용을 저장하고 있다가 추후 toString() 메서드 호출 시 버퍼에 있는 문자열을 반환해준다. 그래서 이 부분을 활용해서 단 한번의 출력시간을 갖게 만들면 더 빠르지 않을까 생각했는데 결과는 오히려 더 시간이 지연되었다. 이 부분에 대해서는 아래경우를 테스트하고 생각을 한번에 정리해야할 듯 하다.

---

방법 4) BufferedWriter활용

try(BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long start = System.currentTimeMillis();
    for(int i = 1  ; i <= n ; i++)
    bw.write("*".repeat(i)+"\n");
        bw.flush();
    System.out.println(System.currentTimeMillis()-start+"ms");
}catch (IOException e){}

프로그래머스 결과 / n=1000 , n = 5000

다음은 i/o에서 등장하는 BufferedWriter를 활용해봤다. 여기서  Buffered~를 사용한 것도 위와같이 출력하기 위해서 버퍼에 한번에 모아두었다가 출력하면 시간을 줄일 수 있겠다는 생각에서 접근해봤다. 그러나 Builder보다는 시간을 줄었으나,  아주 좋은 결과는 얻지 못한 듯한다. 이 부분에 대해서는 기본적으로 콘솔이던 파일이던 어딘가에서 입력을 받고 출력을 하기 위해서는 서로 데이터를  전달하기 위한 Stream이 필요하다. 이 과정에서 Buffered를 이용하면 바로바로 보내는 것이 아니라 데이터를 모아서 한번에 보내기에 사용하지 않을때보다 상대적으로 시간 아낄 수 있다. 예를든다면 "ABCD"라는 문자열을 화면에 출력한다고 할 경우 문자를 하나씩 보내서 찍는다고 생각해보자.. 그럼 'A'보내고 출력되고 다시 'B'를 전송할 시간이 필요하다. 그러나 이를 한번에 모아서 보내면 중간에 전송되는 시간들이 단축될 것이다. 

 

결과적으로 1) 해결방법에 비해서 2)3)4) 모두 굉장히 빠르게 수행되었다. 이것은 사실상 반복문을 줄임으로 이러한 성능을 만들어낸 것이 대부분이다. 나머지 3)4)의 접근방법 같은 경우 실제로 테스트하면서 든 생각으로는 해당문제는 단순 출력만 하면되기에 추가적으로 수행되야 할 작업들이 없다. 그러나 만약 파일에서 읽어와서 출력하는 경우라면 확실히  버퍼가  있는 쪽에서 성능을 기대해볼 수 있지 않을까 생각이든다.  해당 문제에서는 버퍼에 따로 저장을 해야하고 버퍼에 모인 내용을 출력 해야하는 부분들이 있어 사실상 크게 도움이 된 테스트 결과는 없었던 것 같다. 그러나 직접 궁금한 사항을 토대로 직접 시도해 본  부분은 배운 부분을 정리해보고 추후에 적용해보는 부분에서는 충분히 성장하는 밑거름이라  생각이 된다. 추가적으로 4)번 해결방법을 적용할 때 I/O관련하여 생기는 예외처리부분을 처리해보면서 try-with-resource도 리마인트 해 본 계기였다.