[알고리즘] 바킹독 실전 알고리즘 0x03 배열 연습문제

이 글은 바킹독님의 실전 알고리즘 커리큘럼을 보면서 푼 문제를 작성한 글입니다.
링크 : https://blog.encrypted.gg/927

[실전 알고리즘] 0x03강 - 배열

 

[#10808] 알파벳 개수 

📎https://www.acmicpc.net/problem/10808

10808번: 알파벳 개수

 

💡 풀이

단순하게 알파벳의 개수가 담긴 배열을 선언해주고 들어온 문자열의 한 글자씩 비교해 - 'a'를 해주면 a는 0 부터 z 는 25의 인덱스 번호를 구할 수 있다. 해당 알파벳이 들어오면 알파벳 인덱스의 값을 1 증가시켜서 전체 각 알파벳이 몇 번 들어왔는지 구할 수 있다.

 

import java.util.Scanner;

public class Baekjoon10808 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();

        int[] alphabet = new int[26];

        for(int i = 0; i < input.length(); i++) {
            int idx = input.charAt(i) - 'a';
            alphabet[idx]++;
        }

        for(int i = 0; i < alphabet.length; i++) {
            System.out.printf("%d ", alphabet[i]);
        }
    }
}

 

연습문제 2

주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.

입출력 예시
func2({1, 52, 48}, 3) = 1
func2({50, 42}, 2) = 0;
func2({4, 13, 63, 87}, 4) = 1

 

💡 풀이

이중 for문을 이용하여 두 개의 숫자 합이 100이 되면 1을 반환해주고, for문을 전부 다 돌아도 두 숫자의 합이 100이 되는 경우가 없으면 0을 반환해주도록 풀었다.

 

public class ArrayExam2 {
    public static void main(String[] args) {
        int[] arr = {4, 13, 63, 87};
        int N = 4;
        System.out.println(func2(arr, N));
    }
    public static int func2(int[] arr, int N) {
        for(int i = 0; i < N - 1; i++) {
            for(int j = i + 1; j < N; j++) {
                if(arr[i] + arr[j] == 100) {
                    return 1;
                }
            }
        }
        return 0;
    }
}

 

📌 개선

하지만 위 코드의 시간복잡도는 O(N^2) 으로 이 문제를 O(N)으로 해결할 수 있는 방법이 있다. 그 방법은 0-99까지 100개의 요소가 담긴 배열을 선언하고 for문으로 한 번만 arr의 원소를 순회하면서 100 - i 값이 이전에 나온 적이 있는지 체크하고, 나온 적이 없다면 해당 위치의 값을 1로 변경한 후 반복하면 O(N)으로 이 문제를 해결할 수 있다.

 

public static int Solution2(int[] arr, int N) {
        int[] numbers = new int[100];
        for(int i = 0; i < arr.length; i++) {
            if(numbers[100 - arr[i]] == 1) return 1;
            else numbers[arr[i]] = 1;
        }

        return 0;
    }

 

[#2577] 숫자의 개수

📎https://www.acmicpc.net/problem/2577

2577번: 숫자의 개수

 

💡 풀이

세 입력을 곱한 값을 변수로 넣어주고 그 변수를 10으로 계속 나누면서 마지막 한 자리가 몇인지에 따라 0~9까지 담긴 배열에 그 값이 등장하면 하나씩 증가하도록 풀었다.

 

import java.io.*;

public class Baekjoon2577 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] numCount = new int[10];
        int multiNum = Integer.parseInt(br.readLine()) * Integer.parseInt(br.readLine()) * Integer.parseInt(br.readLine());
        while (multiNum > 0) {
            numCount[multiNum % 10]++;
            multiNum /= 10;
        }
        for(int i = 0; i < 10; i++) {
            bw.write(numCount[i] + "\n");
        }
        bw.close();
    }
}

 

[#1475] 방 번호

📎https://www.acmicpc.net/problem/1475

1475번: 방 번호

 

💡 풀이

0부터 8까지의 배열을 선언하고 자릿수를 10으로 나누면서 한자리씩 배열에다가 카운트를 해주고, 9가 들어올 경우에는 6에다가 카운트를 해줬다. 모든 자릿수를 넣고 난 뒤에는 6 자리에 Math.round 메소드를 사용해서 2로 나눈 값을 반올림 해서 다시 저장하고 배열을 정렬한 뒤 배열의 맨 뒤에 있는 값 (가장 큰 값)을 출력하도록 풀었다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Baekjoon1475 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] numCount = new int[9];
        int inputNum = sc.nextInt();
        while (inputNum > 0) {
            if(inputNum % 10 == 9) numCount[6]++;
            else numCount[inputNum % 10]++;
            inputNum /= 10;
        }
        numCount[6] = (int) Math.round(numCount[6] / 2.0);
        Arrays.sort(numCount);
        System.out.println(numCount[8]);
    }
}

 

[#3273] 두 수의 합

📎 https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

💡 풀이

위에 두 수의 합이 100인 문제 중 개선된 코드와 비슷하게 풀었다. 체크할 숫자 변수들을 문제에서 제시된 범위로 배열을 선언해주고 입력된 숫자들을 for문을 돌면서 x 보다 들어온 숫자값이 작고, x - n 이 이전에 들어온 적이 있는지 체크하는 형식으로 풀었다.

 

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

public class Baekjoon3273 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int sizeN = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int xNum = Integer.parseInt(br.readLine());
        int[] checkNum = new int[1000000];
        int count = 0;

        for(int i = 0; i < sizeN; i++) {
            int n = Integer.parseInt(st.nextToken());
            if(xNum > n && checkNum[xNum - n] == 1) {
                count++;
            }
            checkNum[n] = 1;
        }
        bw.write(String.valueOf(count));
        bw.close();
    }
}