글 읽기 - 복잡하게 풀긴 했지만 접근방식이 틀리진 않은거 같은데 코멘트 부탁드립니다

snowscale 5년 전 0

처음에 버블소트 시도하다가 당연하게도 시간 초과가 뜨고, 직접 쓰다보니까, 오름차순이 깨지는 순간 경계선의 개수와 관계가 있단 생각이 들었습니다.

오름차순이 깨지는 경계선 인덱스를 찾게되면, 마지막으로 그 경계선 역할을 했던 인덱스부터 서치해서 해당하는 숫자가 어느 자리에 들어가는 게 맞는지 조회하고, 그 위치부터 경계선 끝까지의 숫자를 구하도록 했는데요, 테스트 케이스나 제가 생각해본 배열들을 넣으면 답은 맞게 나오는데, 어떤 반례가 있을 지 모르겠습니다.

다른 해답을 보니까 정렬 전 배열과 정렬 후 배열의 인덱스 차를 구해서 답을 내던데, 제가 생각한 이 방식도 지금 얼핏 보기에는 답이 안 나오진 않겠단 생각이 들었거든요. 간과하고 있는게 있다면 알려주시면 감사하겠습니다.

import sys


def search(arr, begin, end, num):
    mid = (begin + end)//2
    new_begin = begin
    new_mid = mid
    new_end = end

    while begin <= new_begin <= new_end:
        if arr[new_mid] == num:
            if new_mid < end and arr[new_mid + 1] > num:
                return new_mid + 1
            else:
                new_begin = new_mid + 1
                new_mid = (new_begin + new_end) // 2
        elif arr[new_mid] < num:
            new_begin = new_mid + 1
            new_mid = (new_begin + new_end) // 2
        else:
            if new_mid > begin and arr[new_mid - 1] < num:
                return new_mid
            else:
                new_end = new_mid - 1
                new_mid = (new_begin + new_end) // 2

    return begin



arr = []

n = int(sys.stdin.readline())

for i in range(n):
    arr.append(int(sys.stdin.readline()))

last_border = 0
last_val = arr[0]
cnt = 0

for i in range(n):
    if last_val > arr[i]:
        cnt += i - search(arr, last_border, i-1, arr[i])
        last_border = i
    last_val = arr[i]

sys.stdout.write(str(cnt+1))

snowscale 5년 전 1

검색 결과

5 6 1 3 2 9 8 10 13 일 경우에는 4가 나와야하는데 제 계산에선 5가 나오는군요. 접근방법도 틀렸던거 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

복잡하게 풀긴 했지만 접근방식이 틀리진 않은거 같은데 코멘트 부탁드립니다

snowscale 5년 전 0

snowscale 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말