[백준 2224번] 파이썬 - 명제 증명

백준 2224 - 명제 증명

시간 제한 2초, 메모리 제한 128MB

# 조건

• 수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다.
  • 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.
• 논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다.
• 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.
• 어떤 참인 명제가 주어졌을 때, 이 명제가 참이므로 이 명제 자체도 증명될 수 있다고 할 수 있다.
• 하지만 “P => P”와 같은 명제는 항상 참이 되는데, 이런 식으로 전건과 후건이 같은 경우는 출력하지 않기로 한다.
• N개의 참인 명제들이 주어졌을 때, 증명될 수 있는 명제를 모두 구해내는 프로그램을 작성하시오.
  • 명제를 증명하는 방법은 여러 가지가 있을 수 있지만, 위에서 언급한 방법만을 사용하기로 한다.

입력

• 첫째 줄에 정수 N(1 ≤ N ≤ 10,000)이 주어진다.
• 다음 N개의 줄에는 참인 명제들이 주어진다.
• 명제는 "P => Q"의 꼴로 주어지는데, “=>”는 앞뒤가 공백으로 구분되어 있다.
• P나 Q는 명제를 나타내는 문자인데, 알파벳 대소문자 한 글자를 사용한다.
• 같은 명제가 여러 번 주어질 수도 있다.

출력

• 첫째 줄에 출력할 명제의 개수 X개를 출력한다.
• 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다.
• 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으로 정렬한다.
• 알파벳은 대문자가 소문자에 우선한다.
  • 즉, 정렬했을 때 A, B, …, Z, a, b, …, z 순서로 나와야 한다.

# 접근 방법

• 우선 입력받으면서 전건과 후건이 같지 않다면 islower를 사용하여 대소문자 판별을 해주고 아스키코드로 변환해준다.
  • 0번의 인덱스부터 025 => 대문자, 2651 => 소문자로 사용하기 위하여 대문자의 경우 - 65, 소문자의 경우 - 71을 해준다.
• 변환한 숫자를 alpha[i][j] 에 명제가 존재한다는 표시를 해준다.
• 이후 3중 for문을 돌건데 i => 겹치는 부분, j => 전건, k => 후건으로 사용해준다.
  • 따라서, 전건과 후건이 같지 않고 j != k
  • alpha[전건][겹치는 부분] 이 존재하고 alpha[j][i]
  • alpha[겹치는 부분][후건]이 존재한다면 alpha[i][k]
  • alpha[전건][후건]을 존재한다고 표시해준다.
• 이후 alpha 배열을 돌며 [i][j] 값이 존재한다면 아스키 코드로 다시 변환하여 result 배열에 넣어준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
get_lower = lambda x: int(ord(x)) - 71  
get_upper = lambda x: int(ord(x)) - 65  

alpha_lower = lambda x: chr(x+71)  
alpha_upper = lambda x: chr(x+65)  

alpha = [[0] * 52 for _ in range(52)]  
for _ in range(N):  
    a, b, c = input().rstrip().split()  
    if not a == c:  
        a = get_lower(a) if a.islower() else get_upper(a)  
        c = get_lower(c) if c.islower() else get_upper(c)  

        alpha[a][c] = 1  

result = []  

for i in range(52):  
    for j in range(52):  
        for k in range(52):  
            if not j == k and not alpha[j][k] and alpha[j][i] and alpha[i][k]:  
                alpha[j][k] = 1  

for i in range(52):  
    for j in range(52):  
        if alpha[i][j]:  
            val1 = alpha_upper(i) if i <= 25 else alpha_lower(i)  
            val2 = alpha_upper(j) if j <= 25 else alpha_lower(j)  
            result.append(f'{val1} => {val2}')  

print(len(result))  
print(*result, sep='\n')