[Algorithm] 07.코딩 테스트를 위한 알고리즘 공부

in Study on Algorithm

뒤집은 소수

설명

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요.

예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다.

첫 자리부터의 연속된 0은 무시한다.

입력

첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.

각 자연수의 크기는 100,000를 넘지 않는다.

출력

첫 줄에 뒤집은 소수를 출력하되, 입력된 순서대로 출력한다.

예시 입력 1

9

32 55 62 20 250 370 200 30 100

예시 출력 1

23 2 73 2 3

문제 해결을 위해 생각한 방법

  1. 입력받은 배열 길이만큼 for문 수행

  2. 배열 요소 0부터 끝까지 접근해 숫자 가져오고 역으로 뒤집기

    1. 뒤집는 방법 :

      1. 내가 생각한 방법 - StringBuffer의 reverse를 사용 -> 수학적이지 못한것 같아 검색

      2. 찾은 방법 - 주어진 수를 나누고 나눠서 나머지 값을 얻는 방식으로 1의자리 숫자를 구하고, 거기에 주어진 수의 자리수만큼 10을 곱해줘서 더해줘서 역 숫자를 만드는 방식

  3. 뒤집은 숫자가 소수인지 체크

    1. 체크하는 방법 :

      1. 내가 생각한 방법1 - 2부터 해당 숫자 전의 숫자까지 반복해서 나누면서 나누어 떨어지는지 확인

      2. 생각한 방법2 - 에라토스테네스의 체 활용

  4. 소수로 확인된 숫자를 정답 배열에 추가하기

생각한 방법 1->2_2->3_1->4 로 짜본 코드

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

public class Main {

    public int[] solution(int[] input) {
        List<Integer> answer = new ArrayList<>();

        for(int i = 0; i < input.length; i++) {
            int number = input[i];
            int reverseNumber = 0;
            while(number != 0) {
                reverseNumber = reverseNumber * 10 + number % 10;
                number = number / 10;
            }
            boolean divided = false;
            for(int j = 2; j < reverseNumber; j++) {
                if(reverseNumber % j == 0) {
                    divided = true;
                    break;
                }
                divided = false;
            }
            if (!divided && reverseNumber!= 1) {
                answer.add(reverseNumber);
            }
        }
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numberSize = Integer.parseInt(br.readLine());
        int[] input = new int[numberSize];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberSize; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        int[] answer = main.solution(input);
        for (int i : answer) {
            System.out.print(i + " ");
        }
    }
}

TimeLimitException이 나올줄 알았는데 성공했다. Scanner를 BufferedReader로 바꿔서 그런것 같다.

※ 1을 결과값에서 제외시키는 방식을 더 세련되게 할수는 없었을까 싶다.

BufferedReader공부

내 코드에서 발생한 문제의 원인을 알게 해 준 글 https://www.acmicpc.net/board/view/9744

생각한 방법 1->2_2->3_2->4 로 짜본 코드

: 3_2 를 진행하기 위해 떠올린 방법

  1. 입력받은 배열 만큼의 크기를 갖는 int형 배열 선언

  2. 입력받은 배열을 0부터 끝 인덱스까지 반복하면서 해당 요소의 숫자를 뒤집기

  3. 뒤집은 숫자를 1의 배열에 할당

  4. 뒤집은 숫자 중 가장 큰 숫자를 bigNumber라는 int형 변수에 할당

  5. 반복문이 끝나면 bigNumber만큼의 크기를 갖는 int형 배열 primeNumberList를 선언

  6. 1부터 bigNumber까지의 소수를 구하기 위해 primeNumeberList에 이전에 했던 에라토스테네스의 체 방식으로 값을 입력

  7. 값이 입력된 primeNumeberList를 반복하면서 소수이면서, 1의 배열에 들어가 있는 입력받아 뒤집은 숫자가 맞으면 답이 될 ArrayList인 answer에 add

이렇게 진행했는데 boolean contains = Arrays.asList(reverseNumberList).contains(i + 1); 를 조회해 보니 reverseNumberList가 입력받은 숫자값을 안갖고 있다고 나온다.

뭐가 잘못된건지!?

검색을 해봤다.

-> int형 배열을 Arrays.asList로 변환시키려고 하면 문제가 발생한다

Arrays.asList() 메소드는 primitive 타입을 Wrapper 클래스로 형변환해주지 않는다고 한다. 그럼 무엇으로 변환해 주는지 궁금해서 인텔리제이에서 Arrays.asList(reverseNumberList) 값을 Cmd+Option+v로 변수화 해보려고 하니 List<int[]> ints = Arrays.asList(reverseNumberList); 와 같이 아주 이상한 형식으로 변환해 주는 것을 볼 수 있었다.

int형 배열을 ArrayList로 변환하고자 할 때

