[programmers 72412] 2021 공채 3번 순위검색

savannah030·2022년 4월 12일
0

코딩테스트

목록 보기
1/5

문제

[programmers 72412] 순위검색

전처리

전처리 방법: '각각의' 항목(개발언어, 직군, 경력, 소울푸드)에 대하여
'무관'인 경우도 테이블에 저장

예)
"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번 밖에 안되기 때문에 상관없음!

풀이1(누적합)

우선 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

풀이2(이진 탐색)

풀이 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

table 2차원 vs 4차원 ?

풀이1의 경우 table을 2차원으로 만들었고, 풀이2의 경우 4차원으로 만들었다.
(뭘 쓰던 상관없지만, 최대한 다양하게 풀어보고 싶어서 다르게 만들었다)

  1. 2차원으로 만드는 경우 idx27*i1 + 9*i2 + 3*i3 + i4으로 변환해야한다. 이때 tabletable[idx][score] 이런식으로 접근한다.
  2. 4차원으로 만드는 경우 따로 변환할 필요없이 table[i1][i2][i3][i4] 로 쓰면 된다.

느낀점

  • 워낙 다양한 방법으로 구현할 수 있기 때문에 오히려 풀기 어려웠다.
    (내가 푸는 방법이 맞나? 계속 생각했음)
    이럴 때는 처음 생각했던 방법 그대로 뚝심 있게 푸는 게 좋은 전략같다!
profile
백견이불여일타

0개의 댓글