글 읽기 - 이 문제 어떻게 풀면 좋을까요..

dnpdhd 1년 전 0

정답 제대로 나오게 하면 시간초과뜨고,

그나마 21%까지 맞춘 문제는 '맞았을 때'는 제대로 걸러낼 수 있지만 '틀렸을 때(0이 출력되어야 할 때)'를 맞았다고 출력해버립니다..

6
1 2 3 4 5 6
2 1 3 4 5 6

같은 경우에서요...

ㅠㅠ조그마난 힌트라도 좋으니 도움 부탁드립니다.

import sys
input = sys.stdin.readline
import math
n=int(input())
l=list(map(int,input().split()))
lb=list(map(int,input().split()))
def merge(l,p,q,r):
    global n
    tmp=[] #임시
    index1=p
    index2=q+1
    while True:
        if index1>q or index2>r: #둘 중 하나가 다 빠졌다
            break
            
        if l[index1]<=l[index2]:
            tmp.append(l[index1])
            
            index1+=1
        else:
            tmp.append(l[index2])
            index2+=1
            
   
    while True:
        if index1>q:  #왼쪽리스트가 덜 빠졌다
            break
        tmp.append(l[index1])
        index1+=1
            
    while True:
        if index2>r: 
            break
        tmp.append(l[index2])
        index2+=1

    a=p
    b=0
    신뢰=True
    while True:
        if a>r:
           break
        l[a]=tmp[b]
        #print(l)
        if l[a]!=lb[a]:
            신뢰=False
        if 신뢰==True:
            for i in range(a+1,n):
                #print(i,l)
                if l[i]!=lb[i]:
                    break
                elif i==n-1: #마지막이면
                    print(1)
                    sys.exit()
        a+=1
        b+=1


def merge_sort(l,p,r):
    if p<r:
        q= (p+r)//2
        merge_sort(l,p,q) 
        merge_sort(l,q+1,r)
        merge(l,p,q,r)
if l==lb:
    print(1)
    sys.exit()

#없는 요소 검사하는건 시간초과뜸

merge_sort(l,0,n-1)
        
print(0)

dh0450 1년 전 1

제가 푼 방식은 다음과 같습니다.

A 가 바뀔 때마다 맞는지 체크를 하되을 이전까지 일치했던 부분부터 탐색합니다.

일치를 확인한 인덱스 이전에서 교환이 또 일어나면 0 을 출력하고, 완전히 일치하지 못해도 0 을 출력합니다.

그리고 고수님들 푼거 보니까 코드가 신기하더라고요 ㅠㅠ

dnpdhd 1년 전 0

dh0450님도 엄청난 고수이신걸요..?

막막했는데.... 정말 감사드립니다....ㅠㅠ!!

복 많이많이 받으시길 바랍니다 !! 정말 감사드려요

dnpdhd 1년 전 0

와 ㅠ 드디어 풀었습니다... 덕분입니다... 정말... ㅜㅜㅠㅜㅜㅠ

dnpdhd 1년 전 0

추가로 반례 남겨놓습니다.

4 5 1 3 2

4 5 1 3 3

4 5 1 3 2

4 5 6 3 2

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

문제

문제

출처

ICPC

이 문제 어떻게 풀면 좋을까요..

dnpdhd 1년 전 0

dh0450 1년 전 1

dnpdhd 1년 전 0

dnpdhd 1년 전 0

dnpdhd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말