Java - HashSet & 정렬 (1)

 

HashSet

HashSet은 Set 인터페이스에서 지원하는 구현 클래스이다.

 

때문에 Set 의 성질을 그대로 상속받는다는 것이 특징이다.

HashSet 의 성질 

• 중복된 값을 허용하지 않는다.
• 저장한 순서가 보장되지않는다.
• null값 허용
• 요소 추가는 add() 메소드가 있다.
  • 입력되는 값이 HashSet 내부에 존재하지 않는다면 그 값을 HashSet에 추가하고 true 반환
  • HashSet 내부에 존재한다면 false를 반환한다.
• 요소 삭제는 remove(value), clear();

문제 

백준 11656 : 접미사 배열

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

 

입력된 문자열을 접미사 배열로 변환하여 오름차순으로 정렬 -> 출력 수행한다. 

1. 먼저, 주어진 문자열을 입력받는다.
2. 입력된 문자열을 각 문자별로 배열에 저장. ( toCharArray() 메서드사용 )
3. 문자열의 길이에 해당하는 배열 생성. ( 문자열의 접미사를 저장 )

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

public class Main {
    public static String[] arr;

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

        // 문자열 입력받기
        String inputString = br.readLine();

        // 입력된 문자열을 char 배열로 변환
        char[] charArray = inputString.toCharArray();

        // 입력된 문자열 길이만큼의 String 배열 초기화
        arr = new String[charArray.length];

        // 각 접미사를 배열에 저장
        for (int i = 0; i < charArray.length; i++) {
            StringBuilder temp = new StringBuilder();
            // 접미사를 생성하여 temp에 저장
            for (int j = charArray.length - 1 - i; j < charArray.length; j++) {
                temp.append(charArray[j]);
            }
            arr[i] = temp.toString();
        }

        // 접미사 배열을 오름차순으로 정렬
        Arrays.sort(arr);

        // 정렬된 접미사 배열 출력
        for (String suffix : arr) {
            System.out.println(suffix);
        }
    }
}

처음에 접미사를 배열에 저장할때 냅다 거꾸로 문자를 가져와서 append 하고 바로 제출했더니,, 푸하하 ,,, 마지막 문자부터 하나씩(코드기준 i 만큼) 줄여가면서 다시 append 해줬다. temp는 StringBuilder니까 toString()메소드를 이용해서 arr배열에 저장한다.  

 

백준 1764 : 듣보잡

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

 

문제이름 웃겨서 풀었다. 

 

사실 안웃기다.

 

듣도 못한 사람 수가 N이고, 보도 못한 사람 수는 M 이다. 

N, M 둘다 해당되는 사람을 출력하면 된다. 

사전순으로 출력하라 했으므로 배열을 정렬시킨 후 대조하면서 answer 배열에 저장해야겠다고 생각했다. 

 

[시간초과]

public class Main {
    public static String[] arrN;
    public static String[] arrM;
    public static int N,M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arrN = new String[N];
        arrM = new String[M];
        ArrayList<String> answer = new ArrayList<>();

        //배열 입력받기
        for(int i=0;i<N;i++){
            arrN[i]=br.readLine();
        }

        for(int i=0;i<M;i++){
            arrM[i]=br.readLine();
        }
        Arrays.sort(arrN);
        Arrays.sort(arrM);

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arrN[i].equals(arrM[j])){
                    answer.add(arrN[i]);
                    break;
                }
            }
        }

        //정답
        System.out.println(answer.size());
        for(String word:answer){
            System.out.println(word);
        }

    }
}

 

이게 처음 생각한 코드인데 시간초과떴다.

이유는 두 배열을 이중 루프로 순회하며 공통 요소를 찾기 때문이다..

이 방법은 시간 복잡도가 O(N×M)이며, 두 배열의 크기가 클 경우 매우 비효율적이다.

이 문제를 효율적으로 해결하기 위해 정렬된 배열을 이용한 이분 탐색이나 해시셋(HashSet)을 사용하는 것이 좋다고 한다.

해시셋을 사용하면 시간 복잡도를 O(N+M)으로 줄일 수 있다.

 

[정답 :  시간복잡도: O(N+M) ]

public class Main {
    public static String[] arrN;
    public static String[] arrM;
    public static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arrN = new String[N];
        arrM = new String[M];

        Set<String> setN = new HashSet<>(); 
        ArrayList<String> answer = new ArrayList<>();

        // 배열 N 입력받기
        for (int i = 0; i < N; i++) {
            arrN[i] = br.readLine();
            setN.add(arrN[i]); // 배열 N의 요소를 해시셋에 추가
        }

        // 배열 M 입력받기
        for (int i = 0; i < M; i++) {
            arrM[i] = br.readLine();
            if (setN.contains(arrM[i])) { // 배열 M의 요소가 해시셋에 있는지 확인
                answer.add(arrM[i]);
            }
        }

