[백준 28099번] 파이썬 - 이상한 배열

백준 28099 - 이상한 배열

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 길이가 N인 배열 A가 주어진다.
• 배열 A가 아래 조건을 만족한다면 이 배열 A를 이상한 배열이라 한다.
• Ai = Aj를 만족하는 정수 1 <= i, j <= N와 i < k < j를 만족하는 정수 k에 대해, 항상 Ak <= Ai를 만족한다.
• 배열 A가 주어질 때 A가 이상한 배열인지 확인해라.

입력

• 첫 줄에 테스트케이스의 수 T가 주어진다 (1 <= T <= 200,000)
• 각 테스트케이스에 대해, 첫 번째 줄에 배열의 길이 N이 주어진다. (1<=N<=200,000)
• 두 번째 줄에는 배열의 원소를 나타내는 N개의 정수 A1, A2, .... , AN이 공백으로 구분되어 주어진다. (1<=Ai<=N)
• 모든 테스트 케이스에 대해 N의 합이 200,000이하임이 보장된다.

출력

• 각 테스트케이스에 대해 주어진 배열이 이상한 배열이면 Yes, 아니라면 No를 출력한다.

# 접근 방법

처음 아이디어

• 우선 입력받은 배열에 중복되는 숫자가 없다면, 이상한 배열에도 포함된다.
  • 주어진 테스트 케이스의 1번이 위와 같은 경우여서 이해하는데 시간이 조금 걸렸다.
• nums 딕셔너리를 만들어주고 value값은 리스트로 설정해준다.
• 이후 주어진 배열을 순회하며 각 숫자가 위치한 인덱스 번호를 nums 딕셔너리에 넣어준다.
• 이후, nums의 숫자들을 하나씩 순회할 건데
  • 1보다 크다면 nums[i][0] 부터 nums[i][-1] 까지 순회하며 현재 i보다 arr[k]가 작거나 같은지 검사해준다.
  • 만약 하나라도 크다면 No를 출력해주고 break
• 현재 풀이 같은 경우 O(N^2)의 시간 복잡도이므로 최악의 케이스인 73%에서 시간 초과가 발생한다. 조금 더 줄일 수 있는 방법을 찾아야 할 것 같다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict  


T = int(input())  
for _ in range(T):  
    N = int(input())  
    arr = [*map(int, input().split())]  
    nums = defaultdict(list)  
    for idx, val in enumerate(arr):  
        nums[val].append(idx)  

    result = 'Yes'  
    for i in nums:  
        flag = True  
        if len(nums[i]) == 1:  
            continue  
        for k in range(nums[i][0]+1, nums[i][-1]):  
            if arr[k] > i:  
                print('No')  
                flag = False  
                break  
        if not flag:  
            break  

    else:  
        print(result)

• 아래 범위 내를 탐색하는 부분을 set을 이용하여 변경해주었다.
• 해당 숫자가 처음 등장하는 인덱스라면 set에 add 해주고, 마지막 인덱스라면 set에서 remove해주었는데
  • 이 때, 순회하는 인덱스의 숫자는 set 안에 있는 최소 숫자보다 작아야한다는 조건을 걸어주었다.
  • C++에서는 정렬되는 set이 있어 set 내부의 최소값을 찾는 것이 빠르지만 python에서는 min을 이용해주어야 해서 여전히 시간초과가 발생했다.

check = set()
for idx, val in enumerate(arr):
    if check and val > min(check):
        result = 'No'
        break
    if nums[val][1] == -1:
        continue
    if not val in check:
        check.add(val)
    elif idx == nums[val][1]:
        check.remove(val)

• 3일동안 고민한거 같다.
• 스택과 오큰수를 활용하여 풀어 줄 수 있었다.
  • 오큰수란 숫자들이 나열되어 있을 때, 각 숫자별로 오른쪽에 있는 숫자 중 해당 숫자보다 큰 숫자 중 가장 왼쪽에 외치한 수 말한다.
• 우선 오큰수의 인덱스를 기록할 o_index를 N+1의 값을 default로 만들어 준다.
• 또한, Counter 함수를 이용하여 2번이상 등장하는 숫자들을 기록해준다.
• 빈 스택을 만들고 이제 0번부터 순회를 시작한다
  • 우선 2번 이상 등장한 수라면, check 딕셔너리에 등장한 인덱스를 기록해준다.
• while 문을 돌려줄건데 스택에 수가 존재하고 현재 순회중인 nums[i]가 스택의 top보다 큰 경우에만 계속 돌려준다.
  • 만약 위의 조건을 만족하여 while문을 수행하게 된다면, 현재 스택의 마지막의 오큰수는 정해진 것이다.
  • 따라서, stack을 pop한 값을 o_index에 현재 i로 기록해준다.
• while문이 끝났다면 현재 수를 stack에 넣어준다.
• 모든 수를 한번 순회했다면 해당 수의 오큰수가 정해졌기 때문에 답을 찾기 위한 for 문을 다시 한번 수행해준다.
  • 현재 수가 2번이상 등장한 수이고, 현재 인덱스의 오큰수가 현재 수가 마지막으로 등장한 인덱스보다 작다면 answer = False로 해준다.
  • 마지막까지 False로 변경되지 않았다면 Yes를 출력해준다.
• 예를 들어보면 4 3 5 4 1 6 이라는 배열이 주어졌을 때 오큰수의 인덱스를 기록한 리스트는 [5 2 5 5 5 6]이 되고 for문을 돌리다가 5의 인덱스 2의 차례가 되었다고 해보자.
  • 이 때 기록되어있는 오큰수 인덱스는 5이고 2번이상 등장한 4의 마지막 인덱스는 4이므로 주어진 조건에 위배되는 것이 확인된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import Counter, defaultdict  

T = int(input())  
for _ in range(T):  
    N = int(input())  
    nums = [*map(int, input().split())]  

    set_num = set(Counter(nums) - Counter(set(nums)))  
    check = defaultdict(list)  

    o_index = [N+1] * N  
    stack = []  
    for i in range(N):  
        if nums[i] in set_num:  
            check[nums[i]].append(i)  

        while stack and nums[i] > nums[stack[-1]]:  
            o_index[stack.pop()] = i  

        stack.append(i)  

    answer = 'Yes'  
    for i in range(N):  
        if nums[i] in check and o_index[i] < check[nums[i]][-1]:  
            answer = 'No'  
            break  
    print(answer)