[BOJ] 25327번: 다중 항목 선호도 조사(Large)

출처 : https://www.acmicpc.net/problem/25327

25327번: 다중 항목 선호도 조사 (Large)

 

 

 

1. 문제 설명 

n(n명의 학생)이 주어진다. 각 학생은 세 가지 항목 각각에 대해 반드시 1가지를 선택한다.

 

n명 학생의 선호도에 대하여 m개의 질의를 순서대로 처리한다. 

• 질의 형식은 'subject fruit color'이다.
• subject은 'kor', 'eng', 'math', '-' 중 하나이다.
• fruit은 'apple', 'pear', 'orange', '-' 중 하나이다.
• color는 'red', 'blue', 'green', '-' 중 하나이다.
• '-' 표시는 해당 조건을 고려하지 않겠다는 의미이다.
• n명 학생 중 선호도가 subject fruit color와 일치하는 학생 수를 출력한다.

n명 학생의 선호도와 m개의 질의가 주어지면, m개의 질의를 순서대로 출력하자.

 

 

 

2. 접근 방식 

처음에 접근한 방식은 브루트포스였다. 각 질의에 따라 n명의 학생의 선호도를 모두 살펴보는 방식이였는데, 어김없이 시간 초과가 났다. 사실 그 이후로 문제를 어떻게 접근해야 할 지 떠오르지가 않았다. 고수님들의 도움을 받아 미리 전처리를 해주라는 힌트를 얻었다. (그래도 이해하지 못했다... 나는 문어.. 꿈을 꾸는 문어) 오랜 시간 고민 끝에 n명의 학생의 선호도에 대한 모든 경우의 수를 만들어주고, 각 학생의 선호도를 입력받아서 해당 경우의 수에 1을 더해준다. (해당 경우의 수가 존재한다.) 그리고 m개의 질의에 대해서 처리해줬다. m개의 질의 중에서 '-'가 존재하는 항목이 있다면(해당 조건을 고려하지 않는다. 즉, 어떤 항목을 고르던 상관없다.)  해당 항목에 대한 모든 경우의 수를 더해준다. 

 

ex) 

각 학생의 선호도 중에서 eng - -,  kor apple red, kor pear - 가 존재하고 kor - - 라는 질의가 존재한다고 가정한다면 해당 질의와 일치하는 학생은 2명(kor apple red, kor pear -)이다. 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
s = ['kor', 'eng', 'math']
f = ['apple', 'pear', 'orange']
v = ['red', 'blue', 'green']
cnt = {}
for i in s:
    for j in f:
        for k in v:
            cnt[(i, j, k)] = 0

for _ in range(n):
    a, b, c = input().split()
    cnt[(a, b, c)] += 1

for _ in range(m):
    a, b, c = input().split()
    ans = 0
    if a == '-':
        a = s
    else:
        a = [a]

    if b == '-':
        b = f
    else:
        b = [b]

    if c == '-':
        c = v
    else:
        c = [c]

    for i in a:
        for j in b:
            for k in c:
                ans += cnt[(i, j, k)]

    print(ans)

 

 

4. 분석 및 시간복잡도 

시간복잡도 : O(N+M) => 10^5 + 10^5 * 27