[파이썬] 백준 1411: 비슷한 단어 (실버2)

[파이썬] 백준 1411: 비슷한 단어 (실버2)

 

1411번: 비슷한 단어

---

문제

---

풀이

0. 접근방식

소문자 배열이 들어온다. 처음 등장하는 단어에 맞추어서 단어를 새롭게 매핑하면 다른 단어로 바꿀 수 있다.

이 매핑한 단어를 딕셔너리에 저장하면 같은 타입의 단어가 등장하면 알 수 있다.

 

1. 입력받기

N = int(input())
table = {}
for i in range(N):
    string = input()
    capital = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
    temp,s = {},''

소문자만 들어온다는 조건이 있으므로 대문자로 매핑하면 알파벳에 맞추어서 매핑이 가능하다.

전체 단어를 받아서 table에 결과를 넣는다.

 

2. 단어매핑 / 딕셔너리 추가

    for word in string : # 들어온 단어를 매핑
        if word not in temp :
            temp[word] = capital[0]
            capital.pop(0)
        s += str(temp[word])

    if s not in table : # 매핑을 tabel에 추가
        table[s] = 1
    else :
        table[s] += 1

내부 for문에서 들어온 단어를 한 단어씩 매핑해주고 한 번 나온 단어는 pop을 통해 다음 알파벳이 매핑될 수 있게 한다.

임의의 문자열 s에 매핑된 결과를 더해준다

매핑된 s가 테이블에 존재 할 경우 개수를 세주고 없을 경우 새로 추가한다.

 

3. 단어매핑 / 딕셔너리 추가

similar = list(table.values())
answer = 0
for i in similar :
    answer += (i*(i-1))/2 # nC2
print(int(answer))

정답인 쌍을 출력하기 위해 table의 value값만 가져오고 for문을 돌면서 쌍의 개수를 세준다.

---

전체코드

N = int(input())
table = {}
for i in range(N):
    string = input()
    capital = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
    temp,s = {},''
    
    for word in string : # 들어온 단어를 매핑
        if word not in temp :
            temp[word] = capital[0]
            capital.pop(0)
        s += str(temp[word])

    if s not in table : # 매핑을 tabel에 추가
        table[s] = 1
    else :
        table[s] += 1
        
similar = list(table.values())
answer = 0
for i in similar :
    answer += (i*(i-1))/2 # nC2
print(int(answer))

 

브루트포스처럼 풀지는 않은거같은데 태그가 브루트포스니까..