[백준/BOJ] 10816번 : 숫자 카드 2 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

---

- 문제 -

 

난이도 실버 4 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

어려운 문제라 생각했다. 이분 탐색을 사용해 풀라 했기에 이분 탐색을 적용했지만 여러 문제점에 부딫혔고, 결국 기존의 푸는 방식을 포기하고, 여러 푸는 방법중 한명이 hashmap으로 풀었다길래 필자도 hashmap으로 풀었다. 워낙 입력값의 개수가 적지 않아서 어느정도 시간을 걸리지만 쉽게 통과했다. 하지만 hashmap은 key값과 value 값을 저장해서 key값 또는 value 값을 지정해서 같이 저장된 값을 구한다. 그렇다면 배열로도 충분히 가능할텐데, 마침 첨에 푼 부분에 적용한 것중 하나길래 그걸로 풀었다. 훨씬 빠르게 통과했다.

 

1. hashmap으로 푸는 방법.

2. 배열로 푸는 방법.

3. 아무도 궁금하지 않겠지만 필자가 처음에 풀었다 포기한 방법이다.(거의 이것만 6시간은 걸린거같다. 만약 보고서 문제점을 발견한 사람은 댓글로 알려주시면 감사합니다....)

 

1.

hashmap은 (key, value)값을 저장한다. 하지만 key값이 같으면 value값은 최근에 저장한 걸로 덮힌다.

예를 들면 3 5을 저장하고, 3 2를 저장하게되면 3이란 key에는 2라는 value가 저장된다.

10을 두번 저장하게 되면 10 2가 되는게 아니라 10 1이 된다는 것이다. 그렇기때문에 10이 2개가 오면 10 (키가 10인 value값을 불러와서 +1을하고 저장)하면 나온 만큼 값이 저장되는 것이다.

주의할 점은 hash에 저장되어있는 기초값은 null이다. 그렇기때문에 저장되어 있는게 없을 경우 1을 저장하고, 그 뒤에 저장된 값이 있을때 +1을 해주는 조건을 주자.

이제 hash에 저장된 value값을 출력해야하는데, 방금 말했듯 저장하지 않은 값에대한 키 값의 value는 기초값인 null이다. 그렇기때문에 여기도 조건을 넣고 없을 경우 0, 있을경우 value값을 출력하게 하면 된다.

 

2.

배열을 만든다. 크기는 20000001로 지정해준다. 이유는 입력될 값은 인덱스 입력될때마다 그 값을 인덱스로 갖는 값에 +1을 해줄 것이기때문에 입력가능한 값은 -10000000 ~ 10000000이고, -는 인덱스로 올 수 없기때문에 총 범위량인 20000000에 +1을해서 20000001로 크기를 지정해준것이다.

입력값이 5 2 5 3 8이면, 2인덱스에 1이, 3인덱스에 1, 5인덱스에 2, 8인덱스에 1이 저장되는 것이다.

정수형 배열의 기초값은 0이기때문에 hash맵처럼 빌 경우는 따로 신경 안써도 된다.

입력값을 인덱스로 지정해 주기위해서는 음수가 올 수 있기때문에 +10000000해주고 인덱스로 지정하자.

 

공통적으로 출력에는 StringBuilder를 사용한다. (BufferedWriter를 써도 된다.)

50만개의 입력값이 올 수 있기때문에 그걸 일일히 출력하게 되면 시간초과가 될 수 밖에 없다.

저장해서 한번에 출력하자.

 

코드를 보자.

---

-풀이-

 

1. hashmap

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			int input = Integer.parseInt(st.nextToken());
            //해당 key값에 저장된 value가 null이면 1을 대입 아니면 +1을 해준다.
			if(hash.get(input) == null) hash.put(input, 1);
			else hash.put(input, hash.get(input) + 1);
		}
		
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int input = Integer.parseInt(st.nextToken());
            //해당 key값에 저장된 value가 null이면 0을 sb에 저장해준다.
			if(hash.get(input) == null) sb.append(0).append(" ");
			else sb.append(hash.get(input)).append(" ");
		}
		System.out.println(sb);
	}

}

 

2. 배열

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		int[] arr = new int[20000001];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			int input = Integer.parseInt(st.nextToken());
			//해당 인덱스 값에 +1해준다.
			arr[input + 10000000]++;
		}
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int input = Integer.parseInt(st.nextToken());
			sb.append(arr[input + 10000000]).append(" ");
		}
		System.out.println(sb);
	}

}

 

3. 해결 못한 코드...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<Integer>();
		int[] arr = new int[20000001];
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(list);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int input = Integer.parseInt(st.nextToken());
			int count = 0;
			int start = 0;
			int end = list.size() - 1;
			int mid = (end + start) / 2;
			boolean check = false;
			
			while(!list.isEmpty()) {
				if(input > list.get(list.size() - 1) || input < list.get(0)) break;
				if(input == list.get(mid)) check = true;
				if(!check && input == list.get(start)) {
					mid = start;
					check = true;
				}
				if(!check && input == list.get(end)) {
					mid = end;
					check = true;
				}
				
				if(!check) {
					if(input > list.get(mid)) start = mid + 1;
					else end = mid - 1;
					mid = (end + start) / 2;
				}else {
					list.remove(mid);
					count++;
					if(mid == list.size() || input != list.get(mid)) {
						if(mid != 0) mid--;
					}
					if(list.isEmpty() || input != list.get(mid)) break;
				}
				if(end - start <= 1) break;
			}
			if(arr[input + 10000000] == 0) arr[input + 10000000] = count;
			sb.append(arr[input + 10000000]).append(" ");
		}
		System.out.println(sb);
	}

}

---

-결과-

 

1. hashmap 사용

2. 배열 사용

배열이 좀 더 빠른 대신 크기를 지정해주면 그만큼 쓰게되는 만큼 메모리가 더 크다.

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.