[백준] '머리 톡톡' 1241번 - Java

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

---

문제

---

풀이

해시맵과 소수판정을 이용하여 풀었습니다.

 

소수판정을 할 때 약간 주의하면 됩니다.

• 시간 초과 해결을 위해 Math.sqrt()이하까지만 반복할 것
• 약수라 판정될 경우
  • 약수가 map에 있는지 존재 여부 확인, 있다면 value값 만큼 answer 갱신
  • 만약 약수가 1이라 자기자신이 나올 경우, 이 경우에는 answer를 1만큼 빼주기
  • 만약 4/2 = 2와 같이 key/i == i가 되는 경우, map.get(i) 만큼 다시 빼주기

 

그리고 hashmap을 이용하여 풀어서 result라는 배열을 따로 만들어 해당 번호를 들고있을 사람이 머리를 톡톡 치는 횟수를 저장한 뒤, 출력합니다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		int[] arr = new int[n+1];
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=1; i<=n; i++) {
			int curr = Integer.valueOf(br.readLine());
			arr[i] = curr;
			if(map.containsKey(curr)) map.put(curr, map.get(curr)+1);
			else map.put(curr, 1);
		}
		
		int[] result = new int[1_000_001];
		for(int key: map.keySet()) {
			int answer = 0;
			
			if(key <= 1) answer = map.get(key) - 1; 
			else {
				for(int i=1; i<=Math.sqrt(key); i++) {
					
					if(key % i == 0) {
						if(map.containsKey(i)) answer += map.get(i);
						if(map.containsKey(key/i)) {
							answer += map.get(key/i);
							if(key/i == key) answer --;
							if(key/i == i) answer -= map.get(i);
						}
					}
				}
			}
			result[key] = answer;
		}
		
		for(int i=1; i<=n; i++) {
			System.out.println(result[arr[i]]);
		}
	}

}

 

---

회고

1중 for문으로 푸는 방법인 줄 알고 많이 고민했는데 소수판정으로 시간을 줄이는 방법이었네요..