[완전탐색 문제풀이] 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 작성. 

ex) 00시 00분 03초 = true

00시 04분 14초 = false

<문제풀이>

let N = 5
let count = 0
let t = ''
for(let i = 0; i <= N; i++){
    for(let j = 0; j<60; j++){
        for(let k = 0; k < 60; k++){
            if((String(i)+String(j)+String(k)).includes('3')){
                count++
            }
        }
    }
}
console.log(count)

중요한 점은, 00시 00분 00초부터 N시 59분 59초까지의 경우의 수를 구할 때

시 / 분 / 초가 나뉘어져 있다는 것이다. 그리고 33초와 같이 3이 중복된 경우,

3이 포함된 1가지의 경우로 보아야 한다. 

 

3이 포함되는지 여부를 includes 함수를 써서 바로 확인하려 한다. 

다만 0~N을 확인할 i와 분, 초를 확인할 j,k값을 시,분,초로 하나의 값으로 만들 때

정수로 표현하게 되면 값을 3개로 나누어 반복문을 돌리던 해야할 것이다. 

각 3개의 수를 더하면 하나의 수로 바뀌기 때문이다. 

하지만 문자열로 표현하게 되면 ex) N이 23일 때 230235 로 표현할 수 있다. 

 

그렇게 3개의 수를 문자열로 더한 값에서 3이 포함되어 있을 경우 count에 1을 누적했다. 

 

완전탐색은 가능한 경우의 수를 모두 검사하는 탐색 방법이다. 

1차원적으로 계산하면 끝나다보니 간단하고 쉬운 방법일 수는 있지만,

숫자가 엄청 커지는 등, 경우의 수가 많아질 경우 비효율적인 방법이다. 

 

지금 내가 정의하기로는, 결국 대입할 수 있는 알고리즘이 있다면 그 방법을 쓰는 것이

성능적으로 효율적일 것이고, 무조건적으로 완전탐색이 비효율적일 것이다. 

왜냐하면 다 세는 것보다 덜 세고 찾는 것이 당연히 그만큼 일을 덜 한 것이기 때문이다. 

 

 

지금까지 코테문제들을 대부분 완전탐색 유형으로 풀어왔고, 그렇게 풀려고 하기에

다른 방식으로 시야가 트이지 않아서 막히고 있다는 생각이 들었다. 

다른 유형들의 여러 알고리즘에 대해 공부해야겠다.