Kaprekar 연산

• Kaprekar 연산은 네 자리 수 중 '모든' 자리수가 같지 않은 수의 각 자리의 숫자를 재배열하여, 만들 수 있는 가장 큰수와 가장 작은 수를 만들어 그 '차'를 계산하는데, 그 결과로 나온 새로운 숫자를 갖고 같은 과정을 반복한다.

• 2008의 경우
  • 가장 큰 수: 8200
  • 가장 작은 수: 0028

• 2008
  1. 8200 - 0028 = 8172 -> '가장 큰 수: 8721', '가장 작은 수: 1278'
  2. 8721 - 1278 = 7443
  3. 7443 - 3447 = 3996
  4. 9963 - 3699 = 6264
  5. 6642 - 2466 = 4176
  6. 7641 - 1467 = 6174 (6 단계에서 '6174' Kaprekar 수 발견)
  7. 7641 - 1467 = 6174
  8. ... 계속 6174만 만들어진다.

2008 뿐만 아니라, 한 숫자로 이루어지지 않은 모든 네 자리수는 6174로 가게된다.

각 자리 수 구하기

• 2341
  • 2341 / 1000 = '2'
    • 2341 % 1000 = 341
  • 341 / 100 = '3'
    • 341 % 100 = 41
  • 41 / 10 = '4'
    • 41 % 10 = 1
  • 1 / 1 = '1'

-> So bad..!

mod 10

• 2341
  • 2341 % 10 = '1', -> 2341 / 10 = 234
  • 234 % 10 = '4', -> 234 / 10 = 23
  • 23 % 10 = '3', -> 23 / 10 = 2
  • 2 % 10 = '2', -> 2 / 10 = 0

훨씬 코드가 간결해진다.

X=2341

while True:
    num= X % 10 # 각 자리 수
    remain= X / 10
    X= remain
    if X == 0:
        break

두 수에서 올림이 발생하는가?

a=19, b=9

while a == 0 or b ==0:
    if a % 10 + b % 10 >= 10:
        a = a//10
        b = b//10

• 두 수의 일의 자리씩 올라가며 올림이 발생하는지 체크

시계수

• 시계수: 시계 방향으로 돌렸을 때 나올 수 있는 수
  • 2134
  • 1342
  • 3421
  • 4213

arr=['2','1','3','4']
num[0]=arr[0]*1000 + arr[1]*100 + arr[2]*10 + arr[3]*1
num[1]=arr[1]*1000 + arr[2]*100 + arr[3]*10 + arr[0]*1

optimize

빌딩 문제

빌딩 wrap 싸기

1. 가장 높은 빌딩 구하기

2. 가장 높은 빌딩 기준으로
   왼쪽 부터 제일 큰 것 스캔
   오른쪽 부터 제일 큰 것 스캔

빌딩 높이 Ⅰ

• 스택을 잘 쓰면 하나만 비교해도 안다.
  • hi < hj 만 볼 수 있을 때, 위와 같이 스택을 이용하면 비교 시간을 줄일 수 있다.

빌딩 높이 Ⅱ

설명

• 건물 N개: ($0≤i≤N-1$
• 높이 H: ($1≤H≤1*10^9$
• 건물에서 오른쪽만 본다
• 건물에서 옥상은 자기 건물 높이보다 낮아야만 볼 수 있음
• 각 건물이 볼 수 있는 건물 총 합 구하라
  
• 위 예제 답: 5

solve

• ${6≤N≤80000}$
• ${O(N^2) ≒ 10K}$

• Stack으로 for문 하나에 처리하자!

1. 
2. 
3. 
4. 
5. 각 스택의 idx 부터 앞쪽으로 볼 수 있는 갯수다.!!!
   즉!! 각 iteration마다 스택의 크기를 계속 구하면 된다!!

빌딩 Ⅲ

• 
  
• 더 낮은 값이 들어왔을 때, '그 전'까지 최대 넓이 갱신
  • 더 낮은 값 이후엔, 최대가 될 가능성이 없으니 pop
  • ( 시작점, 높이 )
    • 그 '높이'로 계속 간다는 가정하에 width 구하기

특정 수 안쓰기

• 1~100,000,000,000 층 에서 4가 들어간 수를 뺀 실제 층은?
  • 
  • '4'라는 수를 안쓰기에, 9진수를 사용하며, 매핑을 사용해 9진수를 만든다.
  • 이를 10진수로 변환하면 된다.

소수

• 소수: '1'과 '자기 자신'으로 밖에 나누어지지 않는 '1' 이외의 정수
  • e.g.: 2,3,5,7,11,13...

https://deveun.tistory.com/entry/Python%EB%B0%B1%EC%A4%80-1963%EC%86%8C%EC%88%98-%EA%B2%BD%EB%A1%9C

실수 연속 최대곱

• 아래와 같이 양의 실수가 주어질 때, 하나 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾고, 출력하라.

색칠된 부분의 곱이 최대가 되고, 그 값은 1.638이다.

res=num[0]
for i in range(1,N):
    if num[i]*num[i-1] >= num[i]:
        num[i]=num[i]*num[i-1]
    res=max(num[i], res)