글 읽기 - 계속 100%에서 틀렸다고 나오는데... 뭔 반례가 있을 수 있는지 모르겠어요.

junee0203 2년 전 0

MergeSort로 풀었습니다.

우선, 완전 같은 문자열은 그냥 뒤에껄 먼저 처리.

길이만 같다면, 가장 앞부터 사전순서대로 비교.

아니라면 길이로 비교.

가능한 모든 걸 다 넣어봤지만, 다 되는데 뭔 반례가 존재할 수 있는건지 모르겠어요...

혹시 이상한 반례같은거 있다면, 조언 좀 부탁드립니다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		String[] arr = new String[N];
		String[] sorted = new String[N];
		
		for(int i=0; i<arr.length; i++) {
			arr[i] = sc.nextLine();
		}
		
		mergeSort(arr, 0, arr.length-1, sorted);

		System.out.println(sorted[0]);
		for(int i=1; i<sorted.length; i++) {
			if(sorted[i-1].equals(sorted[i]))
				continue;
			else
				System.out.println(sorted[i]);
		}
	}
	public static void mergeSort(String[] arr, int left, int right, String[] sorted) {
		int mid = (left+right)/2;
		if(left < right) {
			mergeSort(arr, left, mid, sorted);
			mergeSort(arr, mid+1, right, sorted);
			merge(arr, left, mid, right, sorted);
		}
	}
	public static void merge(String[] arr, int left, int mid, int right, String[] sorted) {
		int frontIdx = left;
		int rearIdx = mid+1;
		int sortedIdx = left;
		
		while(frontIdx <= mid && rearIdx <= right) {
			if(arr[frontIdx].equals(arr[rearIdx])) {
				sorted[sortedIdx++] = arr[rearIdx++];
			} else if(arr[frontIdx].length() == arr[rearIdx].length()) {
				String frontStr = arr[frontIdx];
				String rearStr = arr[rearIdx];
				for(int i=0; i<frontStr.length(); i++) {
					if(frontStr.charAt(i) < rearStr.charAt(i)) {
						sorted[sortedIdx++] = arr[frontIdx++];
						break;
					} else if(frontStr.charAt(i) > rearStr.charAt(i)) {
						sorted[sortedIdx++] = arr[rearIdx++];
						break;
					}
				}
			} else if(arr[frontIdx].length() < arr[rearIdx].length()) {
				sorted[sortedIdx++] = arr[frontIdx++];
			} else {
				sorted[sortedIdx++] = arr[rearIdx++];
			}
		}
		
		if(frontIdx > mid) {
			for(int i=rearIdx; i<=right; i++) {
				sorted[sortedIdx++] = arr[i];
			} 
		} else {
			for(int i=frontIdx; i<=mid; i++) {
				sorted[sortedIdx++] = arr[i];
			}
		}
		
		for(int i=left; i<=right; i++) {
			arr[i] = sorted[i];
		}
	}
}

junee0203 2년 전 0

제 병합정렬은 단어가 1개일 때는 제대로 동작하지 않았습니다. 죄송합니다. 다른건 맞았네요.

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

문제

문제

출처

ACM-ICPC

계속 100%에서 틀렸다고 나오는데... 뭔 반례가 있을 수 있는지 모르겠어요.

junee0203 2년 전 0

junee0203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말