세무민의 알고가자 : [HackerRank] 2D Array - DS 문제 풀기

기존에 세무민의 코딩일기에 알고리즘을 작성했는데 

오늘 블로그 스킨부터 조금 변경하다보니 따로 분리시켰고 

그래서 명칭을 조금 변경해봤다.

세무민의 코딩일기(알고리즘) -> 세무민의 알고가자

이유는 추후에 쉽게 관리하고 싶은 마음에 ㅎㅎ

알고가자 -> 알고리즘 가자!라는 간단한 의미로 시작했다 ㅎ

무튼 오늘 풀어볼 문제는 2D Array!

---

문제

---

문제 예시

---

입력 조건 및 출력 조건

---

Sample 입출력

---

문제 요약 및 설명

우선 영어 문제라는 점에서 해석이 중요하다.

hourglass : 모래시계 

위의 단어가 포인트인데 

결론적으로 2D 배열을 모래시개값을 합했을 때 가장 큰 결과를 가진 모래시계 값을 출력하면 됩니다. 

그림으로 표현해봤는데 모래시계 모양으로 i칸씩 증가하면 옆으로 옮기면서 계산할 수 있도록 구현해주면 됩니다. 

아래로도 계속 확인해줘야겠죠?

결론적으로는 2중 포문을 사용하면 됩니다. 

2중 포문말고 다른 방법도 많지만 가장 기초적인 방법입니다.

단 시간복잡도가 2중포문이면 N^2만큼의 시간복잡도가 걸리겠죠?

추후에는 다른 코드로 구성해보는걸 추천합니다.

---

코드

def hourglassSum(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i][j] != 0:
                checkList[i][j] = True
            
    result = -54
    maxSize = 0
    for i in range(len(arr) - 2):
        for j in range(len(arr) - 2):
            maxSize = (arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] +
            arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2])
            if maxSize >= result:
               result = maxSize
            
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr = []

    for _ in range(6):
        arr.append(list(map(int, input().rstrip().split())))

    result = hourglassSum(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

2중 포문을 돌리면서 모래시계 모양에 값을 더하여 MaxSize를 만들어 준 후 

MaxSize가 기존 result값보다 가장 크다면 result에는 MaxSize를 넣어주면 끝입니다. 

여기서 result를 -54로 고정한 이유는 -9가 나오는 경우의 최대값이 

-54이기 때문에 초기값으로 잡아놓고 해당 값보다 큰값이 있으면 변경해주는 마치 탐색하는 방법처럼 구현했습니다.

무튼 성공!

---

오랜만에 HackerRank 문제를 보니 새롭네요 ㅋㅋㅋㅋㅋㅋㅋㅋ

HackerRank 문제가 생각보다 많이 어려운편이라..

무튼 다음에는 더 좋은 포스팅으로 찾아오겠습니다.