[Python/DailyAlgo] 69. 이차원 배열에서 특정 구간 행순회

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

 이차원리스트

https://dailyalgo.kr/ko/problems/69

 

입력 : N x M 자연수로 이루어진 행렬 numbers

그리고 행순회할 구간의 시작 및 끝 인덱스를 나타내는 리스트 start, end

출력 : 행순회한 모든 원소들의 합

테스트케이스 번호	numbers				start	   end	 return
	1		[[1,2,3],[4,5,6],[7,8,9]]	[1,1]	[2,0]	18
	2		[[10,20],[30,40]]		[0,0]	[1,1]	100
	3		[[5]]				[0,0]	[0,0]	5

---

1차 풀이(성공) - C스러운 풀이

# 1차 풀이(성공)
def solution(numbers, start, end):
    N = len(numbers)
    M = len(numbers[0])
    # N x M matrix

    total = 0

    if end[0] - start[0]  == 0:
        for j in range(start[1], end[1] + 1):
            total += numbers[start[0]][j] 
        return total
        # 한 줄이면 그냥 바로 끝냄
    
    for j in range(start[1], M):
        total += numbers[start[0]][j] 
        # 시작 줄 더함
    
    for j in range(0, end[1] + 1):
        total += numbers[end[0]][j]
        # 마지막 줄 더함
    
    # 나중에 안 사실 -> 이거 사실 필요없는 조건문이었음. 통째로 빼도 됨.
    if end[0] - start[0]  == 1:
        return total
        # 두 줄이면 시작 줄, 마지막 줄만 더해서 끝냄
    
    for i in range(start[0] + 1, end[0]):
        for j in range(M):
            total += numbers[i][j]

    return total
    # 세 줄 이상이면, 그 사이 줄들도 더해서 끝냄

# 입력 : N x M 자연수로 이루어진 행렬 numbers
# 그리고 행순회할 구간의 시작 및 끝 인덱스를 나타내는 리스트 start, end
# 출력 : 행순회한 모든 원소들의 합

기본 아이디어는, 행 순회할 행들을 세 분류로 나눈다.

1. 시작 행
2. 끝 행
3. 그 사이 행

그리고, 행 순회할 범위는 세 가지 경우의 수가 가능하다.

1. 시작과 끝 행이 같은 행인 경우
2. 끝 행이 시작 행 바로 다음 행일 경우
3. 시작 행과 끝 행 사이에 행이 하나 이상 있을 경우

이렇게 세 가지 경우의 수에 대해 각각 조건문 if로 분기하여 return을 먹여주면 된다.

2차 풀이 - 1차 풀이를 최적화함, 파이써닉한 풀이

# 2차 풀이 - 1차 풀이를 최적화함
def solution(numbers, start, end):
    # 시작 행과 끝 행이 같다면
    if start[0] == end[0]:  
	      # 밑에 이거 리스트[슬라이싱]을 한 결과도 리스트가 나온다!!
	      # ex. sum([5, 6]) 처럼 리스트가 남게 됨.
        return sum(numbers[start[0]][start[1]:end[1] + 1])

		# 시작 행
    total = sum(numbers[start[0]][start[1]:])  
    # 끝 행
    total += sum(numbers[end[0]][:end[1] + 1])  

    # 중간 행이 존재하면 합산
    # 존재 안 할 경우 range 조건 따라 실행 안되고 바로 return됨.
    for i in range(start[0] + 1, end[0]):
        total += sum(numbers[i])

    return total

생각을 해보니, `if end[0] - start[0] == 1:` 는 사실 필요없는 조건문이었다!!!

왜냐면 어차피 시작 행과 끝 행이 하나 차이나면, 마지막 range문 조건에서 알아서 실행 안되고 넘어갈 것이기 때문이다.

대신`if end[0] - start[0] == 0:` 는 꼭 필요하다. 시작 행과 끝 행이 같을 경우는 체크해줘야함.

 

그리고, 리스트 슬라이싱과 sum 함수를 쓰면 더 편하고 파이써닉하게 풀 수 있었다.

특히, `리스트를 2칸 이상 슬라이싱하면, 그 결과는 리스트가 나올 수 있다`는 걸 잊지 말자!! (넘파이에서 배웠던 아이디어)

---

250218 재풀이

def solution(numbers, start, end):

    sx, sy = start
    ex, ey = end

    if sx == ex:
        return sum(numbers[sx][sy:ey+1])
    else:
        total = 0
        for x in range(sx + 1, ex):
            total += sum(numbers[x])
        total += sum(numbers[sx][sy:]) + sum(numbers[ex][:ey + 1])
        return total