글 읽기 - 버블 소트 질문

myp7 7년 전 0

정렬 시킨후 이분검색으로 값의 정렬된 위치를 찾고

값의 정렬된 위치가 원래 위치보다 앞에 있는 경우 이동 거리를 구했습니다.

이동거리 중 최대인 값을 구했는데..

답이 틀렸다고 나오네요.. 어디가 잘 못된 걸까요??ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class prb1377 {
	private static int dis;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		int[] a = new int[n];
		int[] d = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.valueOf(br.readLine());
			d[i] = a[i];
		}

		Arrays.sort(d);
		for (int i = 0; i < n; i++) {
			bSearch(0, d.length - 1, a[i], d, i);
		}
		System.out.println(dis+1);
	}

	private static void bSearch(int l, int h, int k, int[] d, int index) {
		while (l <= h) {
			int mid = (l + h) / 2;
			if (d[mid] ==  k) {
				if (mid < index){
					if(dis < index - mid)
						dis = index - mid;
				}
				return;
			}
			if (d[mid] > k)
				h = mid - 1;
			else
				l = mid + 1;
		}
	}
}

baactree 7년 전 0

같은 숫자가 여러개 나올 수 있어요

myp7 7년 전 0

같은 숫자가 여러개 나오는 것을 생각 못했네요. 답변 감사합니다!

같은 숫자를 처리하기 위해 이분검색으로 숫자를 검색 후

한칸씩 움직이면서 다음 숫자와 비교를 통해 같은 숫자 중 마지막 숫자의 인덱스 값을 얻었습니다.

이렇게 하니 정답은 맞는거 같은데 시간 초과가 나와버리네요;;

혹시 중복된 숫자에서 마지막 인덱스를 찾는 더 빠른 방법이 있을까요?? 잘 생각이 않나네요..ㅠ

다시한번 항상 답변해 주셔서 감사합니다. :D

private static void bSearch(int l, int h, int k, int[] d, int index) {
        while (l <= h) {
            int mid = (l + h) / 2;
            if (d[mid] ==  k) {
                while((mid+1)<d.length && d[mid]==d[mid+1]){
                    mid = mid+1;
                }
                if (mid < index){
                    if(dis < index - mid)
                        dis = index - mid;
                }
                return;
            }
            if (d[mid] > k)
                h = mid - 1;
            else
                l = mid + 1;
        }
    }

baactree 7년 전 0

stable_sort와 unstable_sort에 대해서 공부해보세여

show454 6년 전 0

이거 stable sort돌려야 하는데

데이터 벡터로 받고 그냥 솔트 돌리신 분들도 정답이 출력되네요

벡터를 이용한 sort에서 안정성이 보장이되나요?

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

문제

문제

출처

ICPC

버블 소트 질문

myp7 7년 전 0

baactree 7년 전 0

myp7 7년 전 0

baactree 7년 전 0

show454 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말