[이코테] 시각

문제 풀면서 작성한 메모

풀이 과정

---

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

문제의 길이가 굉장히 짧았다. 고등학교 때 확률과 통계에서 경우의 수 문제를 푸는 것 같았다. '하나라도 포함되는'을 보자마자 '하나 이상'일 때는 전체 경우의 수에서 하나도 없을 때를 빼야 한다는 생각의 흐름이 자동적으로 이어졌다. 역시 K-입시.. ^^

 

입력 첫째 줄에 정수 N이 주어지므로 정수 N과 입력 조건을 메모했다. 내가 본 입력 조건 중 범위가 작았던 편에 속하는데, 최소 0시 0분 0초이고 최대 23시 59분 59초이다. 그리고 출력해야 하는 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수도 메모했다.

2. 알고리즘을 떠올리고 적용하려고 노력한다.

구현 예시이므로 구현을 먼저 적었고 경우의 수 보자마자 완전 탐색이라고 생각했다. 모든 경우의 수를 구해야 하니까! 

 

경우의 수를 계산해야 하니 문제에서 사례로 든 케이스를 살펴봤다. 5가 주어졌을 때 11475를 출력해야 한다. 어떻게 구할 수 있을까? 앞서 말했듯이 모든 경우의 수에서 3이 한 개도 없는 경우의 수를 뺄 것이다.

 

모든 경우의 수를 구하기 위해 시부터 살펴보면 0부터 N시까지 가능하므로 (N+1)의 경우의 수가 나온다. 분의 경우 00분부터 59분까지 가능하다. 앞자리는 0부터 5가 올 수 있으므로 (5+1)=6가지 경우의 수, 뒷자리는 0부터 9까지 올 수 있으니 (9+1)=10가지 경우의 수다. 초는 분과 마찬가지로 구한다. 각 자리에 올 수 있는 경우의 수를 곱하면 (N+1)*6*9*6*9가 모든 경우의 수이다.

 

이제 3이 한 개도 없는 경우를 생각해보자. 3이 한 개도 없는 경우는 N에 3이 포함되느냐 포함되지 않느냐에 따라 다르다. 즉, N이 3 이상인지 3 미만인지에 따라 경우가 나뉜다. N이 3 이상인 경우 3시가 나오는 경우를 제외하면 나올 수 있는 경우의 수는 (N+1)-1=N이다. 분과 초는 앞자리에 3이 오는 경우를 제외하면 6-1=5, 뒷자리에 3이 오는 경우를 제외하면 10-1=9이다. 따라서 N이 3 이상인데 3이 하나도 포함되지 않는 경우의 수는 N*5*9*5*9이다. N이 3 미만인 경우 3이 없으니 N인데 헉... 결국 똑같다. N에 3이 포함되든 포함되지 않든 3이 하나도 포함되지 않는 모든 경우의 수는 N*5*9*5*9이다. 이걸 작성하면서 깨닫다니.. 입력 예시가 N>=3인 경우라 맞았다고 착각한 것이다. 입력 예시로 든 N이 3 미만이었으면 내가 제출한 답안은 테스트 케이스를 통과하지 못했을 것이다.

3. 필요한 변수에 대해서는 변수명을 작성한다.

입력으로 주어지는 정수 N은 소문자 n으로, 출력해야 하는 경우의 수는 answer라고 이름 지었다.

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

# 정수 N 저장

# 3이 하나라도 포함되는 모든 경우의 수 계산

# answer 출력

5. 의사 코드에 맞춰 구현한다.

# 정수 N 저장
n = int(input())

if n >= 3:
  answer = (n+1)*6*10*6*10 - n*5*9*5*9
else:
  answer = (n+1)*6*10*6*10 - 5*9*5*9

# 3이 하나라도 포함되는 모든 경우의 수 answer 출력
print(answer)

이렇게 작성했는데 블로그 포스팅하면서 n이 3 이상이든 3 미만이든 똑같이 answer는 (n+1)*6*10*6*10 - n*5*9*5*9라는 것을 깨달았다. 다시 고쳐서 업데이트했다.

# 정수 N 저장
n = int(input())

# 3이 하나라도 포함되는 모든 경우의 수 계산
answer = (n+1)*6*10*6*10 - n*5*9*5*9

# answer 출력
print(answer)

답안 예시

---

4-2.py 답안 예시

# H를 입력받기
h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

충격적인 풀이였다. 내가 굉장히 수학적으로 접근했다는 것을 깨달았다. 처음에 for문을 세 번이나 돌면서 1씩 추가하는 것이 매우 비효율적이라 생각했는데 아예 문자열로 바꿔서 '3'이 포함되어 있다면 count 하는 부분은 창의적이었다. 그렇네, 이렇게 풀 수도 있었지...! 예전에 백준에서 풀었던 비슷한 문제가 생각났다.

10809번: 알파벳 찾기

10809번: 알파벳 찾기는 어떤 단어 S가 주어질 때 각 알파벳마다 처음 등장하는 위치를 출력하는 문제이다. 시각 문제와 마찬가지로 구현 문제인데 당시 나는 시각 답안 예시와 같이 문자열로 풀었다. 알파벳과 같은 문자일 때는 문자열로 푸는 게 당연했는데 시, 분, 초는 숫자이기 때문에 숫자로만 풀려했다니.. 고정관념에 사로잡힌 나 자신을 반성했다. 앞으로 경우의 수 문제는 문자열을 떠올리자!

개념 정리

---

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. 구현 유형은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 구현 유형의 문제는 문제의 길이가 꽤 긴 편이지만 고차원적 사고력을 요구하는 문제는 나오지 않는 편이라 오히려 쉽게 풀 수 있다.

 

혹시 코팅 테스트 환경에서 파이썬3 뿐만 아니라 Pypy3도 지원한다면 Pypy3의 실행 속도가 때로는 C/C++과 견줄 만큼 빠르므로 Pypy3을 이용하도록 하자. 특히 반복문이 많을수록 Pypy3와 파이썬3의 속도가 차이가 난다.

 

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다.

완전 탐색

모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

이 문제는 완전 탐색 유형으로, 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다. for문을 3번 돌아도 모든 경우의 수가 24 * 60 * 60은 86,400가지밖에 존재하지 않는다. 즉, 100만 개 이하이므로 시간제한 2초 안에 문제를 해결할 수 있다.

 

구현 문제 유형은 앞장에서 공부했던 그리디 알고리즘과 크게 다르지 않은데, 애초에 구현 유형과 그리디 유형은 별개가 아니라 하나의 문제에 구현 유형과 그리디 유형이 함께 포함된 형태로 출제되는 경우가 많기 때문이다.

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p113-114