[백준] 1436번 영화감독 숌

백준 온라인 저지 단계별로 풀어보기 브루트포스 5단계 문제 1486번

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList list = new ArrayList<>();
        for (int i = 0; i < 3000000; i++) {
            if(String.valueOf(i).contains("666"))
                list.add(i);
        }
        System.out.println(list.get(n - 1));
    }
}

처음에는

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = "666";
        HashSet set = new HashSet<>();
        for (int i = 0; i < 10000; i++) {
            if(String.valueOf(i).length() == 1) {
                set.add(Integer.parseInt(s + i));
                set.add(Integer.parseInt(i + s));
            } 
            else if (String.valueOf(i).length() == 2) {
                set.add(Integer.parseInt(s + i));
                set.add(Integer.parseInt(i + s));
                set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).charAt(1)));
            }
            else if (String.valueOf(i).length() == 3) {
                set.add(Integer.parseInt(s + i));
                set.add(Integer.parseInt(i + s));
                set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).substring(1, 3)));
                set.add(Integer.parseInt(String.valueOf(i).substring(0, 2) + s + String.valueOf(i).charAt(2)));
            }
            else {
                set.add(Integer.parseInt(s + i));
                set.add(Integer.parseInt(i + s));
                set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).substring(1, 4)));
                set.add(Integer.parseInt(String.valueOf(i).substring(0, 2) + s + String.valueOf(i).substring(2, 4)));
                set.add(Integer.parseInt(String.valueOf(i).substring(0, 3) + s + String.valueOf(i).charAt(3)));
            }
        }
        ArrayList list = new ArrayList<>(set);
        list.sort((a, b) -> a - b);
        System.out.println(list.get(n - 1));
    }
}

이렇게 했는데 자꾸 틀렸다고 나오는거다.

그래서 포기하고 구글링을 해봤더니 자바의 String 클래스에 contains()라는 메소드가 있었다.

Java10 API String 클래스의 contains 메소드

https://docs.oracle.com/javase/10/docs/api/java/lang/String.html

String (Java SE 10 & JDK 10 )

이 메소드를 이용해서 0부터 (넉넉하게) 3000000까지 완전히 브루트포스한 방법으로 성공하긴 했는데 아까 그 코드가 왜 틀렸는지가 너무 궁금했다.

그래서 그 리스트를 다 출력해서 복사해서 워드에 붙여넣고 줄번호를 넣어서 비교해봤다.

 

확실히 결과가 다르긴 한데 어디서 부터 왜 잘못된건지 찾아보았다.

비교해보니 121번째 숫자부터 잘못되었다. 보니까 int를 String으로 변환한 후 그것을 concatenation했기 때문에 0이나 00이나 int로는 똑같은 0이기 때문에 00 같은 경우는 빠진 것이었다.

내가 처음에 한 방법은 0부터 큰 숫자를 찾은 것이 아니기 때문에 HashSet을 이용해서 유일하게 만든 후 그것을 ArrayList로 만들고 따로 정렬을 했지만 정답을 낸 이 방법은 정렬을 할 필요도 없었다.

물론 복잡도는 더 높겠지만 이 유형 자체가 브루트포스이기 때문에 무식하게 풀어도 시간초과가 나지 않았다.