        // 정답 정렬
        Collections.sort(answer);

        // 정답 출력
        System.out.println(answer.size());
        for (String word : answer) {
            System.out.println(word);
        }
    }
}

HashSet을 만들고 배열 요소를 HashSet에 추가한다.

다른 배열 M의 요소가 HashSet에 있는지 확인하고 존재한다면 answer 배열에 넣어준다.

answer 배열을 오름차순으로 정렬하고 출력해주면 끝

 

백준 1946 : 신입 사원

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

 

신입 사원이 되고자하는 염원을 담아 풀어봤다. 

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하니까

성적 순위가 1이있으면 무조건 합격이고, 첫번째 요소만 비교했을때 첫번째 요소보다 작은 배열들과 두번째 요소를 비교해야 겠다고 생각했다. 

두번째 요소가 다른 두번째 요소보다 작다면 answer++ (햅객!!!)

크면,, 뜨거운 합격,,,!

 

[시간초과]

public class Main {
    public static int T, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        T = Integer.parseInt(st.nextToken());
        HashSet<Integer> answerArray = new HashSet<>();
//        ArrayList<Integer> answerArray = new ArrayList<>();

        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine()); // 배열 크기 입력받기
            int[][] arr = new int[N][2]; // 2차원 배열 선언

            // 배열 요소 입력받기
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
            }

            // 첫 번째 요소를 기준으로 정렬하기
            Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));


            // 두 번째 요소를 기준으로 합격 여부 판단
            for (int i = 1; i < N; i++) {
                for (int j=0;j<i;j++){
                    if (arr[i][1] < arr[j][1]) { // 현재 사람의 두 번째 요소가 작으면 합격
                        answerArray.add(arr[i][1]);
                    }
                }
            }
            System.out.println(answerArray.size());
        }
    }
}

 

 

[시간초과2 ]

public class Main {
    public static int T, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        T = Integer.parseInt(st.nextToken());

        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine()); // 배열 크기 입력받기
            int[][] arr = new int[N][2]; // 2차원 배열 선언

            // 배열 요소 입력받기
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
            }

            // 첫 번째 요소를 기준으로 정렬하기
            Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
            Boolean pass;
            int answer = 1;

            // 두 번째 요소를 기준으로 합격 여부 판단
            for (int i = 1; i < N; i++) {
                pass=true; //초기화
                for (int j=0;j<i;j++){ //앞에 모든 수들보다 두번째 요소가 작아야 합격
                    if (arr[i][1] > arr[j][1]) {
                        pass=false;
                        break;
                    }
                }
                //모든 조건 충족시 합격
                if(pass){
                    answer++;
                }

            }
                System.out.println(answer);
        }
    }
}

 

시간 초과난 나의 귀여운 코드를 살펴보자. 이중for문의 권위자 답게 이중 for 문을 사용한 모습이다. 

지금 시간 초과가 나고 있는건 각 테스트 케이스마다 모든 지원자들을 비교해서 합격 여부를 판단하고 있어서 일거다..

이중for문으로 모든 지원자수를 비교하기 때문에 지금 시간 복잡도는 O(N^2)이다.

 

[정답 : 시간복잡도 : O(NlogN)]

public class Main {
    public static int T, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        T = Integer.parseInt(st.nextToken());

        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine()); // 배열 크기 입력받기
            int[][] arr = new int[N][2]; // 2차원 배열 선언

            // 배열 요소 입력받기
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
            }

            // 첫 번째 요소를 기준으로 정렬하기
            Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

            int answer = 1; // 첫 번째 학생은 항상 합격
            int minSecond = arr[0][1]; // 현재까지의 합격자 중 가장 작은 두 번째 요소

            // 두 번째 요소를 기준으로 합격 여부 판단
            for (int i = 1; i < N; i++) {
                if (arr[i][1] < minSecond) { // 현재 학생의 두 번째 요소가 최소값보다 작으면 합격
                    answer++;
                    minSecond = arr[i][1]; // 최소값 갱신
                }
            }

            System.out.println(answer);
        }
    }
}

 

시간 복잡도가 O(NlogN)이 되는 이유는 주어진 코드에서 배열을 정렬하는 부분 때문이다.

여기서 사용된 Arrays.sort() 메서드는 대부분의 경우에는 퀵 정렬과 유사한 내부 알고리즘을 사용하며, 이 경우 평균적으로 시간 복잡도가 O(NlogN)이다.

따라서 배열의 크기가 N일 때, 정렬하는데 소요되는 시간은 O(NlogN)이 되고

이후에는 단순한 반복문을 사용하여 합격 여부를 판단하므로, 전체적인 시간 복잡도는 정렬에 의해 결정된다.

따라서 주어진 코드의 전체적인 시간 복잡도는 O(NlogN)이 된다.

 

무분별한 이중 for 문을 멈춰주세욧..!!