4107. Count Valid Suffix Sorts I

Published at 2026-11-17

https://leetcode.com/problems/count-valid-suffix-sorts-i/

문제 요약

길이가 n으로 같은 nums, target 배열 두개가 주어진다. 각 인덱스 i를 기준으로 앞은 그대로, 뒤는 내림차순 정렬했을때 이 새로운 배열이 target과 같은 경우의 수를 반환

직관

  • 배열 전체를 한번에 정렬해서 비교하면 안된다. 가장 작은 숫자가 맨 앞 인덱스에 있었는데 한번에 정렬해버렸다면 그 작은 숫자는 게속 마지막 인덱스에 위치할 것이기 때문
  • 어쨋든, 실제 정렬할 필요는 없고, 비교하려고 하는 범위의 target 배열이 내림차순이어야만 한다. 이는 뒤쪽부터 앞으로 오면서 직전 인덱스 숫자만 확인하면 될 것이다.
  • 근데 순수히 target이 내림차순인지만 확인하면안되는게, i 기준 앞쪽 인덱스는 정렬없이 비교해야 하기 때문.

풀이

  • i를 기준으로 앞, 뒤로 쪼개서 생각한다.
  • 조건1: 앞부분은, 0번부터 하나씩 뒤로가면서 target, nums의 각 위치를 비교해서 같은지 확인
  • 조건2: 뒷부분은, 끝에서부터 하나씩 앞으로 오면서 target이 바로 직전 만난(뒤)숫자랑 비교해서, 내림차순으로 구성되어있는지 확인
  • 조건1과 조건2는, 한번이라도 어긋나면, 그 이후 비교는 항상 실패하기 때문에 의미가 없다. 따라서, 각 조건이 어느 위치에서 유효하지 않은지 확인한다.
  • 조건1과 조건2를 둘다 만족하는 케이스의 개수를 알아내야 하기 때문에, 조건1이 뒤로 간 위치랑 조건2가 앞으로 간 위치를 이용해서 사이에 몇개의 케이스가 있는지 알아낸다.
class Solution:
    # 인덱스 i를 기준으로, 앞 뒤 배열로 쪼갰을때, 각 부분이 다음 두 조건을 모두 만족해야한다.
    # 1. i의 앞: 동일한 위치의 nums와 타겟 배열이 동일해야함
    # 2. i의 뒤: 타겟 배열이 내림차순이어야함
    # 1번 조건은, 앞에서부터 체크하다가 한번이라도 nums,target가 달라지면, 그 이후는 모두 다를것이다.
    # 2번 조건 역시, 뒤에서부터 체크하다가 한번이라도 target이 내림차순이 아니게되면, 앞은 모두 내림차순이 안될것이다.
    # 1번 조건을 만족하는 범위와 2번 조건을 만족하는 범위의 교집합을 구하면 될 것이다.
    def countSuffix(self, nums: list[int], target: list[int]) -> int:
        i, j = 0, len(nums)-1
        last_num = target[j]

        # 두 배열이 구성이 다른경우(개수, 숫자구성) 예외처리
        if Counter(nums) != Counter(target):
            return 0

        while i < len(nums)-1:
            if nums[i] == target[i]:
                i += 1  # 1번 조건이 깨진 자리. 윗줄에서 조건을 비교한 후 증가시키기 때문에 깨진자리는 다음번 돌때 저장될것이다.
            else:
                break

        while j >= 0:
            if target[j] >= last_num:
                last_num = target[j]
                j -= 1  # 2번 조건이 깨진 자리.
            else:
                break

        # 1번 조건을 만족하는 범위는 0 ~ i-1 (-1하는 이유: 위에서 다음 루프 돌릴때 +1 해서 돌리기 때문)
        # 2번 조건 만족하는 범위는 j+1 ~ 끝
        # 위 두 사이에 해당하는 인덱스 개수를 알아내야 하기 때문에 이는 i-j로 구할 수 있다.
        return max(0, i - j)
        

시간복잡도 O(N)