log 2021-03-19

---

할 일

• 이슈처리-437
• pseudo-back

한 일

이슈처리-437 (5일차)

2021-03-19-p.md

웹 표준 검사 도구(WAVE)같은 것이 있다. 공공기관 소프트웨어 납품 등을 위해 인증을 하려면 이러한 것들도 거쳐야 하는 모양이다. 근데 깃허브도 검사해보면 오류 많이 뜬다. 지키기 상당히 빡셀 듯..

pseudo-back

• 이슈등록: 구글 oauth 셋업
• 이슈등록: 자체 auth strategy 사용
• 이슈등록: oauth scope 범위 조사
  • contacts
  • contacts.other.readonly
  • contacts.readonly
  • directory.readonly
  • user.addresses.read
  • user.birthday.read
  • user.emails.read
  • user.gender.read
  • user.organization.read
  • user.phonenumbers.read
  • userinfo.email
  • userinfo.profile

알고리즘 문제풀이

백준 3078 - 좋은 친구

한방에맞았다 !

https://m.blog.naver.com/kks227/220781851401

hint

큐 문제에서 나온건데, 어떻게 큐로 푸는지는 모르겠다. 사람이 점들의 쌍을 셀 때 어떤 규칙으로 세는지 생각함.

py solution

이름별 버킷을 만든 다음, 투포인터로 거리 값 K이하를 유지하며 포인터 위치 차이로 쌍의 개수를 세었다.

def solve():
    n, k = ria()

    # 아 한명이 주어지고 그 좋은 친구들을 찾는 것이 아니라,
    # 전체로부터 좋은 친구를 찾아야 한다.
    # 그러면 제한이 30만이므로 크기 때문에 메모리에 담기 어려울수 있으므로,
    # O(n)으로 처리해야 할듯하다.

    # 근데 k가 최대 n이므로.. 새로 처리할때 이전을 다 조회할 수 없다.
    # 어떻게 해야하지??
    # 현재 것을 처리하는게 o(1)이 되어야 한다.
    # 이전 k개 중 이름이 같은 것을 찾아야 하는데 O(1)이라..
    # 정렬하면?
    # 등수와 이름길이쌍으로 저장한 후, 이름으로 정렬,
    # 그 안에서 다시 등수로 정렬한 다음,
    # 해당 버킷에서 다시 등수의 차이들을 계산한다.
    # 근데, 그렇게 되면 쌍을 세야 하는데 인접 하나씩밖에 못셀텐데..
    # 계산한 등수의 차이들 목록을 가지고 뭘 할수있지??
    # 투 포인터로 두개 사이 거리가 k이하로 유지하면서 쌍 세기??

    # 4 3
    # [ 1,1,2,1] 이라면
    # [1,2,3,5,6] 인 것이고,
    # 1: 2,3, 2:3,5 3: 5,6 5:6 으로 총 7쌍이다.
    # [s,1,1,e,2,1] 까지 2쌍, e를 늘리면 초과하므로 s 전진
    # [1,s,1,2,e,1] 까지 2쌍,
    # [1,1,s,2,1,e] 까지 2쌍,
    # [1,1,2,s,1,e] 로 1쌍?
    from collections import defaultdict
    arrs = defaultdict(lambda: [])  # 각 길이 클래스 등수들
    lasts = [0] * 25
    cur = 0

    while(n > 0):
        nextlen = len(rsa()[0])
        # lasts[nextlen] # nextlen길이의 마지막 등수
        arrs[nextlen].append(cur - lasts[nextlen])
        lasts[nextlen] = cur
        cur += 1
        n -= 1

    it(arrs)
    ans = 0

    for i, v in enumerate(arrs):
        arr = arrs[v]
        s = 1
        e = 1
        # arr = [2, 1, 3, 2]
        # arr = [1, 1, 1, 2, 1]
        cur = 0
        curlen = 0

        while(e < len(arr)):
            curlen += arr[e]
            while(curlen > k):
                curlen -= arr[s]
                s += 1
            e += 1
            cur += e-s
            if(e >= len(arr)):
                break

            # it('s,e,cur,curlen, e-s')
            # it(s, e, cur, curlen, e-s)

        # it(s, e, cur, curlen, e-s)
        ans += cur

    # it(ans)
    print(ans)

기타

생각해보니.. 이미지를 vscode 확장으로 올려버리면 언젠가 저장소 용량 제한에 걸릴지도 모른다.

---