오답노트 #2370 : 시장 선거 포스터

풀이방법 및 문제점

2022.06.08 (1)

이분탐색을 쓰지 않고 그냥 좌표압축을 시도해보았다.

해시맵을 사용하였다.

역시 시간초과가 발생한다.

답의 값 자체는 맞게 도출되는 것 같다.

 

2022.06.08 (2)

이분탐색을 이용하여 좌표압축을 하니 해결되었다.

 

정답 게시글 바로가기

 

코드

Java(2022.06.08(1))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
		int n = Integer.parseInt(br.readLine());
		int[][] input = new int[n][2];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			input[i][0] = Integer.parseInt(st.nextToken());
			input[i][1] = Integer.parseInt(st.nextToken());
			hm.put(input[i][0], 0);
			hm.put(input[i][1], 0);
		}
		
		for(int i=0; i<n; i++) {
			for(int j=input[i][0];
					j<=input[i][1]; j++) {
				if(hm.containsKey(j))hm.put(j, i);
			}
		}
		
		int cnt = 0;
		for(int i=0; i<n; i++) {
			if(hm.containsValue(i)) cnt++;
		}
		
		System.out.print(cnt);
	}

}