lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이 문제는 단순하게 생각하면 더 쉽게 풀 수 있다.
먼저 N의 범위는 1<=N<=10000이며 N번째로 큰 “666”이 포함되는 수를 찾아야 한다.

초기 아이디어

  • 완전탐색 알고리즘을 활용한다.
  • N 번만큼 반복하며 666부터 1씩 증가시키며, “666”이 포함되는 수를 찾는다.


이제 코드를 작성해보자.

1
2
3
4
5
6
7

int N = Integer.parseInt(br.readLine());
int num = 666;
int res = 0;

for(int i=0; i<N; i++) {
    res = nextNum(num, i);
}

main 메서드에서는 N을 입력받고, 666 정수를 담을 num 변수와 최종 N번째로 구할 수를 담을 res 변수를 선언하였다.
N번만큼 반복하면서 newtNum() 함수를 통해 N번째 종말의 수를 구해오도록 하였다.

1
2
3
4
5
6
7
8
9
10

public static int nextNum(int num, int cnt) {
    int n = num;
    for(int i=0; i<cnt; i++) {
        while(true) {
            n++;
            if(String.valueOf(n).contains("666")) break;   
        }
    }  
    return n;
}

nextNum() 함수의 내용이다. 이중으로 i번만큼 반복하면서 현재 num을 N번만큼 증가시키며 666, 1666, 2666 등으로 만들어야 하기 때문에 이중 for문 내에서 while문으로 N번째 수를 계산하였다.


메모리 초과?

사실 테스트케이스를 돌리면서도 시간제한 2초보다 더 걸려 당연히 오답일 것이라 생각하였다..
이중 for문에서 while문까지 실행하니 당연히 메모리를 왕창 잡아먹을 수 밖에 없었다.
다시 처음부터 아이디어를 곰곰히 생각해보니, 작성한 이중 for문을 없애도 충분하였다.


문제 해결을 위한 최종아이디어 도출

  • 완전탐색 알고리즘을 활용하여 666부터 1씩 증가하면서 “666”이 포함되는 수인지를 확인한다.
  • “666”이 포함될 때마다 카운트를 세어 카운트가 N가 같을 때의 수를 반환하면 된다.

하나의 while문만으로 N과 비교할 변수 하나로 위에서 발생한 메모리 문제와 코드의 가독성 2가지를 모두 잡을 수 있었다.
새로 작성한 코드를 살펴보자.

1
2
3
4
5
6
7
8
9

int num = 666;
int cnt = 1;

while(cnt != N) {
    num++;
    if(String.valueOf(num).contains("666")) cnt++;
}

bw.write(num+"\n");

666 수를 담을 num 변수와 N과 비교하며 카운트를 셀 cnt 변수를 선언한다.

  1. num(666)을 1씩 증가시키면서 문자열로 형변환한다.
  2. String으로 형변환된 num이 “666”을 포함하고 있다면 카운트를 하나 센다.
  3. 666부터 1씩 증가시키며 카운트를 세가며 cnt와 N이 같다면 N번째 수를 구한 것이니 while문을 종료한다.

초기 아이디어로 작성한 코드보다 가독성도 좋고, 코드 성능도 훨씬 개선되었다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.io.*;

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));

        int N = Integer.parseInt(br.readLine());
        int num = 666;
        int cnt = 1;
        
        while(cnt != N) {
            num++;
            if(String.valueOf(num).contains("666")) cnt++;
        }

        bw.write(num+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

회고

  • 문제를 올바르게 분석하지 못하고, 복잡하게 생각하니 쉬운 문제도 헤맸던 것 같다. 문제를 단순화하여 풀기쉬운 아이디어로 접근할 수 있도록 유의해야겠다.

You may also enjoy