코딩도장

https://school.programmers.co.kr/learn/courses/30/lessons/250136

석유가 있는곳은 1인 2차원 좌표가 주어지고, 위에서 아래로 파면서 한번에 석유를 가장 많이 얻을수 있는 열을 찾는 문제

bfs로 풀었더니 3번 4번 시간

from queue import Queue
def solution(land):
    answer = 0
    mx,my = len(land[0]), len(land)
    visited = [[False for _ in range(mx)] for _ in range(my)]
    direction = [[0,1],[-1,0],[0,-1],[1,0]]
    csum = [0 for _ in range(mx)]
    def bfs(r,c):
        queue = Queue()
        queue.put([r,c])
        visited[r][c]  = True
        cset = {c}
        cnt = 1
        while queue.empty() != True :
            r,c = queue.get()
            for dr, dc in direction:
                mr, mc = r+dr, c+dc
                if mr>=0 and mc>=0 and mr<my and mc<mx and land[mr][mc]==1 and visited[mr][mc] == False:
                    queue.put([mr,mc])
                    visited[mr][mc]  = True
                    cnt += 1
                    cset.add(mc)
        for v in cset:
            csum[v] += cnt
    
    for r, lst in enumerate(land):
        for c, v in enumerate(lst):
            if v==1 and visited[r][c]==False:
                bfs(r,c)
    answer = max(csum)
    return answer
#9
a = [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]
print(solution(a))

이분은 비슷한데 bfs부분을 그냥 for문 밑에 달아 버렸음 심지어 이분은 queue도 안쓰고 그냥 리스트로 했는데 시간오버 안생김 

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[True]*m for _ in range(n)]
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    oil_cnt = [0]*m
    for i in range(n):
        for j in range(m):
            if land[i][j] and visited[i][j]:
                visited[i][j] = False
                s = [(i,j)]
                col = set()
                oil = 0
                while s:
                    x, y = s.pop()
                    col.add(y)
                    oil += 1
                    for dx, dy in delta:
                        X, Y = x+dx, y+dy
                        if 0<=X<n and 0<=Y<m and land[X][Y] and visited[X][Y]:
                            visited[X][Y] = False
                            s.append((X,Y))
                for y in col:
                    oil_cnt[y] += oil
    return max(oil_cnt)

음 그래서 나도 for문 밑에 달아 봤더니 안된다 ㅠ

힘들게 queue까지 선언까지했는데  list가 더 빠른가

https://school.programmers.co.kr/learn/courses/30/lessons/181188

targets은 공격당하는범위들이다. 요격미사일을 최소로 쏴서 없애야 한다.

공격범위는 0보다 크다 s<e

일단 targets을 작은 순서로 sort에서 앞에서 부터 겹치는 범위를 찾아서 뒤로가다가 겹치는 범위가 없어지면 새로운 미사일을 준비했다. 

def solution(targets):
    answer = 0
    targets.sort()
    rs=0
    re=0
    cnt = 0
    s=[]
    for i,p in enumerate(targets):
        if(i == 0):
            s = p
            continue
        rs = max(s[0],p[0])
        re = min(s[1], p[1])
        if rs>=re:
            if s[0] < s[1]:
                cnt += 1
            s = p
        else:
            s = [rs,re]
    if s[0] < s[1]:
        cnt += 1
    answer = cnt
    return answer

a =[[0, 4], [1, 2], [1, 3], [3, 4]] #2
a = [[0, 4], [0, 1], [2, 3]] #2
#a = [[0,0],[0,0]] #0
solution(a)

sort(key=lamda x:x[1])을 이용해서 끝을 이용해서 정렬했다.

def solution(targets):
    answer = 0
    targets.sort(key=lambda x:x[1])
    answer = 0
    end = -1  # 마지막으로 요격한 미사일의 x좌표

    for s, e in targets:
        if s >= end:  # 이전에 요격한 미사일로는 현재 미사일을 요격할 수 없는 경우
            answer += 1
            end = e  # 현재 미사일을 요격함으로써 끝나는 지점을 업데이트

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/150370

현재 날짜 today 유효기간이 적힌 계약 조건, 계약리스트가 주어진다.

유효기간이 지난 리스트번호를 출력한다.

유효기간의 시작은 오늘부터이므로 -1을 해줘야 한다.

def solution(today, terms, privacies):
    answer = []
    date = today.split('.')
    todays = int(date[0])*28*12 + int(date[1])*28 + int(date[2])
    termdic ={}
    for v in terms:
        term = v.split()
        termdic[term[0]] = int(term[1])
    for i,lst in enumerate( privacies):
        temp = lst.split()
        date = temp[0].split('.')
        outdays = int(date[0])*28*12 + int(date[1])*28 + int(date[2])
        outdays += termdic[temp[1]]*28-1
        if outdays < todays:
            answer.append(i+1)
    return answer
    
a="2022.05.19"	
b=["A 6", "B 12", "C 3"]	
c=["2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"]
solution(a,b,c)

다른분은 map()을 이용해 리스트 요소에 int()를 처리해주었고 

def to_days(date):
    year, month, day = map(int, date.split("."))
    return year * 28 * 12 + month * 28 + day

def solution(today, terms, privacies):
    months = {v[0]: int(v[2:]) * 28 for v in terms}
    today = to_days(today)
    expire = [
        i + 1 for i, privacy in enumerate(privacies)
        if to_days(privacy[:-2]) + months[privacy[-1]] <= today
    ]
    return expire