[구현] 문제 이름 : 시각

문제 설명

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나롣 포함되는 경우의 수를 구하는 프로그램 작성하기

 

1. 사용 알고리즘

구현 - 완전 탐색

 

2. 문제 해결 아이디어

이 문제의 경우 모든 시각의 경우을 하나씩 탐색하여 3이 포함되는 경우를 찾아서 풀 수 있음. 왜냐하면 00시 00분 00초 ~ 23시 59분 59까지의 모든 경우가 86,400가지만 존재하기 때문임.

이러한 유형은 '완전 탐색(Brute Forcing)' 유형으로 분류됨

→ 완전탐색(Brute Forcing) 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법

→ 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에는 정상적 동작 안할 수도 있음

→ 일반적으로 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절함 

 

3. 코드

전체를 탐색하며 조건 만족 시 count 증가시키기

구현방식1)

시분초를 하나의 문자열로 변경하고, 해당 문자열이 3을 포함하고 있는지 확인하기

import java.util.Scanner;

class Ex1 {

	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		int N = kbd.nextInt();
		
		int count = 0; //3이 포함되는 경우의 수 
		
        //3중 for문으로 전체 탐색하기 
		for(int i = 0; i < N+1; i++)
			for(int k = 0; k < 60; k++)
				for(int j = 0; j < 60; j++) {
					//int -> String으로 변환
					String time = Integer.toString(i) + Integer.toString(k) + Integer.toString(j);
					//변환한 String에 3이 있으면 count 증가시키기 
					if(time.contains("3")) count++;
				}
		
		System.out.println(count);
					
	}

}

구현방식2)

시, 분, 초 각각에서 3이 나올 수 있는 경우에 대해 조건문 사용하기

import java.util.Scanner;

public class Ex1_2 {
	
	//시 분 초에서 3이 나올 수 있는 경우에 대한 조건문  
	public static boolean check(int h, int m, int s) {
		if(h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
			return true;
		return false;
	}

	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		int N = kbd.nextInt();
		
		int count = 0;
		
        //3중 for문으로 전체 경우 탐색
		for(int i = 0; i < N+1; i++)
			for(int k = 0; k < 60; k++)
				for(int j = 0; j < 60; j++) {
					if(check(i,k,j)) count++;
				}
		
		System.out.println(count);
					
	}

}

 

추가 개념 정리)

*Integer -> String으로 변환

toString메서드

Integer클래스의 toString() static 메서드를 통해 정수를 String으로 변환 가능함 → Integer.toString(int i)

 

*String에서 특정 문자 포함 여부 확인 

String클래스의 contains메서드

String 클래스의 contains() 인스턴스 메서드를 통해 String 객체가 인자로 주어진 문자를 포함 하는지 boolean으로 반환함