[백준] 1436 - 영화감독 숌(Java)

1436번: 영화감독 숌

 

개요

문제에서 말하는 종말의 수란 숫자 6이 연속으로 3개 이상 들어가는 수를 말한다. 

예를 들어 666, 10666, 6666, 6661은 모두 종말의 수이다.

그러나 6616, 62626은 종말의 수가 아니다.

6이 연속으로 3개 이상 나오지 않기 때문이다.

 

입력으로 N이 주어지고, N번째로 작은 종말의 수를 출력하면 되는 문제이다.

(1≤ N ≤ 10,000)

 

N번째로 작은 종말의 수를 예시를 통해 알아보자.

if ( N == 3)

1번째로 작은 종말의 수 : 666
2번째로 작은 종말의 수 : 1666
3번째로 작은 종말의 수 : 2666 

==> N이 3일 때 2666이 답이다.

 

➡️ 즉, "666"이 포함된 수 중 N번째로 작은 수를 출력하면 된다.

 

 

걸린 시간 : 약 2시간

헷갈린 부분이 있어서 좀 오래 걸렸다. ㅠ

 

 

아이디어

✔️기본적인 아이디어는 다음과 같다.

• 1부터 1씩 증가하는 문자열 변수 front 뒤에 "666"이라는 문자열 변수 six를 붙여준다.
•  front는 1, 2, 3, 4, 5 … 이렇게 1씩 증가하고, 이 뒤에 "666"을 붙이기만 하면 N번째 작은 종말의 수를 금방 찾을 수 있다.
• front가 증가할 때마다 cnt도 같이 증가하고, cnt가 N보다 커지면 반복문을 벗어나고 정답을 출력한다.

⚠️ 주의할 점 1

- 5666 다음으로 작은 종말의 수는 6666이 아니다.

- 6660이 6666보다 작다. ( 아래 표를 참고해 보자 )

종말의 수	N
666	1
1666	2
2666	3
...	...
5666	6
6660	7
6661	8
...	...
6669	16
7666	17
...	...
65666	121
66600	122
66601	123
...	...

 

➡️ 이런 상황들을 처리 하기 위해 front의 일의 자리가 6인 경우

• front의 일의 자리부터 탐색하며 6이 나오지 않기 시작하는 인덱스의 위치를 찾는다.
• 그리고 front를 해당 인덱스까지 잘라준다.
• 잘린 길이만큼 "666"(six)을 앞으로 옮긴 후 그 길이만큼 뒤에 숫자(back 변수)를 붙여주었다.
• 이때 back은 "0 ~ 10^잘린 길이-1"까지 올 수 있다.
• 아래 그림을 보고 이해해보자.

 

⚠️ 주의할 점 2

for (back = 0; back < tmp; back++) {
    
    cnt++;
    // cnt를 증가시키다가 N보다 커지면 break
    if (cnt > N) {
        break;
    }
}

• 예를 들어  back이 0 ~ 99가 될 수 있는 경우
• 위 코드에서 보이듯이 back을 증가시키는 반복문 안에서 cnt가 N보다 커져서 break를 했을 때,
• back이 2인 상태에서 break 한 경우
• back은 항상 두 자리여야 하기 때문에 six 뒤에 "2"가 아니라 "02"로 붙여줘야 한다.

int len = String.valueOf(back).length(); // back의 길이

// 만약 back이 00~99까지 될 수 있는데 2에서 break 된 경우
// "166602" 이렇게 무조건 길이를 맞추기 위해 2 앞에 0을 추가해줘야 한다.
for (int j = front.length() - idx - len; j > 0; j--) {
    num += "0";
}

 

 

Solution Code

아래 코드에 문제가 있다면 댓글 달아주세요! :)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int cnt = 2; // N번째 작은 수를 카운트
		String six = "666";
		String front = "1";
		String num = six; // 정답을 담을 변수

		int back = 0;

		while (cnt <= N) {

			int idx = -1;

			// front의 일의 자리가 6인지 검사
			if (front.charAt(front.length() - 1) == '6') {

				// front의 끝에서부터 6이 나오지 않기 시작하는 인덱스의 위치 찾기
				for (int i = front.length() - 1; i >= 0; i--) {
					if (front.charAt(i) != '6') {
						idx = i + 1;
						break;
					}
				}

				// 만약 front가 전부 6으로만 이루어져 있으면 idx를 0으로 갱신해준다.
				if (idx == -1)
					idx = 0;

			}

			// front 일의 자리가 6이 아닌 경우
			if (idx == -1) {
				num = front + six;
				cnt++;
			}
			// front 일의 자리가 6인 경우
			else {

				int tmp = (int) Math.pow(10, front.length() - idx);

				for (back = 0; back < tmp; back++) {

					cnt++;

					if (cnt > N) {
						break;
					}

				}

				// front와 six 붙이기
				num = front.substring(0, idx) + six;

				int len = String.valueOf(back).length();

				// "0"이 필요한 만큼 붙이기
				for (int j = front.length() - idx - len; j > 0; j--) {
					num += "0";
				}

				// back 붙이기
				num += String.valueOf(back);

			}

			// front 1씩 증가시킴
			front = String.valueOf(Integer.parseInt(front) + 1);

		}

		System.out.println(num);
	}

}

 

 

어려웠던 점 & 헷갈렸던 점

처음엔 front의 일의 자리만 6인지 확인하였다.

그런데 답이 안 나와서 처음부터 쭉 손으로 적어본 후에 65666 다음으로 작은 종말의 수가 66600인 것을 확인하였다.

그 후에 front의 일의 자리부터 탐색하며 6이 나오지 않기 시작하는 인덱스의 위치를 찾는 반복문을 추가해 주어 해결했다.

역시 항상 내가 생각한 로직이 맞는지 꼼꼼히 확인해야 해🥲 

 

---

 

정답 비율이 56%나 되길래 금방 풀겠지라는 생각으로 풀기 시작했다가 놓친 부분이 있어서 푸는 시간이 생각보다 오래 걸렸다. 문제 다 풀고 나서 다른 사람들의 코드를 보니 많은 사람들이 브루트포스로 푼 것을 보았다. 내가 푼 방식이 실행 속도 면에서는 더 빠를 수 있지만 실제 코딩 테스트 상황이라면 좀 더 효율적으로 짜려다가 조건을 놓치는 부분이 있을 수도 있을 것 같다. 요즘은 시간 초과 할까 봐 지레 겁먹고 문제를 좀 더 복잡하게 풀려고 하는 느낌이다. 좀 더 힘을 빼고 푸는 연습도 해야겠다.