import sys
from functools import cmp_to_key
input = sys.stdin.readline
def cmpDic(a,b):
if(a[1]<b[1]):
return 1
elif (a[1]>b[1]):
return -1
if(len(a[0])<len(b[0])):
return 1
elif(len(a[0])>len(b[0])):
return -1
if a>b:
return 1
else:
return -1
N, M= map(int,input().split())
res={}
for i in range(N):
a=input().rstrip()
if(len(a)<M):
continue
if(a in res):
res[a]+=1
else:
res[a]=1
res = [(k, v) for k, v in res.items()]
res.sort(key=cmp_to_key(cmpDic))
for i,j in res:
print(i)
from functools import cmp_to_key
def cmpFile(a,b):
if a[0].upper() > b[0].upper():
return 1
elif a[0].upper() < b[0].upper():
return -1
else:
if int(a[1]) > int(b[1]):
return 1
elif int(a[1]) < int(b[1]):
return -1
return 0
def solution(files):
answer = []
res=[]
for i in files:
head=0
number=0
for j in range(len(i)):
if head==0 and '0'<=i[j]<='9':
head=j
if head!=0 and number==0 and ('0'>i[j] or i[j]>'9'):
number=j
if(number==0):
number=len(i)
answer.append([i[:head],i[head:number],i[number:]])
answer.sort(key=cmp_to_key(cmpFile))
for head,number,tail in answer:
res.append(head+number+tail)
return res
풀이
파일명을 특정 기준을 따라 정렬해라
head, number, tail 구역으로 나눈다.
나눈 파일명을 기준에 따라 정렬하기 위해 cmpFile함수를 작성하고 cmp_to_key를 사용해서 비교함수로 사용한다
정렬한 파일명을 다시 합쳐서 리턴한다.
특이사항
람다와 정규식을 사용해서 풀면 이정도로 줄일 수 있단다…
import re
def solution(files):
a = sorted(files, key=lambda file : int(re.findall('\\d+', file)[0]))
b = sorted(a, key=lambda file : re.split('\\d+', file.lower())[0])
return b
import sys
sys.setrecursionlimit(1000000)
def dfs(land, i, j, m, n, check, patch_id):
if i < 0 or i >= m or j < 0 or j >= n or check[i][j] != 0 or land[i][j] == 0:
return 0
check[i][j] = patch_id
size = 1
size += dfs(land, i + 1, j, m, n, check, patch_id)
size += dfs(land, i - 1, j, m, n, check, patch_id)
size += dfs(land, i, j + 1, m, n, check, patch_id)
size += dfs(land, i, j - 1, m, n, check, patch_id)
return size
def solution(land):
m = len(land)
n = len(land[0])
check = [[0] * n for _ in range(m)]
patch_sizes = {}
patch_id = 1
for i in range(m):
for j in range(n):
if land[i][j] == 1 and check[i][j] == 0:
patch_size = dfs(land, i, j, m, n, check, patch_id)
patch_sizes[patch_id] = patch_size
patch_id += 1
max_oil = 0
for j in range(n):
oil_in_column = set()
for i in range(m):
if check[i][j] != 0:
oil_in_column.add(check[i][j])
total_oil = sum(patch_sizes[pid] for pid in oil_in_column)
max_oil = max(max_oil, total_oil)
return max_oil
풀이
일자로 팠을 때 석유를 최대한 많이 얻는 경우는?
우선 땅에 있는 모든 석유 웅덩이를 dfs로 확인하여 1,2,3 라벨과 넓이를 붙여준다.
그 뒤 땅을 한번씩 돌면서 일자로 팠을 때 시추 가능한 양을 체크하면서 최대로 시추 가능한 곳의 양을 max_oil에 저장하고 리턴한다.
특이사항
우선 정확성은 전부 통과했는데 효율성에러 런타임 에러가 나서 왜그런가 하고 생각해봤는데, 파이썬의 재귀 제한 때문에 오류가 나는것을 파악해서 재귀 허용을 늘려주면 통과한다. (기본 재귀 1000번)
import sys sys.setrecursionlimit(1000000)
원래는 매 시행때 dfs를 돌면서 계속 체크를 하려고 했다가 그렇게 되면 효율성을 통과하지 못할거라고 생각하고 미리 dfs로 모든 석유의 라벨링을 해주며 진행했다.
N = int(input())
coordinate=[]
for i in range(N):
coordinate.append(tuple(map(int,input().split())))
max_x = max(coord[0] for coord in coordinate)
max_y = max(coord[1] for coord in coordinate)
grid = [[0 for _ in range(max_x)] for _ in range(max_y)]
for x, y in coordinate:
for i in range(y):
grid[i][x - 1] = 1
grid.reverse()
res=0
for i in range(len(grid)):
if(grid[i].count(1)==0):
continue
if(grid[i].count(1)==1):
res+=1
continue
front_index = grid[i].index(1) + 1
back_index = len(grid[i]) - grid[i][::-1].index(1)
res+=back_index-front_index+1
print(res)
import sys
input = sys.stdin.readline
m, n =map(int,input().rstrip().split())
keyword = {}
unUse=m
for i in range(m):
keyword[input().rstrip()]=False
for i in range(n):
memo = input().rstrip().split(',')
for j in memo:
if(j in keyword):
if(not keyword[j]):
keyword[j]+=True
unUse-=1
print(unUse)
풀이
사용되지 않은 키워드의 개수를 구해라
키워드를 입력받아 딕셔너리 키워드:0 형태로 만들어준다.
unUse , 사용되지 않은 키워드의 개수를 세는 변수는 만들어준다
블로그에 사용한 키워드를 memo에 입력받고, 언급된 키워드들을 제거해준다.
keyword에 없는 단어들은 체크하지 않는다.
keyword에 있는데 value가 False이 아닌 단어는 이미 한번 이상 사용된 단어이므로 넘어간다.
keyword에 있는 단어인데 value가 False인경우 사용하지 않은 단어이므로 True로 바꿔준 후 unUse-=1을 해준다
