[백준 | 1475] 방 번호- Java

문제

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

 

입력

---

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

 

출력

---

첫째 줄에 필요한 세트의 개수를 출력한다.

 

 

예제 입력

---

내 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

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

        String roomNumber = br.readLine();

        int[] number = new int[10];
        for (char ch : roomNumber.toCharArray()) {
            number[ch - '0']++;
        }

        number[6] = (number[6] + number[9] + 1) / 2;
        number[9] = 0;

        int max = 0;
        for (int count : number) {
            if (count > max) {
                max = count;
            }
        }

        bw.write(max + "");
        br.close();
        bw.flush();
        bw.close();
    }
}

문제 해결 사고 과정

• 문제 이해: 주어진 문제는 다솜이의 방 번호를 만들기 위해 몇 개의 숫자 세트가 필요한지 최솟값을 구하는 것입니다. 방 번호에 포함된 숫자들을 분석하여 필요한 세트 수를 계산하는 문제로 이해하였습니다.
• 접근 방식: 방 번호의 빈도수를 관리하는 배열을 선언하였고 입력받은 숫자의 빈도를 계산 후 6과 9의 빈도는 하나로 합산하여 하나의 세트로 처리하는 방식으로 접근 하였습니다.

자료 구조 선택 이유

• 선택한 자료 구조: 배열을 사용하여 숫자의 빈도를 카운트 하였습니다.
• 이유 및 장점: 배열은 특정 인덱스에 접근하고 값을 변경할 때 O(1)의 시간 복잡도를 가지므로 메모리 사용이 효율적이며, 각 숫자의 빈도를 빠르게 카운트 할 수 있습니다.

테스트 케이스

•  

시간 및 공간 복잡도 분석

• 시간 복잡도: 배열을 한 번 순회하며 숫자의 빈도를 계산하고, 최댓값을 찾기 위해 다시 한 번 순회하므로 시간 복잡도는 O(N)입니다. 여기서 N은 방 번호의 길이입니다.
• 공간 복잡도: 추가적으로 사용하는 공간은 크기가 10인 배열과 몇 개의 변수뿐이므로 공간 복잡도는 O(1)입니다.