from functools import reduce
def solution(participant, completion):
part = reduce(lambda temp,value : temp.update({value:temp.get(value, 0)+1}) or temp, participant, {})
for a in completion:
part.update({a:part.get(a,1)-1})
answer = list(filter(lambda a : part.get(a) != 0,part))[0]
return answer
성공한 스테이지는 배열에 저장되어있는 값 -1 이다. ex) stages = [2,1,2,6,2,4,3,3] 일 때, stages[0]는 2이다. 즉, 2 스테이지를 시도했지만 실패했다, 실제 성공은 1 스테이지까지만 한게 된다.
스테이지별로 반복을 돌려 필요한 값을 얻어낸다.
반복부 끝에 스테이지에 머물러있는 사람들을 변수하나에 누적시켜서 실패자의 총합을 갖고 있는다.
n스테이지 성공자 수 구하는 공식 len(stages배열) /* 총 게임 참여자 수 */ - stages배열.count(n) /* n스테이지 실패자 */ - { (n-1 스테이지 실패자 ) + (n-2 스테이지 실패자) + ... + (0 스테이지 실패자) } /* 0~n-1 스테이지 실패자 합 */
시도 배열[n] = 성공자배열[n] + 실패자배열[n]
작성 코드
def solution(N, stages):
answer = []
successCount = [0 for i in range(0,N)]
tryCount = [0 for i in range(0,N)]
failCount = [0 for i in range(0,N)]
sumFailPeople = 0
totalPeople = len(stages)
for stage in range(1, N+1):
failCount[stage-1] = stages.count(stage)
successCount[stage-1] = totalPeople - failCount[stage-1] - sumFailPeople
tryCount[stage-1] = successCount[stage-1] + failCount[stage-1]
sumFailPeople += failCount[stage-1]
result = [{'idx' : idx, 'fail' : f, 'try' : tryCount[idx]} for idx, f in enumerate(failCount)]
failRatio = []
for i in result:
value = 0
if i['fail'] != 0:
value = i['fail']/i['try']
failRatio.append({'idx' : i['idx'], 'value' : value})
answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
return answer
참고 (시간 제한 오류난 케이스)
def solution(N, stages):
answer = []
successCount = [0 for i in range(0,N+1)]
tryCount = [0 for i in range(0,N+1)]
for man in stages:
for i in range(0,man):
tryCount[i] += 1
if i != man-1:
successCount[i] += 1
failCount = [tryCount[idx]-i for idx,i in enumerate(successCount)]
result = [{'idx':idx,'fail':f,'try':tryCount[idx]} for idx,f in enumerate(failCount) if idx != len(failCount)-1]
failRatio = []
for i in result:
value = 0
if i['fail'] != 0:
value = i['fail']/i['try']
failRatio.append({'idx' : i['idx'], 'value' : value})
answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
return answer
relation의 컬럼(column)의 길이는1이상8이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
relation의 로우(row)의 길이는1이상20이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
relation의 모든 문자열의 길이는1이상8이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
유일성 :
2차원 배열로 들어온 relation[row][col]의 값 중 col이 같은 값을 하나의 set에 넣어서 검증하면 된다고 생각했다.
여러 col의 조합이 유일한지 확인하기 위해서는 인위적인 조작이 필요하다고 생각했다.
컴럼들의 경우의 수를 모두 얻은 후에 각 값들의 유일성을 검증하기로 했다.
itertools의 combinations를 사용해서 col의 모든 조합을 만든다.
반복문으로 col의 조합을 가져와서 합친 쳐서 하나의 tempCol을 만들고 set에 넣어서 개수를 확인한다. ex) 1,2 조합이라면 set(["100ryan","200apeach","300tube","400con","500muzi","600apeach"])
개수가 원래 row의 수와 동일하면 유일성이 보장된 것이기 때문에 따로 저장해둔다.
최소성 :
유일함이 보장된 조합에서 최소성을 검증한다.
리스트 내에서 부분집합을 갖고 있다면 최소성 조건에 맞지 않기 때문에 삭제 대상 set에 넣는다.
유일성이 보장된 그룹의 수에서 삭제 대상의 수를 뺀다.
작성 코드
from itertools import combinations
def solution(relation):
answer = 0
# 모든 컬럼의 조합 리스트
all = list()
#유일성 만족하는 조합 리스트
uniqeIndex = []
if len(relation) > 0:
# 컬럼의 개수
colSize = len(relation[0])
# 로우의 개수
rowSize = len(relation)
# 모든 컬럼의 조합 구하기 (Set형태)
for i in range(1, colSize + 1):
# append는 런타임에러가 뜸 append와 extend 비교하여 알아둘 것
all.extend([set(k) for k in combinations([j for j in range(colSize)], i)])
# 조합들의 유일성 검증
for comb in all:
#set에 추가하여 사이즈 비교로 검증
vaildSet = set()
# 조합에 해당되는 로우를 하나의 str로 합쳐서 set에 넣음
for row in range(rowSize):
temp = ''
for col in comb:
temp += relation[row][col]
vaildSet.add(temp)
# 유일성 확인하여 리스트에 추가
if len(vaildSet) == rowSize:
uniqeIndex.append(comb)
# 최소성 검증
# 삭제대상 Set (최소성 위배)
delSet = set()
#부분집합 여부 확인
for stdMinElem in uniqeIndex:
for idx, compMinElem in enumerate(uniqeIndex):
# 부분집합이면서 자기 자신이 아니라면 상위집합을 삭제 대상에 추가
if stdMinElem.issubset(compMinElem) and stdMinElem != compMinElem:
delSet.add(uniqeIndex.index(compMinElem))
# 유일성 - 최소성 위배
answer = len(uniqeIndex)-len(delSet)
return answer
