[백준] 1436번 영화감독 숌
https://www.acmicpc.net/problem/1436
문제
숫자 6이 연속으로 3개 이상 포함되는 수 중 가장 작은 수는 666이다.
그렇다면 숫자 6이 연속으로 3개 이상 포함되는 수 중 N번째로 작은 수를 구하는 프로그램을 작성하라.
입력 :
첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력 :
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
나의 답안
처음에 문제를 잘못 읽었다.
6이 연속해서 3개 이상 포함되어야 하는데, 연속하지 않아도 3개 이상 포함되기만 하면
되는 줄 알고 charAt() 메서드를 사용해서 코드를 작성했다...
왜 안되나 계속 들여다 보다가 한참 뒤에 문제를 다시 읽고 원인을 발견했다 ㅋㅋㅋ
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int i = 666;
while (count < n) {
String s = String.valueOf(i);
if (s.contains("666")) count++;
if (count == n) break;
i++;
}
System.out.println(i);
}
}
어떻게 하면 효율적으로 풀까 하다가 생각이 나지 않아 무식하게(?) 작성해봤는데 통과되었다.
count 변수를 이용해 몇 번째 숫자인지를 카운트했고,
666부터 시작해 수를 1씩 올려가며
contains()메서드를 이용해 해당 숫자에 6이 연속 3회 이상 포함되는지 확인했다.
개선 사항
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException{
// Scanner에 비해 처리속도 높음
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int count = 1;
int num = 666;
while (count < n) {
num++; //조건문 말미에 넣는 대신 처음에 넣음으로써 break;문 제거
if (Integer.toString(num).contains("666")) count++;
}
System.out.println(num);
}
}
- Scanner보다 BufferedReader를 통해 입력 받는 것이 처리 속도 면에서 유리
- 문자열 변수를 별도로 생성하는 대신 Integer.toString(num)을 사용
- while문 첫부분에 num++를 넣음으로써 불필요한 break문 제거
※브루트포스 알고리즘:
문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방법
규모가 작거나, 다른 최적화된 알고리즘을 사용하기 어려울 때 유용하다.
장점
1. 확실성: 모든 가능성을 탐색하기 때문에 100%의 정확도를 가짐
2. 단순성: 구현이 쉽고 직관적임
단점
1. 비효율성: 경우의 수가 많아질수록 시간이 오래 걸림
2. 고비용: 데이터소모가 매우 많아짐
브루트포스 알고리즘을 쓰더라도, 확실하게 정답이 아닌 것들은 최대한
제거해주는 코딩을 하는 것이 바람직할 것으로 보인다!