코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
웅덩이
앞서 공부한 시뮬레이션 알고리즘을 사용해 웅덩이 문제를 풀어보겠다.
문제
매개변수 nums에 n행 n열의 이차원 배열에 격자판 정보가 주어집니다.
각 격자에는 그 지역의 높이가 쓰여있습니다. 각 지역은 상하좌우 인접한 지역의 숫자가 모두 자신보다 클 경우 이 지역을 웅덩이 지역이라고 합니다.
격자의 가장자리는 1000으로 초기화 되었다고 가정한다.
만약 5*5 이차원 배열의 격자판 정보다 아래와 같다면 총 웅덩이의 수는 5개입니다.
주어진 격자에 웅덩이가 몇 개 있는지 찾아 그 개수를 반환하는 프로그램을 작성하세요.
입출력 예
| 입력(nums) | 출력(answer) |
|---|---|
| [[10, 20, 50, 30, 20], [20, 30, 50, 70, 90], [10, 15, 25, 80, 35], [25, 35, 40, 55, 80], [30, 20, 35, 40, 90]] | 5 |
| [[80, 25, 10, 65, 100], [20, 10, 32, 70, 33], [45, 10, 88, 9, 90], [10, 35, 10, 55, 66], [10, 84, 65, 88, 99]] | 4 |
| [[33, 22, 55, 65, 55], [55, 88, 99, 12, 19], [18, 33, 25, 57, 77], [46, 78, 54, 55, 99], [33, 25, 47, 85, 17]] | 6 |
제한사항
- 3 <= n <= 10
- 배열 nums의 원소는 자연수입니다. 1 <= nums[i][j] <= 100
작성한 코드
def solution(nums):
answer = 0
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
# 행의 개수
n = len(nums)
# 열의 개수
# m = len(nums[0])
for i in range(n):
for j in range(n):
flag = True
for k in range(4):
nr = i + dr[k]
nc = j + dc[k]
if nr >= 0 and nr < n and nc >= 0 and nc < n:
if nums[i][j] >= nums[nr][nc]:
flag = False
if flag:
answer += 1
return answer
# TestCase
print(solution([[10, 20, 50, 30, 20], [20, 30, 50, 70, 90], [10, 15, 25, 80, 35], [25, 35, 40, 55, 80], [30, 20, 35, 40, 90]]))
print(solution([[80, 25, 10, 65, 100], [20, 10, 32, 70, 33], [45, 10, 88, 9, 90], [10, 35, 10, 55, 66], [10, 84, 65, 88, 99]]))
print(solution([[33, 22, 55, 65, 55], [55, 88, 99, 12, 19], [18, 33, 25, 57, 77], [46, 78, 54, 55, 99], [33, 25, 47, 85, 17]]))풀이
코드 내용은 시뮬레이션 알고리즘 게시물에서 풀이한 simulation 함수와 거의 동일하다.
- 방향 배열
dr,dc를 12시부터 시계방향으로 설정 - 현재 위치의 값
i,j이 상하좌우 좌표들의 값nr,nc보다 하나라도 크거나 같으면 flag = False로 설정 flag== True라면answer에 웅덩이 한 개를 추가board의 모든 원소를 다 돌면 웅덩이 개수return answer
끄적끄적