[백준][오픈테스트] 3초 정렬

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/22963

22963번: 3초 정렬

 

내가 작성한 코드

import sys, copy
from collections import deque
from collections import defaultdict
read = sys.stdin.readline

N = int(read().rstrip())
nums = list(map(int, read().rstrip().split(' ')))
q = deque([(0, defaultdict(int))])

# nums[i] > nums[i+1]일 때
# i+1 이전값들을 nums[i+1]로 바꿔주는 방식
def left(i: int, ans):
    l, right = i, nums[i+1]
    ans = copy.copy(ans)
    while l >= 0 and nums[l] > right:
        ans[l+1] = right
        l -= 1
    return ans

# i 이후값들을 nums[i]로 바꿔주는 방식
def right(i: int, ans):
    left, r = nums[i], i+1
    ans = copy.copy(ans)
    while r < len(nums) and nums[r] < left:
        ans[r + 1] = left
        r += 1
    return ans

answer = defaultdict(int)
while q:
    i, answer = q.popleft()
    if len(answer) > 3:
        continue
    while i < len(nums)-1:
        if nums[i] > nums[i+1]:
        	# left/right 방식의 결과를 queue에 삽입
            q.append((i+1, left(i, answer)))
            q.append((i+1, right(i, answer)))
            break
        i += 1
    # nums 탐색이 끝나고 answer가 3개 이하이면 종료
    if i == len(nums)-1 and len(answer) <= 3:
        break

if len(answer) > 3:
    print("NO")
else:
    print("YES")
    print(len(answer))
    for i, num in answer.items():
        print(i, num)

• 정렬이 되지 않은 시점
  
  • nums[i] > nums[i+1]일 때
• 2가지 방식
  • nums[0:i+1] 중 nums[i+1]보다 큰 값들 바꾸기
  • nums[i+1:N] 중 nums[i]보다 작은 값들 바꾸기
• 바꿀 수 있는 값(3)이 작으므로 완전탐색
  • "정렬되지 않은 시점"에 대해, "2가지 방식"을 모두 탐색

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 복잡한 여러 조건들이 떠올랐으나, 위에서 정의한 2가지 방식으로 완전 탐색해도 충분함
  
  • N이 최대 200,000 -> O(n)도 충분
  • 바꿀 수 있는 값이 3 -> DFS/BFS 등을 활용한 완전탐색에 부담이 없음
• 조금 헷갈렸던 것이 N의 범위
  • 문제의 "제한" 중
    1. 1 <= N <= 200_000
    2. 이미 오름차순으로 정렬된 수열은 주어지지 않는다.
  • N == 1일 때, 이 수열은 정렬이 된 수열 또는 정렬할 수 없는 수열
  • N == 1일 때, 테스트 케이스가 없는 듯 ("YES"/"NO")에 대한 제출 모두 통과
  • 관련 내용 수정 올림

https://www.acmicpc.net/board/view/73811

글 읽기 - N의 범위 오류 (N=1 제외 요청)

+) 답변을 받았는데 조건은 종합적으로 봐야한다고 한다. 조건끼리의 모순을 찾아내지말고 모든 조건이 성립해야한다고 생각해야겠다. 즉, "이미 오름차순으로 정렬되지 않은 수열"만 주어진다는 조건으로 인해, N == 1인 경우는 입력으로 들어오지 않는다.