제로베이스 20220531 코테 연습
-
오프라인 수업에서 제공되었던 코드테스트 문제들이다.
-
연습하고나서 비공개로 두려니 억울해서 올리기로 했다.
문자열 조작
1. 문자열 압축
- 알파벳 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는 경우 반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하는 프로그램을 작성하세요.
- 단, 반복횟수가 1인 경우 생략합니다.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이
def solution(s):
answer = ""
s += " "
cnt = 1
for i in range(len(s)-1):
if s[i] == s[i+1]:
cnt += 1
else:
answer += s[i] + str(cnt) if cnt > 1 else s[i]
cnt = 1
return answer
print(solution("AAABCCCDD"))
리뷰
- 앞문자와 같다면 cnt + 1, 다르다면 cnt를 뒤에 달아준다.
- 이때, cnt가 1이라면 cnt없이 문자만 표기한다.
2. 문자열 압축
- 앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 회문 문자열이라고 합니다.
- 문자열이 입력되면 해당 문자열이 회문 문자열이면 “YES”, 회문 문자열이 아니면 “NO”를 출력하는 프로그램을 작성하세요.
- 단, 회문을 검사할 때 대소문자를 구분하지 않습니다.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이 1(실전용)
def solution(s):
answer = ""
s = s.lower()
if s == s[::-1]:
answer = "YES"
else:
answer = "NO"
return answer
print(solution("AAABCCCDD"))
리뷰
- 실제로는 이렇게 푸는게 가장 빠르고 편하다.
- 다만, 수업에서는 제약조건이 추가되어 다른 코드를 작성했다.
제한사항 2
- [::-1]을 이용해 문자열을 뒤집는것을 금지합니다.
풀이 2.
def solution(s):
answer = ""
s = s.lower()
for i in range(len(s)//2):
if s[i] != s[len(s)-i-1]:
answer = "NO"
break
else:
answer = "YES"
return answer
print(solution("AAABCCCDD"))
리뷰
- 하나의 포인터를 이용해 문자열의 양끝을 검사하며 좁혀나가는 방식으로 작성했다.
풀이 3. (강사님 풀이)
def solution(s):
# prof's solve
answer = "YES"
s = s.upper()
lt = 0
rt = len(s)-1
while lt < rt:
if s[lt] != s[rt]:
return "NO"
else:
lt += 1
rt -= 1
return answer
print(solution("AAABCCCDD"))
리뷰
-
lt와 rt 두 포인터를 활용해 양 끝단을 비교하는 방식으로 진행되었다.
-
포인터를 두개 사용하는 만큼, lt와 rt를 이용한 제한을 이용해 반복횟수를 제어하는것이 특징.
3. 특정 문자 뒤집기
- 영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고, 특수문자는 자기자리에 그대로 있는 문자열을 만들어 반환하는 프로그램을 작성하세요.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이
def solution(s):
answer = ""
l = list(s)
lt = 0
rt = len(s)-1
while lt < rt:
# s[lt].isalpha()를 사용해도 된다.
if 65 > ord(s[lt]) or 122 < ord(s[lt]):
lt += 1
continue
if 65 > ord(s[rt]) or 122 < ord(s[rt]):
rt -= 1
continue
tmp = l[lt]
l[lt] = l[rt]
l[rt] = tmp
lt += 1
rt -= 1
answer = ''.join(l)
return answer
print(solution("###ab*@@Sty"))
리뷰
-
lt와 rt를 이용해 각 위치의 문자가 특수문자인지 여부를 체크하며 진행되었다.
-
내가 푼 방법은 ord()함수를 활용하여 아스키코드로 변환, 범위를 체크하는것이었다.
-
강사님은 isalpha()를 통해 더 편하게 검사하는 방법을 제시했고, 솔직히 내가봐도 이게 맞는것 같다.
-
검사한 알파벳의 위치를 변경하고, 포인터 위치를 조작하면 끝.
4. 회문문자열2
- 문자열 s가 주어지면 s가 최대 문자 1개까지 지워서 회문문자열이 되면 “YES”를 출력하고, 그 렇지 않으면 ”NO”를 출력하는 프로그램을 작성하세요.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이 1
def solution(s):
answer = ""
answer = "NO"
for i in range(len(s)):
new_s = s[:i] + s[i+1:]
if new_s == new_s[::-1]:
return "YES"
return answer
print(solution("abcacbakcba"))
리뷰
-
문자 하나를 제거한 문자열을 만들어 그것이 회문인지 비교하는 방식이다.
-
이 방식은 문자열의 길이만큼 반복문을 돌려야한다는 단점이 있다.
- 물론, 이번 문제의 제한사항에서 길이를 100으로 줬으니 사용해도 시간상의 문제는 안걸릴듯 하다.
풀이 2
def solution(s):
answer = ""
lt,rt사용
answer = "YES"
for i in range(len(s)):
new_s = s[:i] + s[i + 1:]
lt = 0
rt = len(new_s) - 1
while lt < rt:
if new_s[lt] != new_s[rt]:
return "NO"
lt += 1
rt -= 1
return answer
print(solution("abcacbakcba"))
리뷰
-
위와 기본적인 틀은 같지만, 포인터 두개를 사용하여 푼 버전이다.
-
역시 문자열을 매 반복문마다 생성해야하고, 반복문을 문자열 길이만큼 돌아야 한다는건 동일한 문제점이다.
풀이 3
def solution(s):
answer = "YES"
for i in range(len(s)):
lt = 0
rt = len(s) - 1
while lt < rt:
if s[lt] != s[rt]:
return "NO"
lt += 1
rt -= 1
if lt == i:
lt += 1
if rt == i:
rt -= 1
return answer
print(solution("abcacbakcba"))
리뷰
-
포인터를 이왕 쓰는 김에,
포인터를 한칸씩 더 움직여 해당 위치의 글자가 없는것과 같은 효과
를 주는 식으로 짜본 코드다. -
풀이 2에 비해 그나마 나아진 점이라면, 매번 새로 문자열을 생성할 필요가 없어 메모리적인 부분에서 조금 효율성이 올라간 정도?
-
물론 근본적인 문자열 길이만큼 반복해야한다는 문제는 해결 못했다.
풀이 4 (강사님 풀이)
def solution(s):
answer = "YES"
left = 0
right = len(s)-1
while left < right:
if s[left] != s[right]:
s1 = s[left:right]
s2 = s[left+1:right+1]
if s1 != s1[::-1] and s2 != s2[::-1]:
return "NO"
left += 1
right -= 1
return answer
print(solution("abcacbakcba"))
리뷰
-
포인터를 활용해 양 끝의 문자부터 비교해 들어간다.
-
이때 양쪽에 위치한 문자가 다르다면 해당 글자가 다르다는 말이 된다.
- 따라서, 왼쪽의 문자를 제거하는 경우의 문자열(s1, left:right)과 오른쪽의 문자를 제거하는 경우의 문자열(s2, left+1:right+1) 두가지가 각각 회문인지 체크한다.
-
s1과 s2모두 회문이 아닐 경우, 다른 글자가 하나 이상 더 있다는 의미이므로, NO를 리턴한다.
-
그 외의 경우에는 해당 글자를 제거시 회문이 되므로 YES를 리턴한다.
5. 회문문자열3
- 팰린드롬(palindrome, 회문)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다.
- 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다.
- 만일 그 자체는 회문이 아니지만 한 문자를 삭제
하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라
고 부른다.
- 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
- 여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다.
-
만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 반환해야 한다.
- 매개변수 s에 문자열 배열이 주어지면 각 문자열이 0, 1, 2중 어떤 것을 반환해야 하는지 숫자배열로 만들어 반환하는 프로그램을 작성하세요.
제한사항
- 문자열 배열 s의 길이는 30을 넘지 않습니다.
- s[i]의 길이는 100을 넘지 않습니다.
풀이
def solution(s):
answer = []
for string in s:
left = 0
right = len(string) - 1
if string == string[::-1]:
answer.append(0)
elif string[left] != string[right]:
s1 = string[left:right]
s2 = string[left + 1:right + 1]
if s1 != s1[::-1] and s2 != s2[::-1]:
answer.append(2)
else:
answer.append(1)
else:
answer.append(1)
return answer
print(solution(["abba",
"summuus",
"xabba",
"xabbay",
"comcom",
"comwwmoc",
"comwwtmoc"
]))
리뷰
-
앞에서 풀었던 문제들의 총집편이다.
-
4번 문제의 강사님 풀이가 제일 효율적인 풀이법이므로, 해당 방법을 베이스로 작성했다.
6. 공통문자가 없는 단어
- 문자열 배열이 주어지면 서로 공통문자가 없는 두 문자열을 선택해 두 문자열의 길이를 곱했을 때 최댓값을 반환하는 프로그램을 작성하세요.
- 공통문자가 없는 두 문자열이 없다면 0을 반환합니다.
제한사항
- 문자열 배열 s의 길이는 30을 넘지 않습니다.
- s[i]의 길이는 100을 넘지 않습니다.
풀이 1(내 풀이)
def solution(s):
answer = 0
# my solution
for i in range(len(s)):
for j in range(i+1,len(s)):
if not(set(s[i]) & set(s[j])):
value = len(s[i]) * len(s[j])
if answer < value:
answer = value
return answer
print(solution(["skudy", "kstue", "time", "back", "good"]))
리뷰
- set 자료형과 set 자료형의 교집합 연산을 활용해 겹치지 않는 문자열을 찾아내고, 해당 길이를 곱해 최대값과 비교하는 방식을 사용했다.
풀이 2(강사님 풀이)
def solution(s):
answer = 0
def isUnique(short,long):
for x in short:
if long.find(x) != -1:
return False
return True
answer = 0
n = len(s)
s.sort(key=lambda x: len(x))
for i in range(n):
for j in range(i+1,n):
if isUnique(s[i],s[j]):
tmp = len(s[i]) * len(s[j])
answer = max(answer,tmp)
return answer
print(solution(["skudy", "kstue", "time", "back", "good"]))
리뷰
-
문자열의 길이가 짧은순으로 정렬한다음, isUnique함수를 통해 문자열이 겹치는지 체크한다.
-
isUnique함수는 문자열의 find함수를 이용하여, 짧은 문자열을 이루는 글자가 긴 문자열 내에 존재할시 False를 리턴, 아닐시 True를 리턴하는 함수이다.
- 문자열의 find함수 : 해당 문자가 문자열 안에 존재할시 인덱스를 반환. 없으면 -1을 반환.
-
answer = max(answer,tmp)를 통해 최대값을 찾아 반환.
7. 학급 회장
-
학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.
-
투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다.
-
매개변수 s에 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 주어지면 어떤 기호의 후보가 학급 회장이 되었는지 반환하는 프로그램을 작성하세요.
-
반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이 1(내 풀이)
from collections import Counter
def solution(s):
# my solution
answer = [key for key,val in Counter(s).items() if val == max(Counter(s).values())][0]
return answer
print(solution("AAAAABBCCDDDD"))
리뷰
-
갑자기 발병한 한줄코딩병으로 인해 가독성을 희생하고 뭔가 잘해보이는것처럼 보이기를 선택해버렸다.
-
Counter를 활용해 각 문자가 나온 횟수를 찾는다.
-
이때, 조건문에 의해 Counter(s).values()의 최대값과 같은 val를 가지는 key값만 리스트 안에 들어가게 된다.
-
학급회장은 반드시 1명만 선출되므로, 결과로 나온 리스트는 무조건 1개의 값만 가지게 되며, 그 값은 0번 인덱스에 있다.
풀이 2(강사님 풀이)
def solution(s):
import collections
# defaultdict :
sH = collections.defaultdict(int)
for x in s:
sH[x]+=1
maxH = 0
for key in sH:
if sH[key] > maxH:
answer=key
return answer
print(solution("AAAAABBCCDDDD"))
리뷰
-
본래 강사님의 출제 의도는 해싱(hashing)을 사용하는 것이었다.
-
그래서인지, collections의 defaultdict를 사용해 딕셔너리를 생성하는것을 확인할수 있었다.
-
등장한 문자에 대해 해싱을 진행, 각 문자가 등장한 횟수를 기록하고, 최대값을 가진 키값을 리턴한다.
collections.defaultdict
-
생성자로 기본값을 지정해 넘겨주면 모든 키에 대해 값이 없는 경우 자동으로 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다.
-
예를들어, defaultdict(int)로 선언하고 키값을 넣으면, 키값이 존재하지 않는 키에 대한 value는 자동으로 0으로 설정된다는 뜻.
- 이때, int를 넘겨주는 이유는 int()는 0을 리턴해서 라고 한다.
-
이를 응용하면 빈 리스트나 set()을 기본값으로 설정하거나, 람다식을 활용해 특정한 값으로 기본값을 설정하는 등(lambda: 기본값)의 활용이 가능하다.
8. 한번 사용한 최초 문자
- 문자열에서 한번만 사용한 문자를 찾으려고 합니다.
- 한번만 사용한 문자 중 문자열에서 먼저 나타난 문자의 인덱스 번호를 반환하는 프로그램을 작성하세요.
- 인덱스는 1부터 시작합니다.
- 한번만 사용한 문자가 없을 경우 -1를 반환하세요.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
- 문자열은 소문자로만 이루어져 있습니다.
풀이 1 (내 풀이)
from collections import Counter
def solution(s):
# my solution
answer = [s.index(key) + 1 for key, val in Counter(s).items() if val == 1]
return answer[0] if answer else -1
print(solution("statitsics"))
리뷰
-
Counter를 활용해 한번만 나온 값(val == 1)을 가지는 키의 인덱스값을 가지는 리스트를 뽑아낸다.
-
인덱스는 1부터 시작하므로, s.index(key)에 1을 더해준다.
-
이 집합은 한번만 사용한 문자가 나오지 않는 경우 빈 리스트가 되므로 조건문을 통해 비어있다면 -1을 리턴, 비어있지 않다면 리스트의 첫번째 항목(=먼저 나타난 문자)를 출력한다.
풀이 2 (강사님 풀이)
import collections
def solution(s):
# prof's solutions
sH = collections.Counter(s)
for index, val in enumerate(sH):
if sH[val] == 1:
return index + 1
return -1
print(solution("statitsics"))
리뷰
-
Counter인 sH를 통해 해싱한다.
-
반복문을 돌려 문자열에 한번만 등장한 값(sH[val]==1)이 발견될 경우, index+1을 즉시 리턴한다.
-
내 풀이는 list comprehension이므로, 리스트를 한번 완성해야한다.
-
반면 강사님의 풀이는 반복문 도중에 조건만 만족되면 바로 리턴이 이루어진다.
-
따라서, 문자열의 길이가 제한사항에 걸린것보다 압도적으로 길어지게 될시 강사님의 방식은 내 풀이에 비해 결과값이 빠르게 나올것으로 예상된다.
9. 같은 빈도수 만들기
- 소문자 a, b, c로 이루어진 문자열이 주어지면 해당 문자열에서 a, b, c의 최소의 개수를 추가하여 a, b, c의 빈도수가 동일하게 되도록 해야 합니다.
- 동일빈도수가 되는 최소 추가 개수를알파벳 a, b, c순으로 배열에 저장하여 반환하는 프로그램을 작성하세요.
- 만약 주어진 문자열이 “aaabc” 라면 빈도수는 a:3 , b:1, c:1 이고 최소 개수를 추가하여 동일 빈도수가 되게 하려면 b를 2개 추가, c를 2개 추가하면 모두 빈도수가 3개로 동일해집니다.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이 (강사님 풀이)
from collections import Counter
def solution(s):
answer = []
# prof's solution
sH = Counter(s)
maxH=float('-inf')
for x in "abc":
if sH[x] > maxH:
maxH = sH[x]
for x in "abc":
answer.append(maxH-sH[x])
return answer
print(solution("aabb"))
리뷰
-
defaultdict를 활용해 거의 풀었으나, 문자열에 특정 문자가 존재하지 않는 경우에 대한 처리를 하지 못한 관계로, 내 풀이는 없다.
-
Counter를 이용해 문자열을 해싱하고, 문자열 안에서 가장 많이 나온 개수를 저장한다.
-
(가장 많이 나온 횟수) - (문자열에 등장한 횟수)를 저장하여 리턴한다.
-
Counter 내에 존재하지 않는 키값을 호출했는데도 KeyError가 발생하지 않았다.
-
통상적인 Dictionary와 달리 없는 키값에 대한 접근도 가능한건가 싶어, 간단한 실험을 진행해보았다.
-
번외. dictionary와 Counter의 차이 (접기/펼치기)
# Error 발생. KeyError : 'c'
dic = {'a':1,'s':1,'d':1}
print(dic['c'])
# 정상 실행. 0이 출력됨.
dic = Counter('asd')
print(dic['c'])
-
실험 결과 : Counter에 없는 키값은 보여주지 않았을 뿐, 0의 value를 기본값으로 가지고 있다.
- Counter의 결과값이 그냥 dictionary인줄 알았는데, 이제보니 defaultdict쪽에 좀 더 가까운것 같다.
10. 팰린드롬 길이
- 문자열이 주어지면 해당 문자열의 문자들을 가지고 만들 수 있는 최대길이 팰린드롬을 만들고 그 길이를 구하세요.
- 문자열은 소문자로만 이루어져 있습니다.
- 만약 “abcbbbccaa” 가 주어진다면 만들 수 있는 가장 긴 팰린드롬은 ”bbcaaacbb”이고 답은 9입니다.
제한사항
- 문자열 s의 길이는 100을 넘지 않습니다.
풀이 1 (내 풀이)
from collections import Counter
def solution(s):
answer = 0
c = Counter(s)
odd = []
for val in c.values():
if val % 2 == 1:
odd.append(val)
else:
answer += val
answer += max(odd)
odd.remove(max(odd))
for o_num in odd:
answer += o_num - 1
return answer
print(solution("aaaaaccc"))
리뷰
팰린드롬을 이루는 각 문자의 갯수는 짝수개이다.
- ex) “abba” => a 2개, b 2개
단, 딱 1종류의 문자는 홀수개 넣을수 있다.
- ex) “abcba” => a 2개, b 2개, c 1개
-
따라서, 주어진 문자열에서
(홀수번 등장한 문자중 제일 많이 등장한 횟수) + (홀수번 등장한 문자들의 횟수에서 1을 빼주어 짝수로 만든 경우 나오는 횟수의 총합) + (짝수번 등장한 문자들의 횟수)
가 가장 긴 팰린드롬의 길이가 된다. - odd에 홀수번 나온 문자들의 횟수를 저장한다.
-
짝수번 등장한 경우, 바로 answer에 더해준다.
-
odd에서 가장 큰 값(가장 많이 나온 홀수번 등장한 문자)를 answer에 더해준다.
- 나머지 홀수번 등장 문자들에 대해 횟수에 -1한값을 answer에 모두 더해주고, 리턴한다.
풀이 2 (강사님 풀이)
from collections import Counter
def solution(s):
answer = 0
sH = Counter(s)
cnt = 0
for x in sH:
if sH[x]%2 == 1:
cnt += 1
return len(s)-cnt+1 if cnt > 0 else len(s)
print(solution("aaaaaccc"))
리뷰
-
기본적인 이론의 토대는 같다.
-
강사님의 경우,
전체 길이에서 홀수번 등장한 문자의 갯수를 빼주고(홀수번 나온 문자들을 1씩 감소시킴), 1을 더함(홀수번 나온 문자중 가장 많이 나온 문자를 그대로 더함)
으로서 답을 구했다.- 물론, 홀수번 등장한 문자가 없을경우 전체 길이를 그대로 사용하셨다.
-
이쪽이 잡다한 계산이 없으므로 훨씬 빠를것으로 예상된다.
11. 음성 인식
- 음성 인식 기술을 사용하면 사람이 말하는 음성 데이터를 문자 데이터로 변환할 수 있습니다.
- 당신은 오늘의 집에 전화로 들어온 주문을 자동으로 처리하기 위해, 음성 데이터를 문자 데이터로 변환하려 합 니다.
- 당신은 이 문자 데이터를 쓰기 전에 먼저 반복적으로 사용된 말버릇 패턴을 삭제해야 합니다.
- 말버릇 패턴이란 문자 데이터에서 가장 많이 등장하는 길이 1 이상의 패턴이며, 문자 데이터에 등장하는 해당 패턴을 모두 삭제하면 됩니다.
- 단, 이러한 패턴은 대소문자를 구분하지 않으며, 가장 많이 등장한 패턴이 여러 개일 경우 그러한 패턴을 모두 삭제합니다.
-
다음은 문자 데이터에서 말버릇 패턴을 삭제하는 예시입니다.
삭제 전 삭제 후 “abcabcdefabc” “def” “abxdeydeabz” “xyz” - “abcabcdeabc”에서 ”abc”가 3번 등장하며, 가장 많이 등장한 패턴입니다.
- ”abc”를 삭제하면 “def”가 남게 됩니다.
- “abxdeydeabz”에서 “ab”와 ”de”가 2번 등장하며, 가장 많이 등장한 패턴입니다.
- “ab”와 ”de”를 삭제하면 “xyz”가 남게 됩니다.
- “abcabcdeabc”에서 ”abc”가 3번 등장하며, 가장 많이 등장한 패턴입니다.
- 음성 데이터를 문자 데이터로 변환한 문자열 cell이 매개변수로 주어집니다.
- 이때, 가장 많이 등장한 말버릇을 삭제한 결과를 문자열로 return하도록 solution 함수를 완성해주세요.
제한사항
- 3<= cell의 길이 <=1,000
- cell은 알파벳 대소문자로만 구성되어 있습니다.
- 가장 많이 등장하는 말버릇 패턴을 삭제했을 때, 남은 문자열의 길이가 1이상인 경우만 입력으로 주어집니다.
풀이 (강사님 풀이)
from collections import Counter
def solution(s):
# prof's solution
answer=''
tmp = s.lower()
sH=collections.defaultdict(int)
max_H = -1
for x in tmp:
sH[x] += 1
if sH[x] > max_H:
maxH=sH[x]
for i,x in enumerate(tmp):
if maxH>sH[x]:
answer += s[i]
return answer
print(solution("aaaaaccc"))
리뷰
-
가장 많이 나온 패턴은, 가장 많이 나온 문자이다.(패턴의 길이는 1 이상이다.)
- ‘abc’가 가장 많이 나온 패턴이라면, ‘a’,’b’,’c’가 가장 많이 나온 문자라는 의미가 된다.
-
패턴의 대소문자 구분에 대해 처리하지 못해 내 풀이는 올리지 못했다.
-
강사님의 경우, 문자열을 islower()처리하여 소문자로 만들어 tmp에 저장하고 tmp를 해싱한후, 가장 많이 나오는 문자의 갯수를 체크했다.
-
enumerate(tmp)를 통해 인덱스와 문자를 뽑아내고, 해당 문자가 가장 많이 나온 문자인지 체크한 후, 아니라면 s에서 해당 인덱스의 글자를 answer에 더해주는 방식으로 복원했다.
12. 공통문자찾기
- N개의 문자열이 주어지면 모든 문자열에 공통으로 들어있는 문자를 찾아 출력하는 프로그램을 작성하세요.
-
만약 어떤 문자가 모든 문자열에서 2번 나타난다면 답에서도 2번 나타나게 해야합니다.
-
문자열 배열 words가 주어지면 모든 문자열에 공통으로 들어있는 공통문자를 문자배열형태로 반환하는 프로그램을 작성하세요.
- 문자의 순서는 상관없습니다.
- 반드시 공통문자는 존재합니다.
제한사항
- 문자열 words의 길이는 30을 넘지 않습니다.
- words[i]의 길이는 100을 넘지 않습니다.
- 모든 문자열은 소문자로 이루어져 있습니다.
풀이 1 (내 풀이)
from collections import Counter
def solution(s):
answer = ""
common_keys = set(s[0])
l = []
for string in s:
common_keys = common_keys & set(string)
l.append(list(Counter(string).items()))
d = {x:y for x,y in zip(list(common_keys),[101] * len(common_keys))}
for value in l:
for key,val in value:
if key in common_keys:
if val < d[key]:
d[key] = val
print(list(''.join([x*y for x,y in zip(d.keys(),d.values())])))
return answer
print(solution(["longlong", "longtong", "longbig"]))
리뷰
-
각 문자열을 set 자료형으로 변경 후 & 연산을 통해 교집합을 구함으로서 공통 문자를 뽑아냈다.
-
각 문자열을 Counter로 변환해둔 리스트에서 각 공통문자가 가장 적게 나온 갯수를 찾아 저장한다.
-
공통문자들을 그 갯수만큼 중복하여 만든 리스트를 문자열로 바꾸고, 그것을 다시 리스트로 만든다.
- 부연 설명이 좀 필요한데, 만약 s가 2개, a가 1개, e가 1개 나왔다면 첫번째 리스트에서는 [“ss”,”a”,”e”]로 나오기 때문에 이것을 문자열로 만들었다가 다시 리스트로 만들어 [”s”,”s”,”e”,”a”]처럼 만들기 위함이다.
풀이 2 (다른분 풀이)
from collections import Counter
def solution(s):
answer = ""
compareWord = Counter(s[0])
for word in s[1:]:
counterWord = Counter(word)
compareWord = compareWord & counterWord
return list(compareWord.elements())
return answer
print(solution(["longlong", "longtong", "longbig"]))
리뷰
-
Counter 역시 set처럼 교집합 연산이 가능했다는 사실을 처음 알았다.
- 내가 만든 풀이를 한방에 삽질로 만드는 힘이 있었다.
-
Counter를 교집합으로 만들었으니, 당연히 갯수와 key값이 보존된다.
-
Counter.elements()를 리스트로 만들어 리턴.
- Counter.elements() : 카운터의 key값을 그 key의 value만큼 출력한다.