Python Algorithm) Dictionary 자료형을 이용한 알고리즘 문제
단어 찾기
현수는 영어로 시는 쓰는 것을 좋아합니다.
현수는 시를 쓰기 전에 시에 쓰일 단어를 미리 노트에 적어둡니다.
이번에는 N개의 단어를 노트에 적었는데 시에 쓰지 않은 단어가 하나 있다고 합니다. 여러분이 찾아 주세요.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=100)이 주어진다.
두 번째 줄부터 노트에 미리 적어놓은 N개의 단어가 주어지고, 이어 바로 다음 줄부터 시에 쓰인 N-1개의 단어가 주어진다.
▣ 출력설명
첫 번째 줄에 시에 쓰지 않은 한 개의 단어를 출력한다.
▣ 입력예제
1 5
big
good
sky
blue
mouse
sky
good
mouse
big
▣ 출력예제
1
blue
내 풀이)
처음에 문제가 너무 단순한데? 싶어서 hash를 사용해야한는 건가 해서 hash fucntion을 직접 만들고, 충돌 해결을 위해 Linear Probing로 해보고 했지만.. 너무 꼬아서 생각하고 있다는 느낌이 들었다.
그냥 dict형식을 사용하면 되는 거였다.
이 문제에서 더 배운 것은 'python에서 Value로 Key찾기'
pythone의 dictionary 자료형 메서드 중 key와 value를 한꺼번에 for문을 반복하려면 items() 를 사용한다.
word_dict = {'big': 1, 'good': 1, 'sky': 1, 'blue': 0, 'mouse': 1}
print(word_dict.items())
#실행 결과: dict_items([('big', 1), ('good', 1), ('sky', 1), ('blue', 0), ('mouse', 1)])
그래서 이 .items()을 사용해서 배열 형태로 된 것을 for문을 돌면서 value를 검사해주면 된다.
for k, v in word_dict.items():
if value == 0:
print(key)
break처음에
not_used = [k for k, v in word_dict.items() if v==0]
print('not_used: ', not_used[0])이런식으로 코드를 짰었는데 어짜피 사용하지 않은 단어는 하나밖에 없으니 이 코드 보다는 위에서 if문으로 중간에 걸러주는 코드가 공간상으로나 시간상으로 더 좋은 것 같다.
코드)
n = int(input())
word_dict = {}
# 노트에 적은 단어를 입력시마다 0으로 dict에 input
for i in range(n):
key = input()
word_dict[key] = 0
# 시에 쓰인 단어를 입력시ㅣ마다 1로 수정(사용했다는 의미)
for i in range(n-1):
used_key = input()
word_dict[used_key] = 1
# 이제 word_dict에서 value가 여전히 0인(사용되지 않은) key인 단어를 출력
for k, v in word_dict.items():
if v == 0:
print(k)
break
# not_used = [k for k, v in word_dict.items() if v==0]
# print(not_used[0])
Anagram(아나그램 : 구글 인터뷰 문제)
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.
▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.
▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.
▣ 입력예제 1
AbaAeCe
baeeACA
▣ 출력예제 1
YES
내 풀이 1)
이 문제도 크게 어렵지 않다. 위의 문제와 다른 점은 key가 있는지 없는지 유무만 체크해주는게 아니라 개수를 세어야 한다는 것이다.
이 때도 dictionary 자료형의 함수들을 적절하게 사용할 수 있는가에 대해서 더 많이 배운 문제였다.
대표적으로
for i in str1:
if i in str1_dict:
str1_dict[i] += 1
else:
str1_dict[i] = 0이렇게 count해 주는 것을 .get() 메소드를 사용하면
for i in str1:
str1_dict[i] = str1_dict.get(i, 0)+1
# str1_dict에 i에 해당하는 알파벳이 key값으로 있니?
# 없으면 0
# 있으면 1누적이렇게 간단하게 적을 수 있다.
코드 1)
str1 = input()
str2 = input()
str1_dict = dict()
str2_dict = dict()
for i in str1:
str1_dict[i] = str1_dict.get(i, 0)+1
for i in str2:
str2_dict[i] = str2_dict.get(i, 0)+1
if str1_dict == str2_dict:
print("YES")
else:
print("NO")
내 풀이 2)
이 문제를 딱 처음 봤을 때 'str1_dict에서 count한 것을 str2를 돌면서 str2_dict를 또 만들지 말고, 그냥 str1_dict의 count를 반대로 지워나가면 되지 않을까? 라고 생각했다가 그냥 위의 방법이 더 쉬울 것 같아서 풀이 1대로 했다.
그런데 생각해 보니 풀이2 방법이 공간상 dict를 하나 덜 쓰기 때문에 더 좋은 방법인거 같아서 이 풀이도 한번 구현해 보고자 한다.
그냥
풀이 1의
str2_dict = dict()을 없애고
for i in str2:
str2_dict[i] = str2_dict.get(i, 0)+1 을
for i in str2:
str1_dict[i] = str1_dict.get(i, 0)-1 로 고쳐준다. 그리고 검사할ㄹ 때는
str1_dict에 value값이 1이상인 것이 남아있으면 이것은 아나그램이 아닌 것이다.
코드)
str1 = input()
str2 = input()
str1_dict = dict()
for i in str1:
str1_dict[i] = str1_dict.get(i, 0)+1
for i in str2:
str1_dict[i] = str1_dict.get(i, 0)-1
for cnt in str1_dict:
if str1_dict.get(cnt) >=1:
print("NO")
break
else:
print("YES")
reference
17. dictionary(딕셔너리) - 파이썬 - 기본을 갈고 닦자! - WikiDocs