24년 11월 이전/레거시-알고리즘(3)

[프로그래머스 1단계] 알고리즘 16. 삼각형 출력하기

Gurumee 2018. 3. 30. 12:43
반응형

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)


알고리즘 16. 삼각형 출력하기


printTriangle 메소드는 양의 정수 num을 매개변수로 입력받습니다. 다음을 참고해 *(별)로 높이가 num인 삼각형을 문자열로 리턴하는 printTriangle 메소드를 완성하세요 printTriangle이 return하는 String은 개행문자('\n')로 끝나야 합니다.

높이가 3일때

*
**
***

높이가 5일때

*
**
***
****
*****


function printTriangle(num) {
var result = ''
// 함수를 완성하세요
return result
}
// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log( printTriangle(3) );


풀이 :  

이 문제의 풀이 역시 간단하다. 그래서 반복문을 쓰는 방법과 재귀를 쓰는 방법 그리고 역 삼각형 출력하기를 해 볼 생각이다. 먼저 반복문은 다음과 같이 사용할 수 있다.


function printTriangle(num) {
var result = ''
for (var i =0; i<num; i++)
result += '*'.repeat(i+1) + '\n'

return result
}


자바스크립트에서 '*'.repeat(n) 함수는 주어진 문자열 '*'을 n번 반복하는 문자열을 반환해준다.  반복문 안에 반복문을 넣는 방법도 있지만 좀 더 자바스크립트 내부 기능을 이용하고 싶어서 이러한 코드를 작성하였다. 이제 재귀 호출문으로 바꿔보자. 코드는 다음과 같다.


function printTriangle(num) {
return (num > 0) ? printTriangle(num -1) + '*'.repeat(num) + '\n' : ''
}


재귀 호출은 차곡 차곡 함수 호출 스택에 쌓인 뒤 반환한다는 것을 이해하자. 가령 num=3이라 치면 조건문 num > 0 이 참이니까 다시 printTriangle(3-1)을 먼저 호출하게 된다. 따라서 


printTriangle(3) -> printTriangle(2) -> printTriangle(1) -> printTriangle(0)


먼저 호출되어 스택에 쌓이게 된다. 그렇다면 num = 0일 때는 어떻게 될까? 


printTriangle(0) = ''


왜냐하면 조건문 num > 0 을 충족시키지 못하기 때문에 바로 ''를 반환한다.  그 후 호출 스택에 쌓인 순서대로 다음과 같이 문자열을 반환한다.


printTriangle(1) = printTriangle(0) + '*'.repeat(1) + '\n' 

  = '' + '*\n'

printTriangel(2) = printTriangle(1) + '*'.repeat(2) + '\n' 

       = '*\n'  + '**\n'

printTriangel(3) = printTriangle(2) + '*'.repeat(3) + '\n' 

  = '*\n**\n' + '***\n'


이렇게 차례대로 반환하게 된다.  따라서 위의 반복문처럼 문자열이 쌓이게 된다. 여기까지 이해됐다면 역순으로 출력해보자. 역순은 재귀호출의 순서를 바꾸면 쉽게 출력할 수 있다. 코드는 다음과 같다.


function printReversedTriangle(num) {
return (num > 0) ? '*'.repeat(num) + '\n' + printReversedTriangle(num-1) : ''
}


'*'.repeat(n) + '\n' 과 재귀 호출 부(print...(n-1))의 순서만 바꾸는 것으로 역순으로 출력이 가능하다. 이번에는 어떻게 호출 스택이 쌓이는지 확인해보자. 역시 예는 nun =3이다. 여기서는 조건문 (n > 0)이 참이기 때문에 먼저 '*'.repeat(3) + '\n'으로 ***을 만든다 그 후 printReversedTriangle(3-1) 호출한다. 이렇게 문자열이 쌓이고 호출 스택을 쌓아간다. 상황은 이렇게 된다.


printReversedTriangle(3) = '***\n'+ printReversedTriangle(2) -> 

printReversedTriangle(2) = '**\n' + printReversedTriangle(1) -> 

printReversedTriangle(1) = '*\n'  + printReversedTriangle(0)


num=0일 때 조건문 num >0 을 충족시키지 못하여 ''를 반환하니까 이제 호출 스택에 따라서 차례대로 반환하게 된다.


printReversedTriangle(1) = '*\n'     + printReversedTriangle(0) 

= '*\n' + ''

printReversedTriangle(2) = '**\n'    + printReversedTriangle(1) 

= '**\n' + '*\n'

printReversedTriangle(3) = '***\n'   + printReversedTriangle(2) 

= '***\n' + '**\n*\n'


따라서 역 삼각형을 출력하게 된다.

728x90
반응형