[hash]99클럽 코테 스터디 9일차 TIL + 백준/Bronze/9933. 민균이의 비밀번호

문제 설명

창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다.

파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다.

예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다.

민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

 

 

### 입력

첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다. 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

 

 

### 출력

첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.


<내 코드>

import sys
from collections import defaultdict

N = int(sys.stdin.readline())
pws_dict = defaultdict(str)
answer = ""

for _ in range(N):
    s = sys.stdin.readline().strip()
    if len(s) % 2 == 0 :
        continue
    pws_dict[s] = s[::-1]

for k in pws_dict.keys():
    if pws_dict[k] in pws_dict:
        answer = k

sys.stdout.write(str(len(answer)))
sys.stdout.write(" "+answer[len(answer)//2])

- 이번에는 특정 조건 만족하지 않는 내용은 아예 dict에 안담았음

 

- 역순 정렬 s[::-1] 을 알게됨

 

- [len(answer)//2] 이 방식을 생각해서 뿌듯

 

- 아쉬운점

1. 조금만 더 생각하고 했으면 검증 부분에 대해서 내용 줄이기 가능했음

2. 답은 하나이기 때문에 찾는 즉시 곧바로 아래 반복문 break 해도 충분

3. 반대문자열 저장할 필요없음

 

 

<모범사례>

import sys

N = int(sys.stdin.readline().strip())
pws_dict = {}

for _ in range(N):
    word = sys.stdin.readline().strip()
    reversed_word = word[::-1]
    
    # 비밀번호와 반대 문자열이 모두 존재하면 답으로 설정
    if reversed_word in pws_dict:
        length = len(word)
        middle_char = word[length // 2]
        print(f"{length} {middle_char}")
        break
    else:
        pws_dict[word] = reversed_word

- 받는 즉시 곧바로 반대 문자열 존재하는지 검증하는 방법이고, 존재여부로 조건문으로 분기처리 하면 수월함

- 그리고 출력은 문자열 포매팅 방식으로 가능함

- 훨씬 단순

 

 

<보충학습>

 

1. 파이썬의 set()은 hash로 구현되어있음

그렇기 때문에 O(1)의 시간복잡도 가

import sys

N = int(sys.stdin.readline().strip())
pws_set = set()  # 해시 테이블 기반의 집합 사용

for _ in range(N):
    word = sys.stdin.readline().strip()
    reversed_word = word[::-1]

    # 반대 문자열이 이미 집합에 존재하면 비밀번호로 설정
    if reversed_word in pws_set:
        length = len(word)
        middle_char = word[length // 2]
        print(f"{length} {middle_char}")
        break
    else:
        pws_set.add(word)  # 단어를 집합에 추가

- 이렇게 set으로 해도 문제 취지에 부합하는 것임