[알고리즘] 구현 - 시각

문제

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

 

 

---

 

입력 조건

첫째 줄에 정수 N이 입력된다 (0 <= N <= 23)

 

---

 

출력 조건

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

 

---

 

풀이

아 이거 어려운 문제도 아닌데 진짜 너무 오래 걸렸다...

이 문제는 완전 탐색 유형으로 분류할 수 있는데, 가능한 모든 경우의 수를 검사해보기 때문이다.

완전 탐색 문제 또한 구현이 중요한 문제이며, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에는 정상적으로 작동하지 않을 수 있다. 

일반적으로 알고리즘 문제를 풀 때는 확인해야 할 전체 데이터가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

 

public class Problem2 {


    private int count;


    public int solve(Time time){

        while (time.timeUp()){
            if (time.hasThree()) count++;
        }

        return count;
    }


    public static void main(String[] args) {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){

            Problem2 problem2 = new Problem2();
            System.out.println(problem2.solve(new Time(br.readLine())));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

class Time{

    private String hour;
    private String minute;
    private String second;
    private String max_hour;

    public Time(String max_hour) {
        this.hour ="0";
        this.minute = "0";
        this.second = "0";

        this.max_hour = max_hour;
    }

    public boolean timeUp(){
        return secondUp();
    }

    private boolean secondUp(){
        if(second.equals("59")){
            second ="0";
            return minuteUp();
        }
        second = String.valueOf(Integer.parseInt(second)+1);
        return true;
    }

    private boolean minuteUp(){
        if(minute.equals("59")){
            minute ="0";

            return hourUp();
        }
        minute = String.valueOf(Integer.parseInt(minute)+1);
        return true;
    }

    private boolean hourUp(){
        if(hour.equals(max_hour)){
            return false;
        }
        hour = String.valueOf(Integer.parseInt(hour)+1);
        return true;
    }


    public boolean hasThree(){
        return hour.contains("3") || minute.contains("3") || second.contains("3");
    }
}

 

 

📔 Reference

[이것이 취업을 위한 코딩 테스트다 - 나동빈]

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체