백준 [2501] 약수 구하기 문제 , 오답

Question

안녕하세요! 저는 코린이 입니다. 백준 문제를 풀었는데, 제 IDE에서는 분명 예시대로 잘 출력이 되는데 , 백준에서는 오답으로 나옵니다. 원인을 알고 싶어서 선배님들에게 여쭤봅니다.제가 짠 코드가 한숨만 나오지만 ! 발전을 위해 코드 리뷰 부탁드립니다.https://www.acmicpc.net/problem/2501 문제 출처 import java.util.ArrayList; import java.util.Scanner; public class test3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList numList = new ArrayList<>(); ArrayList numCheck = new ArrayList<>(); int n = sc.nextInt(); // n 의 약수 int k = sc.nextInt(); // k 번째로 작은 수 if( 0 > n ){ System.out.println(0); } int v; //나머지 int r; //몫 for (int i = 1; i <= 9; i++) { v = n % i; if (v == 0) { //나머지가 0인 것 배수 찾기 numList.add(i); r = n / i; numList.add(r); for (int item : numList) { if (!numCheck.contains(item)) { numCheck.add(item); } } } } if (k <= numCheck.size()) { Object[] arr = numCheck.toArray(); for (int s = 0; s < numCheck.size(); s++) { //size (4) for (int j = 0; j < numCheck.size() - 1; j++) { int o1 = (int) arr[j]; int o2 = (int) arr[j + 1]; if (o1 > o2) { int c = o1; arr[j] = o2; arr[j + 1] = c; } } } //System.out.println(Arrays.toString(arr)); k = k - 1; System.out.println(arr[k]); } if(k > numCheck.size()){ System.out.println(0); } } }

mirheeoj · Answer

1부터 9까지 체크하는 방법으로는 약수a, 약수b가 둘 다 10이상인 경우를 제대로 체크할 수 없습니다.예를 들어 1089의 약수는 1, 3, 9, 11, 33, 99, 121, 363, 1089이므로 네 번째 약수를 출력하면 돌려보면 11이 나와야 하나 본 로직으로는 121이라는 오답이 나옵니다. 로직을 그대로 살려서 10000이라는 최댓값에 대응하려면 첫 루프에서 체크하는 범위를 더 늘려야 할 것 같아요. 예를 들어 100까지 체크해보면 잘 나옵니다. (하지만 다른 부작용이 있을 수도 있습니다.)알고리즘 자체를 바꾸는 것은 논외로 치고 이외에 해볼 만한 것은.. linkedhashset, treeset 등 노가다를 줄일 수 있는 컬렉션을 사용해보세요. 문제를 빨리 풀고 오답을 줄이는 데에 도움이 될 겁니다. 그리고 소소하지만 처음 n값을 체크하는 것도 이미 n의 범위가 문제에 주어진 상태이므로 굳이 안하셔도 됩니다.

yeori · Answer

1부터 9까지만 나누면 안되구요,주어진 N에 대해서 Math.sqrt(N) 보다 작거나 같은 범위까지 나눠봐야 합니다.limt := Math.sqrt(N)N이 500이면 제곱근이 22.27xxx.. 니까 22까지는 봐야 함.K 가 위에서 구한 limit * 2 보다 크면 어차피 답은 없습니다. 약수가 아무리 많아봤자 갯수는 2* limit이하입니다.약수는 numList 안에 들어있을테니 정렬해서 k번째 값을 꺼내면 됩니다. 언어마다 정렬해주는 기능이 다 있으니 가급적 사용하는게 좋습니다.넣고나서 정렬하지 않고, 넣을때마다 정렬하는 자료구조를 연습삼아 써보면 좋습니다. TreeSet에 약수를 넣으면 꺼낼때마다 작은 값이 나옴(성능은 arraylist보다 좋지는 않음. 그냥 연습으로 해보는거..)약수의 특성을 잘 이용하면 정렬없이 값을 구할 수도 있습니다. 12의 경우 약수를 구하는대로 걍 집어넣음...01, 12, 02, 06, 03, 04그리고 인덱스를 잘 계산하면 k번째 약수의 위치를 따낼 수 있습니다.(16이나 25처럼 제곱근인 경우엔 4나 5를 두 개 다 넣음)

백준 [2501] 약수 구하기 문제 , 오답

2개의 답변

커리어 목록