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)