알고리즘 문제 풀이 47번_봉우리 찾기

 

목차

---

• 문항 분석

• Code

• 결과 및 분석

---

문항 분석

2차원 배열이 입력으로 들어왔을 때, 해당 Index의 부분이 해당 배열의 값을 둘러싼 다른 값보다 낮은 값을 가지는지 높은 값을 가지는지를 비교해 봉우리 여부를 판단하고, 이를 갯수로 추려내는 문항.

 

풀이 방향 1. 2차원 배열 생성 -> 외부에 0으로 채워진 배열을 추가로 형성해 외부 영역에 대한 추가 예외처리를 피함.

 

0 0 0 0 0 0 0

0 5 3  7  2 3 0

0 3 7  1  6  1 0

0 7 2  5  3 4 0

0 4 3  6  4 1 0

0 8 7  3  5 2 0

0 0 0 0 0 0 0

-> index 중 이전 탐색에서 이미 더이상 조회가 필요없는 부분을 건너뛸 필요성 있음.

같은 크기의 2차원 배열 선언 후 flag 값 사용 가능할 듯.

Code

//
//  47_봉우리.cpp
//  Algorithm
//
//  Created by WANKI KIM on 2021/01/13.
//

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int **arr = new int*[n+2];
    for(int i = 0; i <n+2; i++){
        arr[i] = new int[n+2]{0,};
    }
    
    for(int i = 1; i < n+1; i++){
        for(int j = 1; j< n+1;j++){
            cin >> arr[i][j];
        }
    }
    
    int result = 0;
    for(int i = 1; i < n+1; i++){
        for(int j = 1; j< n+1;j++){

            if(arr[i][j]>arr[i-1][j] && arr[i][j]>arr[i+1][j] && arr[i][j]>arr[i][j-1] && arr[i][j]>arr[i][j+1]){
                result++;
            }
        }
    }

    cout << result << endl;
    
    
    return 0;
}

결과 및 분석

 

* C++ 2차원 동적 배열 생성 방법.

//2중 포인터로 포인터를 값으로 갖는 배열 선언.
    int **arr = new int*[n+2];
    //2중 포인터 내 각 주소값이 해당 크기의 공간을 갖도록 할당.
    for(int i = 0; i <n+2; i++){
        arr[i] = new int[n+2]{0,};
    }

항상 모두 사용 후, 동적할당된 메모리에 대한 반환이 필요하다.

delete[] 연산 사용 필요. -> 할당의 역순서로 진행.

 

해당 글은 'it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코테 대비' 강의를 수강하며, 개인적으로 정리하기 위해 업로드하였습니다.

강좌 : https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#