문제
다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.
다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 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)입니다.
'PS > 백준' 카테고리의 다른 글
| [백준 | 1406] 에디터 - Java(Linked List 사용) (0) | 2024.08.22 |
|---|---|
| [백준 | 1158] 요세푸스 문제 - Java (LinkedList 사용) (0) | 2024.08.22 |
| [백준 | 1919] 애너그램 만들기 - Java (0) | 2024.08.21 |
| [백준 | 2577] 숫자의 개수 - Java (0) | 2024.08.21 |
| [백준 | 10845] 큐- Java (0) | 2024.08.16 |
