☌

[WEIRD] Weird Numbers

개발이야기/알고스팟2021. 12. 30. 11:33

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/WEIRD

 

algospot.com :: WEIRD

Weird Numbers 문제 정보 문제 In mathematics, weird numbers are natural numbers that are abundant but not semiperfect. In other words, a natural number N is a weird number if and only if: Sum of its proper divisors (i.e. less than N ) is greater than

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            System.out.println(isWeird(scanner.nextInt()) ? "weird" : "not weird");
        }
    }
    
    private static boolean isWeird(int n) {
        List<Integer> divisors = getDescSortedDivisors(n);
        if (divisors.size() < 2) throw new IllegalArgumentException("N was not greater than 1");
        
        return isWeird(divisors.remove(0), divisors);
    }
 
    private static boolean isWeird(int n, List<Integer> divisors) {
        // Condition 1 : Sum of its proper divisors (i.e. less than N ) is greater than the number.
        int sum = 0;
        for (Integer divisor : divisors) {
            sum += divisor;
        }
        if (sum < n) return false;
 
        // Condition 2 : No subset of its divisors sum to N.
        return !hasSumOfDivisorsToN(n, divisors, 0, 0);
    }
 
    private static List<Integer> getDescSortedDivisors(int n) {
        List<Integer> ret = new ArrayList<>();
        for (int i = (int) Math.sqrt(n); i >= 1; --i) {
            if (n % i != 0) continue;
            int divide = n / i;
            if (divide == i) ret.add(divide);
            else {
                ret.add(0, divide);
                ret.add(i);
            }
        }
 
        return ret;
    }
 
    private static boolean hasSumOfDivisorsToN(int n, List<Integer> divisors, int acc, int cur) {
        if (n == acc) return true;  // 기저사례 1 : 누적된 덧셈이 n 가 동일한가? (N 을 구성할 수 있는 Subset 존재)
        if (n < acc) return false;  // 기저사례 2 : 누적된 덧셈이 n 보다 큰가? (해당 경우의 수는 더 살펴보지 않음)
        if (divisors.size() <= cur) return false; // 기저사례 3 : index 가 약수의 개수를 초과 (경우의 수 끝에 도달)
 
        // 각 index 의 숫자를 포함하는 경우와 아닌 경우에 따라 완전탐색을 한다.
        // 큰 수를 먼저 덧셈하기 때문에, 기저사례2 에 먼저 도달할 수 있도록 처리한다.
        return hasSumOfDivisorsToN(n, divisors, acc + divisors.get(cur), cur + 1)
                || hasSumOfDivisorsToN(n, divisors, acc, cur + 1);
    }
}
 cs

 


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
[BOARDCOVER] 게임판 덮기  (0) 2021.12.28
Posted by N'
,

[XHAENEUNG] 째능 교육

개발이야기/알고스팟2021. 12. 29. 00:36

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/XHAENEUNG

 

algospot.com :: XHAENEUNG

째능 교육 문제 정보 문제 산업 기능 요원 복무를 무사히 마치고 학교로 돌아온 xhae는 최근 복학을 위한 많은 지출로 인해 자금난에 허덕이고 있었다. 이러한 xhae가 선택한 일은 다름 아닌 째능

www.algospot.com

 

풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
 
public class Main {
    private static final String[] matches = new String[]{
            "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
    };
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int a = parseNumber(scanner.next());
            String op = scanner.next();
            int b = parseNumber(scanner.next());
            scanner.next();
            String c = scanner.next();
 
            int expected;
            switch (op) {
                case "+":
                    expected = a + b;
                    break;
 
                case "-":
                    expected = a - b;
                    break;
 
                case "*":
                    expected = a * b;
                    break;
 
                default:
                    throw new IllegalArgumentException();
            }
 
            boolean ret = false;
            if (expected >= 0 && expected < matches.length) {
                char[] expectedArray = matches[expected].toCharArray();
                char[] actualArray = c.toCharArray();
                Arrays.sort(expectedArray);
                Arrays.sort(actualArray);
                ret = Arrays.equals(expectedArray, actualArray);
            }
 
            System.out.println(ret ? "Yes" : "No");
        }
    }
 
    private static int parseNumber(String str) {
        for (int i = 0, len = matches.length; i < len; ++i) {
            if (matches[i].equals(str)) return i;
        }
 
        throw new IllegalArgumentException();
    }
}
 cs

 


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[WEIRD] Weird Numbers  (0) 2021.12.30
[URI] URI Decoding  (0) 2021.12.29
[BOARDCOVER] 게임판 덮기  (0) 2021.12.28
[HOTSUMMER] 에어컨을 끈다고 전력난이 해결될까?  (0) 2021.12.27
Posted by N'
,

[URI] URI Decoding

개발이야기/알고스팟2021. 12. 29. 00:12

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/URI

 

algospot.com :: URI

URI Decoding 문제 정보 문제 URI (Uniform Resource Identifier) is a compact string used to identify or name resources on the Internet. Some examples of URI are below: http://icpc.baylor.edu.cn/ mailto:foo@bar.org ftp://127.0.0.1/pub/linux readme.txt W

www.algospot.com

 

풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue<Character> buffer = new ArrayDeque<>();
        Map<Character, Character> matches = new HashMap<>();
        matches.put('0', ' ');
        matches.put('1', '!');
        matches.put('4', '$');
        matches.put('5', '%');
        matches.put('8', '(');
        matches.put('9', ')');
        matches.put('a', '*');
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            String line = scanner.next();
            for (int i = 0, len = line.length(); i < len; ++i) {
                char c = line.charAt(i);
                int bufferSize = buffer.size();
 
                if (c == '%') buffer.offer(c);
                else if (bufferSize == 1 && c == '2') buffer.offer(c);
                else {
                    if (bufferSize == 2 && matches.containsKey(c)) {
                        buffer.clear();
                        System.out.print(matches.get(c));
                    } else {
                        while (!buffer.isEmpty()) System.out.print(buffer.poll());
                        System.out.print(c);
                    }
                }
            }
 
            System.out.println();
            buffer.clear();
        }
    }
}
 cs



이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[WEIRD] Weird Numbers  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
[BOARDCOVER] 게임판 덮기  (0) 2021.12.28
[HOTSUMMER] 에어컨을 끈다고 전력난이 해결될까?  (0) 2021.12.27
[CONVERT] Conversions  (0) 2021.12.27
Posted by N'
,
Daum / Designed by i2i Labs

티스토리툴바