1105. [Python]팔

1. 문제

 

https://www.acmicpc.net/problem/1105

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 수학
• 그리디 알고리즘

 

3. 파이썬 코드

 

L, R = map(str,input().split())
# 인풋 값의 길이 측정
L_length = len(L)
R_length = len(R)
# 각 인풋에서 들어온 값들에 8 이 있는지 체크하고 없으면 무조건 0 이 나오게 된다.
# 또한 각각 길이를 비교하여 두 길이가 다른경우도 무조건 0이 나오게된다.
if L.count("8") == 0 or R.count("8") == 0 or L_length != R_length:
    print(0)
# 외의 경우
else:
    # cnt 변수를 선언해주고
    cnt = 0
    # 길이가 같기 때문에 두 인덱스의 값을 비교하며 같은경우 8인지 확인하고 8인 경우 cnt 를 증가
    for i in range(L_length):
        if L[i] == R[i]:
            if L[i] == "8":
                cnt += 1
        # 같지 않은 경우 cnt 를 출력하고 break를 시행
        else:
            print(cnt)
            break
    # break가 걸리지 않을 경우 cnt 출력
    else:
        print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 수학적으로 생각하는 문제로 어떻게 접근하는지 고민을 많이 했다.
• 문자열로 접근하여 각 자리수를 비교한 후 그 자리수가 다른 경우 무조건 0이 나오는 것을 확인할 수 있었다.
  • 예시로 800 과 1000 이 있다고 하면 결국 1000 에서 8이 들어있지 않은 값이 나오기 때문에 0 이 나올 수 밖에 없다.
• 문자열 길이가 같은 경우에서 살펴보면
  • 각각의 자리수를 비교하기 시작하며 두 자리수가 같은 경우 다른 경우를 나눠서 생각할 수 있다.
  • 각 인덱스의 자리가 다른 경우는 결국 1xxx, 9xxx 이라고 하면 2000, 3000, 4000 등 8이 없는 수가 나올 수 있다.
  • 같은 경우 1xxx, 1xxx 이렇게 같은 경우에서는 값이 8인지 확인해주면 쉽게 접근할 수 있다.
  • 112x, 115x 이렇게 같은 경우도 결국 cnt로 앞에서 개수를 체크해줬기 때문에 break 걸리기 전에 cnt를 출력해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 수학
• 그리디 알고리즘