[이것이 코딩테스트다] Chapter 2. 구현

코딩테스트에서 구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

 

예제 4-1 상하좌우

첫째 값 : 공간의 크기를 나타내는 N

둘째 값 : 여행가 A가 이동할 계획서 내용

 

입력 예시

5

R R R U D D

 

출력 예시 

3 4

 

답안 예시

n = int(input())
x, y = 1, 1
plans = input().split()


# L, R, U, D에 따른 이동 방향
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny
print(x,y)

 

예제 4-2. 시각

 

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

 

3이 하나라도 포함되어 있다면, 수를 센다.

 

입력 예시

5

 

출력예시 

11475

 

 

Sol)

모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제다. 단순히 시각을 1씩 증가시키면서, 3이 하나라도 포함되어 있는 지 확인하면 될 것이다. 이러한 유형은 완전 탐색 으로 불린다.

 

# 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)

1시간에 60분.. 1분에 60초 ..