다양한 변환 방법에 대해 안내되어 있는 글 https://www.techiedelight.com/ko/convert-int-array-list-integer/

contains메서드를 사용하는 방식 외에 주어진 배열에 특정 값이 존재하는지 확인하는 방법들

참고한 글 https://developer-talk.tistory.com/666

수정한 코드 : 새로운 문제 발견

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

    public int[] solution(int[] input) {
        List<Integer> answer = new ArrayList<>();
        int[] reverseNumberList = new int[input.length];
        int bigNumber = 0;

        for(int i = 0; i < input.length; i++) {
            int number = input[i];
            int reverseNumber = 0;
            while(number != 0) {
                reverseNumber = reverseNumber * 10 + number % 10;
                number = number / 10;
            }
            if (bigNumber < reverseNumber) {
                bigNumber = reverseNumber;
            }
            reverseNumberList[i] = reverseNumber;
        }
        int[] primeNumberList = new int[bigNumber];


        for(int i = 1; i < bigNumber; i++) {
            for(int j = 0; i + ((i + 1) * j) < bigNumber; j++ ) {
                primeNumberList[i + ((i + 1) * j)]++;
            }
        }

        for(int i = 1; i < bigNumber; i++) {
            List<Integer> reverseIntegerNumberList = Arrays.stream(reverseNumberList)
                .boxed()
                .collect(Collectors.toList());
            if((primeNumberList[i] == 1) && (reverseIntegerNumberList.contains(i + 1))) {
                answer.add(i + 1);
            }
        }
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numberSize = Integer.parseInt(br.readLine());
        int[] input = new int[numberSize];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberSize; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        int[] answer = main.solution(input);
        for (int i : answer) {
            System.out.print(i + " ");
        }
    }
}

27

469 84 8851 189 69 1210 682 57 6217 484 8 3590 662 36 8275 887 17 1254 462 67 8969 141 70 5603 958 100 3843

값이 입력되면

953 71 7 859

이런 값이 출력되어야 정답인데

7 71 859 953

이렇게 입력받은 순서가 아니라 앞에서부터 출력해 주는 것을 볼 수 있었다.

primeNumberList를 1부터 bigNumber까지의 소수를 확인해 주는 에라토스테네스의 체로 만들어서 그렇다.

문제 해결을 위해 생각한 방법

  1. answer를 List대신 Map<Integer, Integer>로 만들어서 에라토스테네스의 체의 숫자를 추출했을 때 해당 숫자가 reverseNumberList의 몇 번째 요소에 해당되는지를 체크해서 <순서, 값> 쌍으로 put한다.

특정 값이 배열의 몇번째 요소에 해당되는지 확인하는 방법 https://www.techiedelight.com/ko/find-index-element-array-java/

  1. Map의 요소들을 int형 배열로 만들어 줄 때 stream에서 순서 값 부분을 작은 수에서 큰 수 순서로 정렬해서 반환해 준다.

Map을 List로 바꿔주는 방법 https://www.techiedelight.com/ko/find-index-element-array-java/

Map을 List로 바꿀 때 Map의 키값의 오름차순으로 정렬하는 방법 : 시도하다 도저히 떠오르지 않아서 GPT에게 물어보았다

Map의 EntrySet을 가져옵니다. 그리고 Collections.sort() 메서드를 사용하여 EntrySet을 “순서(Integer 타입)”의 값에 따라 오름차순으로 정렬합니다. 정렬된 EntrySet에서 값을 추출하여 List에 추가한 후, 원하는 대로 처리할 수 있습니다.

GPT가 알려준 대로 했더니 잘 되었다! 그런데..

또 발생한 문제! 23 2 73 2 3이 출력되어야 하는데 23 2 73 3이 출력되었다. -> 1~뒤집은 수 중 가장 큰 수 까지의 에라토스테네스의 체에서 뒤집은 수 리스트에 있는 숫자를 체크할 때 아래처럼 진행을 하는데

    int index = IntStream.range(0, reverseNumberList.length)
    .filter(x -> target == reverseNumberList[x])
    .findFirst()
    .orElse(-1);

findFirst()로 맨 앞에있는 인덱스를 반환해 주기 때문에 두번째 2를 저장하지 못했다.

다시 GPT에게로…

findFirst()는 스트림에서 첫 번째 요소를 찾아옵니다. 두 번째로 찾아지는 인덱스를 조회하고 싶다면, findFirst() 대신 filter()를 사용하여 해당 조건을 만족하는 모든 요소를 필터링한 후, findFirst()를 사용할 수 있습니다. 이렇게 하면 첫 번째와 두 번째로 찾아지는 인덱스를 모두 얻을 수 있습니다.

GPT없었으면 어떻게 살았을까🥹

