[TIL]Day 151

itertools chain 모듈을 사용하여 2차원 리스트를 일렬로 이어붙이기

import itertools
arr = [[1,2,3],[4,5,6],[7,8,9]]
arr = list(itertools.chain(*arr))
print(arr)

list로 변환하지 않아도 max 같은 함수 사용이 가능하다.

import itertools
arr = [[1,2,3],[4,5,6],[7,8,9]]
print(max(itertools.chain(*arr)))

프로그래머스 순위검색
효율성 떨어지는 코드

def solution(info, query):
    answer = []
    for q in query:
        ql = q.replace('and ','').split(' ')
        cnt = 0
        for p in info:
            pl = p.split(' ')
            for i in range(5):
                if i == 4:
                    if int(ql[i]) <= int(pl[i]):
                        cnt += 1
                    break
                if ql[i] != '-' and ql[i] != pl[i]:
                    break
        answer.append(cnt)    
    return answer

효율성 통과 코드

def solution(info, query):
    answer = []
    d = get_dic(info,{})
    for k in d:
        d[k].sort()
    for q in query:
        ql = q.replace('and ','').split(' ')
        q1 = ''.join(ql[:-1])
        s = int(ql[4])
        cnt = 0
        if d.get(q1,False):
            cnt = upper_bound(d[q1],s-1)
        answer.append(cnt)    
    return answer

def get_dic(info,d):
    for s in info:
        t1 = s.split(' ')
        t2 = ['']
        n = int(t1[4])
        for i in range(4):
            t3 = []
            for j in range(len(t2)):
                t3.append(t2[j]+t1[i])
                t3.append(t2[j]+'-')
            t2 = t3
        for item in t2:
            # d[item] = d.get(item,[]) + [n]
            if d.get(item,False):
                d[item].append(n)
            else:
                d[item] = [n]
    return d

def upper_bound(arr,n):
    s = 0
    e = len(arr)
    while s < e:
        mid = s + (e-s)//2
        if n >= arr[mid]:
            s = mid + 1
        else:
            e = mid
    return len(arr) - s

key point
0.딕셔너리에 미리 저장해둬야함
1.정렬 미리 해야함
2.이진탐색으로 찾아야함

upper bound 알고리즘
특정값 이상의 값이 나타나는 인덱스 반환

def upper_bound(arr,n):
	arr.sort()
    s = 0
    e = len(arr)
    while s < e:
        mid = s + (e-s)//2
        if n >= arr[mid]:
            s = mid + 1
        else:
            e = mid
    return s