글 읽기 - 제가 생각하지 못한 반례가 있나봅니다 ㅠㅠ

hdrgba 6년 전 1

81%까지 진행후에 틀렸습니다가 나오네요 ㅠㅠ

bucket 자료구조를 이용하였구요

단어의 길이를 key로, 그 단어의 길이로 구성된 문자열 배열리스트를 value로 하는 해쉬맵으로 구성했습니다.

같은 단어로만 넣어볼경우,

bb, aaaa 를 넣을경우 bb aaaa순서로 출력이 되구요...

미처 제가 생각지 못한 반례가 있다면 고수님들 도움 부탁드립니다 ㅠㅠ

import java.io.*;
import java.util.*;

class Data {
	HashMap<Integer, ArrayList<String>> bucket;

	public Data() {
		bucket = new HashMap<Integer, ArrayList<String>>();
	}

	public void put(String str) {
		int len = str.length();
		if (!bucket.containsKey(len)) {
            //넣으려는 문자열의 길이 key가 없는경우
			ArrayList<String> tmp = new ArrayList<String>();
			tmp.add(str);
			bucket.put(len, tmp);
		} else {
            //넣으려는 문자열의 길이 key가 있는경우
			ArrayList<String> tmp = bucket.get(len);
			if (tmp.contains(str)) {
                //문자열이 이미 존재하는 경우
				return;
			} else {
                //문자열이 존재하지 않는 경우
				tmp.add(str);
				Collections.sort(tmp);
			}
		}
	}

	public void printAll() {
		for (Map.Entry<Integer, ArrayList<String>> tmp : bucket.entrySet()) {
			for (String str : tmp.getValue()) {
				System.out.println(str);
			}
		}
	}
}

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1);
			int n = Integer.parseInt(br.readLine());
			Data data = new Data();
			for (int i = 0; i < n; i++) {
				data.put(br.readLine());
			}
			data.printAll();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

upple1 6년 전 2

해쉬의 자료구조 자체가 입력이 빠른 대신 검색이 정확하지 않습니다. 해쉬안에 있다고 판단해도 실제로는 없을 수도 있습니다. 자세한건 https://ko.wikipedia.org/wiki/...

대신 없다고 결정되면 확실히 없습니다. 때문에 이문제에는 적합하지 않은 것 같네요

hdrgba 6년 전 0

해쉬가 빠르다는것만 생각하고 무작정 달려들었었네요 ㅠㅠ

답변해주신것을 바탕으로 링크드리스트같은 다른 자료구조를 사용해보겠습니다 감사합니다!

upple1 5년 전 0

정정합니다. 해쉬자체는 정확하지 않은 건 사실이지만 자바에 내장된 라이브러리들은 링크드 리스트 등을 사용하여 정확하게 만든 것입니다. 잘못된 정보를 올린 것에 사과드립니다

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

문제

문제

출처

ICPC

제가 생각하지 못한 반례가 있나봅니다 ㅠㅠ

hdrgba 6년 전 1

upple1 6년 전 2

hdrgba 6년 전 0

upple1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말