LIS self review

[dakyommii]

LIS self review

1. 해결 시도 과정

입력한 수열을 배열로 입력받아 배열 크기, 배열, 탐색 시작 인덱스를 순증가 수열을 찾는 메소드로 전달합니다.
수열을 찾는 메소드에서는 앞에 있는 숫자와 현재 탐색위치에 있는 숫자를 비교해 순증가 부분을 찾고 순증가가 맞으면 순증가 수열 길이와 탐색 인덱스를 증가해줍니다. 그리고 재귀함수를 통해 이어서 다음 위치에서도 계속해서 순증가가 맞는지 확인합니다. 순증가가 아닌 위치가 나타나면 이전까지의 순증가 부분의 길이를 저장하고 수열 길이를 초기화해 다음 위치부터 또다른 순증가 수열을 탐색하도록 조정합니다.
수열을 모두 돌면 저장된 순열 길이 중에 가장 큰 값을 출력합니다.

2. 아이디어

수열을 돌면서 순증가 부분을 찾습니다. 하나의 순증가 수열을 찾을 때마다 수열 길이를 저장해둡니다. 다음 위치로 넘어가서 이어서 탐색을 하려면 재귀호출을 통해 이어서 수열 끝까지 탐색합니다.

3. 코드 설명

int len = 0;    //순증가 수열 길이

//순증가 수열 길이 저장 배열
int totalCnt[500];
int flag = 0;

순증가 수열 찾기 메소드 -> 수열 저장한 배열, 배열 크기, 탐색 시작 인덱스 전달받기

int sol(int n, int c[], int idx) {

    //마지막 인덱스일 경우
    if (idx == n) {
        totalCnt[flag] = len;
        int max = 0;
        for (int i = 0; i < flag + 1; i++) {
            if(totalCnt[i] > max) max = totalCnt[i];
        }
        return max;
    }

수열 끝까지 돌면 최대값 return

    
    //시작일 경우 or 순증가
    if (idx == 0 || c[idx] > c[idx - 1]) {
        len++;
        idx++;
        sol(n, c, idx);
    }
    else if(c[idx] < c[idx - 1]) { //순증가 아님->len 초기화
        idx++;
        flag++;
        totalCnt[flag] = len;
        len = 1;
        sol(n, c, idx);
    }

순증가이면 순증가 길이, 인덱스 조정해주고 다음 탐색 위치로 가지만 순증가가 아닐 경우 이전까지의 순열 길이 저장하고 인덱스 조정하고 길이 초기화해 다음 탐색 위치로 갑니다.

     
    return len;
}

int main() {
    //입력
    int C, N;
    //테스트 케이스
    cin >> C;
    
    for (int i = 0; i < C; i++) {
        //수열에 포함된 원소 수 N
        cin >> N;
        
        //N개 정수 입력
        int *arr = new int[N];
        for (int j = 0; j < N; j++) {
            cin >> arr[j];
        }
        
        //solution
        int result = 0;
        result = sol(N, arr, 0); //배열 크기, 배열, 시작 index 전달
        
        //출력
        cout << result << endl;
    }

}

4. 막힌 점 및 개선 사항

재귀를 사용하는 부분에서 꼬인 부분이 있어서 순열 찾는 메소드 부분을 수정해야합니다. 메소드 부분에서 루프를 최소화하고 최대한 재귀를 활용해서 다시 풀어보면 RTE를 해결할 수 있을 것 같습니다. 아이디어는 괜찮았는데 구현부분에서 잘못했습니다.