전처리 방법: '각각의' 항목(개발언어, 직군, 경력, 소울푸드)에 대하여
'무관'인 경우도 테이블에 저장
예)
"java backend junior pizza 150"
라는 info가 들어오면,
"java backend junior - 150"
"java backend - pizza 150"
"java - junior pizza 150"
"- backend junior pizza 150"
"java backend - - 150"
"java - - pizza 150"
"- - junior pizza 150"
...
"- - - - 150"
처럼 각각의 항목이 무관일 수 있는 모든 경우의 수에 대하여 테이블에 저장해야함
이를 코드로 나타내면 다음과 같다.
for i1 in [0,lang]:
for i2 in [0,group]:
for i3 in [0,career]:
for i4 in [0,food]:
idx = 27*i1 + 9*i2 + 3*i3 + i4
table[idx][score] += 1
처음엔 4중 for문으로 구현하는 게 맞는건가? 했는데
생각해보면 4중 for문이라 해도 16번 밖에 안되기 때문에 상관없음!
우선 info 마다
table[idx][score] += 1
하고,score-1
99999부터 0까지 반대로 더해주기(누적합)
(table[idx][score]
는 idx 조건에서 score점 이상인 사람의 수)for idx in range(108): for score in range(100000,0,-1): # score-1 범위: 99999~0 table[idx][score-1] += table[idx][score]
l1 = ["-", "cpp", "java", "python"]
l2 = ["-", "backend", "frontend"]
l3 = ["-", "junior", "senior"]
l4 = ["-", "chicken", "pizza"]
table = [ [0]*100001 for _ in range(108) ] # 4*3*3*3
def solution(infos, queries):
for info in infos:
# "java backend junior pizza 150"
info = info.split()
lang,group,career,food,score = l1.index(info[0]),l2.index(info[1]),l3.index(info[2]),l4.index(info[3]),int(info[4])
# 무관(-)에 대해서도 기록해야 하기 때문
for i1 in [0,lang]:
for i2 in [0,group]:
for i3 in [0,career]:
for i4 in [0,food]:
idx = 27*i1 + 9*i2 + 3*i3 + i4
table[idx][score] += 1
# 누적합(table[idx][score]=idx 조건에서 score점 이상인 사람의 수. 따라서 반대로 합해야함)
for idx in range(108):
for score in range(100000,0,-1):
# 99999~0
table[idx][score-1] += table[idx][score]
answer = []
for query in queries:
query = query.split()
# "java and backend and junior and pizza 100"
# "cpp and - and senior and pizza 250"
lang,group,career,food,score = l1.index(query[0]),l2.index(query[2]),l3.index(query[4]),l4.index(query[6]),int(query[7]) # 복붙조심..
idx = 27*lang + 9*group + 3*career + food
answer.append(table[idx][score])
return answer
풀이 1과 다르게
table
의 원소를 리스트 형태로 만들고, info마다 맞는 자리에 넣어주고for i1 in [0,lang]: for i2 in [0,group]: for i3 in [0,career]: for i4 in [0,food]: table[i1][i2][i3][i4].append(score)
정렬하기
for i1 in range(4): for i2 in range(3): for i3 in range(3): for i4 in range(3): table[i1][i2][i3][i4].sort()
** info 배열의 크기가 최대 50000이기 때문에 풀이 1보다 훨씬 빠름
from bisect import bisect_left
l1 = ["-", "cpp", "java", "python"]
l2 = ["-", "backend", "frontend"]
l3 = ["-", "junior", "senior"]
l4 = ["-", "chicken", "pizza"]
table = [ [ [[[] for _ in range(3)] for _ in range(3)] for _ in range(3)] for _ in range(4) ]
def solution(infos, queries):
# info는
for info in infos:
# "java backend junior pizza 150" # 무관(-)인 입력은 들어오지 않지만
info = info.split()
lang, group, career, food, score = l1.index(info[0]), l2.index(info[1]), l3.index(info[2]), l4.index(info[3]), int(info[4])
for i1 in [0,lang]: # 무관에 대해 처리해야함(인덱스 0)
for i2 in [0,group]:
for i3 in [0,career]:
for i4 in [0,food]:
table[i1][i2][i3][i4].append(score)
# 정렬
for i1 in range(4):
for i2 in range(3):
for i3 in range(3):
for i4 in range(3):
table[i1][i2][i3][i4].sort()
answer = []
# 무관이면 인덱스 0
for query in queries:
query = query.split()
i1,i2,i3,i4,score = l1.index(query[0]), l2.index(query[2]), l3.index(query[4]), l4.index(query[6]), int(query[7])
answer.append(len(table[i1][i2][i3][i4])-bisect_left(table[i1][i2][i3][i4],score))
return answer
풀이1의 경우 table을 2차원으로 만들었고, 풀이2의 경우 4차원으로 만들었다.
(뭘 쓰던 상관없지만, 최대한 다양하게 풀어보고 싶어서 다르게 만들었다)
- 2차원으로 만드는 경우
idx
를27*i1 + 9*i2 + 3*i3 + i4
으로 변환해야한다. 이때table
은table[idx][score]
이런식으로 접근한다.- 4차원으로 만드는 경우 따로 변환할 필요없이
table[i1][i2][i3][i4]
로 쓰면 된다.
- 워낙 다양한 방법으로 구현할 수 있기 때문에 오히려 풀기 어려웠다.
(내가 푸는 방법이 맞나? 계속 생각했음)
이럴 때는 처음 생각했던 방법 그대로 뚝심 있게 푸는 게 좋은 전략같다!