[알고리즘 떠먹여 주는 남자] 백준 1436 - 영화감독 숌

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

Sup lads!

이번에 다뤄 볼 알고리즘은 역시 브루트포스 타입의 문제 '영화감독 숌' 입니다. 문제 자체의 난이도는 그다지 높지 않았으나, 제출 결과가 사실 만족스럽지는 않습니다.. 다른 알고리즘 제출 결과들과는 달리 메모리 사용량과 시간이 너무 오래 걸려서인데요. 그래서 다른 분들은 어떤 결과를 얻으셨나 확인하기 위해 '맞힌 사람' 리스트를 확인 해 보았더니 51등에 랭크 되어 있더군요. 사실 제 풀이 방식이 엄청 메모리 관리 측면에서 효율적일 거라고 생각하지는 않았습니다만 그래도 생각보다 높게 나온 것 같아서 조금 놀란 감이 없지 않아 있습니다.

 

그래서 더 효율적으로 문제를 해결할 수 있는 방법이 없나 고민하고 있습니다. 혹시라도 찾게 된다면 업데이트 하도록 하겠습니다.

 

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

1666

예제 입력 2 복사

3

예제 출력 2 복사

2666

예제 입력 3 복사

6

예제 출력 3 복사

5666

예제 입력 4 복사

187

예제 출력 4 복사

66666

예제 입력 5 복사

500

예제 출력 5 복사

166699

문제 풀이

처음엔 저게 무슨 말인가 싶었지만 다시 읽어보니 이해할 수 있었습니다. 간략히 설명 해 보자면:

• 숌 감독은 세상의 종말 영화 시리즈를 만드는데, 시리즈의 넘버엔 무조건 666 이 들어가야 한다.
• 주어진 N 번째 시리즈의 넘버를 구하여라.

위의 말을 해석 해 보면 이러한 순서를 얻을 수 있습니다.

666, 1666, 2666, ....., 5666, 6660, 6661, 6662, ..., 6669, 7666, 8666, ....

예제에서 조금 더 힌트를 줄 수도 있었을 거 같은데.. 헷갈리게 하려는 의도가 담겨있을 지도 모른다는 킹리적 갓심을 뒤로 한 채, 바로 코드로 넘어가 보겠습니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = Number(fs.readFileSync(filePath).toString().trim());

let count = 0;
let currentNumber = 0;

while (true) {
  currentNumber++;
  if (!currentNumber.toString().includes('666')) continue;
  count++;
  if (count === input) {
    console.log(currentNumber);
    break;
  } 
}

위에서도 언급 하였듯이, 메모리와 시간이 다른 알고리즘 풀이에 비해 높게 나온 것 같아서 변수 선언도 최대한 줄이고 코드 라인도 줄였습니다. 처음에는 90몇등? 정도였던 것 같은데, 위의 방식으로 코드를 바꾸고 나서 30등 대로 올라갔습니다 ㅎㅎ.. 하지만 아직 만족스럽지 않다는 ㅠ

 

while 문을 사용하여 무한 루프를 돌리고, 만약 현재 숫자 (currentNumber) 가 666을 포함하고 있다면, count 값을 하나씩 올려주면서, 카운트 변수의 값이 input 값과 동일할 때 현재 숫자를 출력해주고 무한 루프를 탈출하는 방식입니다.

제출 결과

현재 등수

이상한 점은 위 제출 결과에서 두 번째와 네 번째의 코드가 똑같습니다. 그럼에도 메모리와 소요 시간이 다르다는.. ㅎㅎ 아무튼 문제 자체의 난이도는 어렵지 않았습니다.

 

마무으리

사실 이 문제 전에 체스판 다시 그리기 문제가 있었는데 그 문제는 더 복잡해 보여서 일단 패스하고 이 문제부터 풀었습니다. 아마 내일 다시 도전 해 보지 않을까 싶습니다. 오늘도 빼먹지 않고 알고리즘 한 문제를 풀었네요 ㅎㅎ 뿌듯합니다. 앞으로도 웬만하면 쉬운 문제라도 하루에 하나 정도씩 꼬박 꼬박 푸는 습관을 들여야겠습니다. 그럼 이번 포스트는 여기서 마무리 짓도록 하고, 모두들 좋은 밤 되시기 바랍니다 😊