글 읽기 - 반례를 못찾겠어요

spicechicken 5년 전 0

먼저 단어 길이별로 퀵정렬 후에, 배열안에 저장되어있는 단어의 길이에 따라 나누어 새로운 배열을 만들고

같은 길이의 단어만 들어 있는 배열을 정렬해서 기존에 배열에 값을 다시 넣는 구조로 짰는데

시간초과도 아니고 틀렸다고 나와서, 제가 생각한 여러 반례를 넣어봐도 값은 잘 나오더라고요

혹시 코드 구조상 문제점이 있거나 반례가 있는지 궁금합니다

import java.util.*;

public class Main {

	static void swap(String[] a, int i, int j) {
		String temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	static int partition(String[] a, int start, int end) {
		int value = a[end].length(); // 기준값
		int i = start - 1; // i는 1구역의 끝지점
		for (int j = start; j <= end - 1; ++j) // j는 3구역의 시작 지점
			if (a[j].length() < value) // a[j] 값이 1구역에 속하면
				swap(a, ++i, j); // a[j] 값을 1구역의 끝에 추가한다. 1구역 크기 1증가.
		swap(a, i + 1, end); // 기준값인 a[end] 원소와 2구역의 시작 원소를 교환한다.
		return i + 1; // 기준값 위치 리턴
	}

	static void quickSort(String[] a, int start, int end) {
		if (start >= end)
			return;
		int middle = partition(a, start, end); // 배열 나누기
		quickSort(a, start, middle - 1); // 1구역 정렬
		quickSort(a, middle + 1, end); // 2구역 정렬
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		String[] arr = new String[num];
		sc.nextLine();

		for (int i = 0; i < num; i++)
			arr[i] = sc.nextLine();

		Set<String> temp = new LinkedHashSet<String>(Arrays.asList(arr));
		String[] unique = temp.toArray(new String[temp.size()]); // 중복 제거

		quickSort(unique, 0, unique.length-1); // 단어 길이별 sort
		System.out.println(Arrays.toString(unique));

		int start = 0;
		int end = 0;

		for (int i = 0; i < unique.length - 1; i++) {
			if (unique[i].length() != unique[i + 1].length()) { // 같은 길이의 단어를 저장하고 있는 영역인지 검사
				String[] tempArr = new String[end - start + 1]; // 같은 길이의 단어를 저장하는 배열
				System.arraycopy(unique, start, tempArr, 0, end - start + 1); // 같은 길이의 단어만 가진 영역을 복사
				Arrays.sort(tempArr);
				for (int j = 0; j < tempArr.length; j++) {
					unique[start++] = tempArr[j]; // 기존 배열에 sorting이 완료된 단어 입력
				}
				end = start; // 다음 영역 초기화
			} else
				end++; //같은 길이의 단어를 저장하는 영역일시 영역의 마지막 값 증가
		}

		for (String s : unique)
			System.out.println(s);
	}

}

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

문제

문제

출처

ICPC

반례를 못찾겠어요

spicechicken 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말