문제 url:
영화감독 숌
문제:
🤔 문제 알아보기
영화감독의 특이한 취향 덕분에, 어떤 수에 6이 적어도 3개 이상 연속으로 들어가야 한다.
아래 예제 입력을 보면, 2번째 일때는 1666 3번째 일때는 2666 이런 형태로 되는 것을 볼 수 있다. 그렇게 해서 N번째 숫자를 출력하는 문제로
문제에서 N번째 영화는 N번째로 작은 수와 같다고 한다.
즉, 우리는 숫자에 666이 연속적으로 들어갈 때마다 카운트를 해서, 총 N번째 까지 카운트를 반복하는 로직을 생각할 수 있다.
그래서 해당 문제는 브루트포스 알고리즘로 분류할 수 있다.
아래 코드와 함께 리뷰를 살펴보며 좀 더 깊게 알아보도록 하자
🐱👤 실제 코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// N이 1일 경우 666을 바로 출력
if (N == 1) {
System.out.println(666);
return;
}
br.close();
// N번째 값을 구하기 위해 count 변수 정의
// 해당 변수가 N과 같아지면 break;
// 이미 666으로 1을 카운트 했기 때문에 1로 초기화
int count = 1;
// 해당 값은, 666 이후 첫 번째로 666이 연속적으로 나오는 수
int num = 1666;
while(true) {
// contains를 사용하기 위해 문자열로 캐스팅
String str_num = String.valueOf(num);
if(str_num.contains("666")) {
count++;
if(count == N) {
break;
}
}
num++;
}
System.out.println(num);
}
}
코드의 로직은 간단하다.
N번째 숫자를 구하기 위한 count변수를 정의하고, count가 N과 같을 때까지 반복후 해당하는 num변수를 출력하면 되는 것이다.
여기서 중요한 로직은 아래 로직이다.
String str_num = String.valueOf(num);
if(str_num.contains("666")) {
count++;
if(count == N) {
break;
}
}String.valueOf() 메서드는 Object값을 문자열로 변환시켜주는 메서드로,
숫자에 666이 포함되었는지를 확인하기 위해 int형을 문자열로 변환하였다.
그 후, contains()메서드를 사용하였는데, 해당 메서드를 설명하면
🎄 contains()
- boolean contains(CharSequence s)
- contains()메서드는 대상 문자열에 특정 문자열이 포함되어 있는지 없는지 확인
- 존재한다면 true / 존재하지 않는다면 false를 반환
- 파라미터로 들어오는 값에 대해서 대/소문자를 구분한다.
- 또한 공백값도 체크하기 때문에 유의해야 한다.
🤢 코드 리팩토링
처음에는 contains()를 몰라서 풀지 못하다가 타 블로그를 보면서 알게 된 메서드이다.
그리고 다른 방법이 있는지 둘러보던 중 브루트 포스를 사용하지 않는 방법을 배우게 되면서 이를 연습해보고자 한다.
해당 방법은 구간을 나누어 count를 하는 방식으로 브루트 포스를 하지 않고, 계산하는 방식이다.
먼저 666이 연속적으로 들어간 숫자들 중, 4자리(천의 자리)까지 나타내면
666, 1666, 2666, 3666, 4666, 5666, (6660, 6662...6669), 7666, 8666, 9666 값이 존재한다.
여기서 6660로 시작하는 값을 주목하면, 5666 다음으로 6666이 아닌, 값 사이에 나타낼 수 있는 작은 값부터 나타내야 하기에 6660부터 시작한다.
5자리(만의 자리) 역시 똑같이 계산한다.
10666, 11666, 12666, 13666, 14666, 15666, (16660, 16661....16669), 17666, 18666, 19666
20666, 21666, 22666, 23666, 24666, 25666, (26660, 26661....26669), 27666, 28666, 29666
또한, 5자리부터는 66600의 숫자고 계산할 수 있는데, 이 또한
66600, 66601, 66602, .... 66699까지 계산을 해준 다음 70666으로 넘어가면 된다.
그럼, 알고리즘을 풀어보도록 하자.
첫 번째는 666 두 번째는 1666으로 666앞에 붙일 수 있는 1을 prev_digit(앞에 부튼 자리수)로 지칭하고, 이를 prev_digit++를 진행하고자 한다.
그 후 prev_digit이 6이 되었을때, 6660, 6661... 6669까지 계산한 후 해당 반복문이 끝나면 다시 prev_digit++하여 7부터 시작하도록 한다.
이를 반복해서 6이 아닌, 66이 되었을 때는 66600, 66601... ~ 66699(0~99 총 100번) 반복하며 count++를 진행해준 다음 다시 prev_digit++하여 진행한다.
해당 반복이 count == N이 되었을 때, 즉 666이 나온 횟수(count)가 N(N번째)와 같을 때 해당 값을 출력하면 되는 것이다.
설명이 매끄럽지 않지만, 코드를 보면서 또 설명해보겠다.
코드를 연습한 결과.. 잘 나오지 않았다 (이해도 못한 것 같다.) 그래서
아래의 참고 자료에 있는 링크를 확인하면 더 좋을 듯하다.
💜 참고자료
[백준] 1436번 : 영화감독 숌 - JAVA Stranger's LAB <- 항상 감사합니다 ^^
