파이썬으로 블록 높이 리스트가 y=x 직선을 기준으로 대칭인지 확인하는 프로그램

숫자 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트는 정사각형 블록들의 높이를 나타내며, 우리가 확인해야 할 것은 이 블록들이 이루는 전체 형태가 y = x 직선을 기준으로 대칭인지 여부입니다.

예를 들어 입력이 nums = [7, 5, 3, 2, 2, 1, 1]이라면, 이 블록 형태는 y = x 선에 대해 대칭이므로 출력은 True가 됩니다.

문제 해결 접근 방법

y = x 축 대칭에서는 좌표 (i, j)에 블록이 존재한다면 좌표 (j, i)에도 반드시 블록이 존재해야 합니다. 이 성질을 이용해 오른쪽 끝 열부터 왼쪽으로 이동하면서 각 열의 높이와 해당 행의 길이가 서로 일치하는지 검사하면 됩니다. 구체적인 단계는 다음과 같습니다.

• i를 0으로 초기화합니다.
• j를 (nums의 길이 − 1)로 초기화합니다.
• i <= j인 동안 다음을 반복합니다.
  • h := nums[j]
  • i < h인 동안 다음을 반복합니다.
    • 만약 nums[i]가 (j + 1)과 같지 않다면 False를 반환합니다.
    • i를 1 증가시킵니다.
  • j를 1 감소시킵니다.
• 모든 검사를 통과하면 True를 반환합니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

class Solution:
    def solve(self, nums):
        i = 0
        j = len(nums) - 1
        while i <= j:
            h = nums[j]
            while i < h:
                if nums[i] != j + 1:
                    return False
                i += 1
            j -= 1
        return True

ob = Solution()
nums = [7, 5, 3, 2, 2, 1, 1]
print(ob.solve(nums))

입력

[7, 5, 3, 2, 2, 1, 1]

출력

True

동작 원리

이 알고리즘은 두 개의 포인터 i와 j를 사용해 리스트의 양쪽 끝에서부터 안쪽으로 검사를 진행합니다. 먼저 마지막 열의 높이 h를 읽고, 그 높이만큼의 각 행 i에 대해 nums[i]의 값이 j + 1과 정확히 일치하는지 확인합니다. 대칭 형태라면 (i, j) 셀과 (j, i) 셀이 항상 짝을 이루어야 하기 때문입니다. 검사 과정에서 단 하나라도 조건이 어긋나면 즉시 False를 반환하고, 모든 조건을 통과하면 True를 반환합니다. 이 방식은 각 요소를 한 번씩만 방문하므로 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.