글 읽기 - 11651번 반례가 있을까요?

ejc0628 3년 전 0

주석에도 달았지만,

0 4

1 2

1 -1

2 2

3 3

이런 경우,

y값을 key로 하고 x값들을 담는 list를 만들었습니다.

key	value
4	0
2	1, 2
-1	1
3	3

이렇게 담긴 map을

y좌표 list들을 sorting해준 뒤,

x좌표, y좌표 형태로 출력해주었습니다.

혹시 다른 반례가 있을까요?

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());

		Map<Integer, ArrayList<Integer>> map = new HashMap<>(); // map으로 정의
		for(int i = 0; i < num; i++) {
			String str = br.readLine();
			StringTokenizer tokens = new StringTokenizer(str, " ");
			int x = Integer.parseInt(tokens.nextToken());
			int y = Integer.parseInt(tokens.nextToken());
			
			ArrayList<Integer> list = map.get(y); //y좌표를 key값으로 가지는 list를 가져오기
			if(list == null) {
                //list가 없는 경우 -> list 생성이 필요함
				list = new ArrayList<Integer>();
				list.add(x); //list에 x좌표를 넣어준 후
				map.put(y, list); //map 자체에 < y좌표, x좌표 list형태>로 저장
			}
			else {
				list.add(x); //list가 있으면 그냥 추가
			}
		}
		Set<Map.Entry<Integer, ArrayList<Integer>>> entries = map.entrySet();
		for(Map.Entry<Integer, ArrayList<Integer>> entry : entries) {
			Collections.sort(entry.getValue()); //x좌표 list를 sorting해주기
			for(Integer i : entry.getValue()) { 
				bw.write(i + " " + entry.getKey() + "\n"); //<y좌표, x좌표> 형태로 저장되어 있으니, 거꾸로 출력
			}
		}
		
		bw.flush();
		bw.close();	
	
	}
}

pichulia 3년 전 0

HashMap은 Key 순으로 정렬이 되어있지 않습니다.

TreeMap을 사용하시던가, entrySet을 다시 정렬해야합니다.

https://www.java67.com/2015/01...

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

문제

문제

출처

ICPC

11651번 반례가 있을까요?

ejc0628 3년 전 0

pichulia 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말