코딩 테스트 연습 - Pascal's Triangle2

다용도리모콘·2020년 9월 17일
0

CodingTest

목록 보기
21/34

01. 이해

파스칼 삼각형에서 주어진 숫자의 행을 반환 하라.

02. 계획

행이 증가할 수록 행의 길이는 1씩 증가하고 행의 첫번째와 마지막 숫자는 1이다.
첫번째와 마지막을 제외한 인덱스 n에 위치한 숫자는 이전 행의 n-1,n 인덱스의 합이다.
첫번째 행은 이전 행이 없으므로 예외처리 해야 함.

03. 실행

fun getRow(rowIndex: Int): List<Int> {

    val initList = intArrayOf(1)

    if (rowIndex == 0) {
        return initList.toList()
    }

    var preRowList = initList

    for (i in 1 until rowIndex + 1) {
        val row = ArrayList<Int>()
        for (j in 0 until ((i/2) + 1)) {
            if (j == 0 || j == i) {
                row.add(1)
            } else {
                row.add(preRowList[j - 1] + preRowList[j])
            }
        }

        if (i.rem(2) != 0) {
            row.addAll(row.reversed())
        } else {
            row.addAll(row.subList(0, row.size -1).reversed())
        }
        preRowList = row.toIntArray()
    }

    return preRowList.toList()
}

04. 회고

Pascal's Triangle과 로직은 동힐 하기 때문에 좀 더 개선할 방법을 생각해 봤다.
행을 기준으로 볼 때 왼쪽의 절반만 구하고 오른쪽은 복사하는 로직을 사용할 때 절반 크기의 정수 값을 구하기 위해 round를 사용했는데 쓰지 않아도 되는 것이었다.
정수형의 나눗셈은 자동으로 반올림이 되는 듯 하다.

0개의 댓글