최종 성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    public int[] solution2(int[] input) {
        List<Integer> answer = new ArrayList<>();
        Map<Integer, Integer> answerMap = new HashMap<>();
        int[] reverseNumberList = new int[input.length];
        int bigNumber = 0;

        for (int i = 0; i < input.length; i++) {
            int number = input[i];
            int reverseNumber = 0;
            while (number != 0) {
                reverseNumber = reverseNumber * 10 + number % 10;
                number = number / 10;
            }
            if (bigNumber < reverseNumber) {
                bigNumber = reverseNumber;
            }
            reverseNumberList[i] = reverseNumber;
        }
        int[] primeNumberList = new int[bigNumber];

        for (int i = 1; i < bigNumber; i++) {
            for (int j = 0; i + ((i + 1) * j) < bigNumber; j++) {
                primeNumberList[i + ((i + 1) * j)]++;
            }
        }

        for (int i = 1; i < bigNumber; i++) {
            List<Integer> reverseIntegerNumberList = Arrays.stream(reverseNumberList)
                .boxed()
                .collect(Collectors.toList());
            boolean contains = Arrays.asList(reverseNumberList).contains(i + 1);
            if ((primeNumberList[i] == 1) && (reverseIntegerNumberList.contains(i + 1))) {
                int target = i + 1;

                List<Integer> indexes = IntStream.range(0, reverseNumberList.length)
                    .filter(x -> target == reverseNumberList[x])
                    .boxed()
                    .collect(Collectors.toList());

                for (int j = 0; j < indexes.size(); j++) {
                    answerMap.put(indexes.get(j), i + 1);
                }
            }
        }

        List<Map.Entry<Integer, Integer>> tmpList = new ArrayList<>(answerMap.entrySet());

        Collections.sort(tmpList, new Comparator<Entry<Integer, Integer>>() {
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getKey().compareTo(o2.getKey());
            }
        });

        for (Entry<Integer, Integer> entry : tmpList) {
            answer.add(entry.getValue());
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numberSize = Integer.parseInt(br.readLine());
        int[] input = new int[numberSize];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberSize; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        int[] answer = main.solution2(input);
        for (int i : answer) {
            System.out.print(i + " ");
        }
    }
}

수행시간을 보면 1->2_2->3_1->4 로 진행한 코드는 290ms에서 304ms사이의 값을 갖는데, 1->2_2->3_2->4 로 진행한 코드는 328ms에서 921ms사이의 값을 갖는다. 나는 에라토스테네스의 체 방식을 활용한 후자가 더 괜찮은 코드일거라고 생각했는데, 막상 코드를 진행하는것도 수행시간 측면에서도 썩 만족스럽지 못했다.

강사님의 풀이 방법을 보기로 했다.

강사님 풀이 방식

강사님께서는 내가 생각한것과 완전히 다른 방식으로 접근하셨는데, 굳이 따지자면 1->2_2->3_1->4 에 더 가깝다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
   public boolean isPrimeNumber(int number) {
        boolean isPrimeNumber = true;
        if (number == 1) {
            isPrimeNumber = false;
        }
        for(int i = 2; i < number; i++) {
            if (number % i == 0) {
                isPrimeNumber = false;
            }
        }
        return isPrimeNumber;
   }

    public List<Integer> teacherSolution(int[] input) {
        List<Integer> answer = new ArrayList<>();

        for (int i = 0; i < input.length; i++) {
            int given = input[i];
            int number = 0;
            while(given > 0) {
                int tmp = given % 10;
                number = number * 10 + tmp;
                given = given / 10;
            }
            if (isPrimeNumber(number)) {
                answer.add(number);
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numberSize = Integer.parseInt(br.readLine());
        int[] input = new int[numberSize];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberSize; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> answer = main.teacherSolution(input);
        for (int i : answer) {
            System.out.print(i + " ");
        }
    }
}

우선 solution에서 값을 만들어줄 때 나처럼 int형 배열에 집착하지 않으시고 ArrayList로 반환하신것부터 달랐고, 소수인지 체크하는 메서드를 따로 빼신것도 인상적이었다. 가독성도 더 좋아지고 문제 풀기도 더 수월한 느낌이었다.

소수를 구하는 방법은, 굳이 에라토스테네스의 체를 만들어서 하지 않고 내가 1->2_2->3_1->4

에서 했던것처럼 2부터 해당 숫자 전까지 1씩 증가시키면서 나누다가 나누어지지 않는 경우에 소수로 인정하는 방식을 선택하셨다.

느낀점

때로는 단순한 방법이 더 빠르고 좋은 방법일 수 있다는 것을 알게 되었다. 그래도 복잡한 방법으로 시도하며 알게 된 여러가지 java문법들은 잘 기억해 놓으면 데이터를 가공할 때 잘 활용할 수 있을것 같다는 생각이 들었다.


© 2021.1. by jean202

Powered by jean202