1475번 방 번호

문제 출처 : https://www.acmicpc.net/problem/1475

10퍼에서 계속 틀림. 내가 놓치는 부분이 뭘까? 반례가 뭘까?
찾았다. 문제는 round 함수!! 사사오입 원칙에 있다.

사고과정

조건1 : 필요한 숫자 세트 개수의 최솟값
조건2 : 6과9는 같은 취급

=> (0,1,2,3,4,5,7,8) 과 (6,9)는 다른 Group
이에 따라 구분해서 조건을 해결

import sys
import math

N = list(map(int,sys.stdin.readline().rstrip("\n")))
while N[0]==0 and len(N)!=1 :
    N.pop(0)
n = len(N)
s_n=0
num={0:0,1:0,2:0,3:0,4:0,5:0,7:0,8:0}

for i in range(n) :
    if N[i]==6 or N[i]==9 :
        s_n+=1
    else:
        num[N[i]]+=1
s_n=math.ceil(s_n/2) if ((s_n)%2)!=0 else s_n//2
print(max(max(num.values()),s_n))

이정도면 dictionary는 list보다 많은 메모리를 차지한다는 게 거의 확실한 것 같다. 사실 굳이 dictionary로 풀 필요는 없는 것 같다. index를 이용해서 풀 수 있지 않을까?

import sys
import math

N = list(map(int,sys.stdin.readline().rstrip("\n")))
while N[0]==0 and len(N)!=1 :
    N.pop(0)
n = len(N)
s_n=0
num=[0 for _ in range(10)]

for i in N :
    if i==6 or i==9 :
        s_n+=1
    else:
        num[i]+=1
s_n=math.ceil(s_n/2) if ((s_n)%2)!=0 else s_n//2
print(max(max(num),s_n))

dictionary를 index로 교체해도 메모리에는 변화가 없다...

import sys

N = list(map(int,sys.stdin.readline().rstrip("\n")))
while N[0]==0 and len(N)!=1 :
    N.pop(0)
n = len(N)
s_n=0
num=[0 for _ in range(10)]

for i in N :
    if i==6 or i==9 :
        s_n+=1
    else:
        num[i]+=1
s_n = s_n//2+1 if s_n%2!=0 else s_n//2
print(max(max(num),s_n))

import math, ceil등을 사용하지 않으니까 메모리가 줄어들었다! import math하는 과정들이 메모리 사용을 키운 것 같다.

---

사사오입이란?

자 이제 문제의 사사오입이다! 찾아보니까 사실 반올림의 다의어이다.
round(4.5) # 4
round(3.5) # 4
이와 같이 round 함수를 사용하여 반올림을 할때 발생하는 차이에 의해 문제를 계속해서 틀렸다. round 함수는 반올림을 할 때 앞자리의 숫자가 짝수면 내림하고 홀수면 올림을 한다.

WHY?

여기저기 정보를 찾아보니까 이것도 이유가 있더라. 그 이유는 프로그래밍에서 근사 처리 되어야 할 대상을 더욱 근사치에 가깝게 하기 위해, 즉 더 정교하게 하기 위해서이다.
이게 무슨 소리야.. 싶을텐데

1.5, 2.5, 3.5 이 세개를 모두 다 반올림 하면 2,3,4가 되버린다. 이런 맹목적인 올림이 프로그래밍에서는 적절히 않다고 파이썬 개발자는 생각하였나 보다. 그래서 전체 데이터량에서 절반이나 반올림을 해야한다하면 오차는 그만큼 커지게 되고 이러한 오차를 보정해주기 위해
위와 같이 반올림 결과를 짝수에 맞추게 된 것이다. 그래서 결과값은 2,2,4 가 된다.

이것도 빨리 풀면 겁나 빨리 끝났을텐데... 이런 새로운 지식을 습득하게 되네!