문제
풀지 못한 이유
- 이 문제는 풀긴 풀었는데, 내 풀이가 맘에 들지 않는다. 훨씬 더 좋은 방법을 찾을 수 있었는데도 1차원적인 사고로 풀었다. 확실히 정리해서 다시 다듬자.
풀이 1) 리스트
내가 푼 방법으로 테스트케이스는 모두 통과했지만, 5 이상 1,000,000 이하인 s를 다루기엔 다른 풀이에 비해서 비효율적이다.
def solution(s):
answer = []
# s가 문자열이니까 리스트로 변환하기
s = s.strip('{''}').split('},{')
s = list(map(lambda x: x.split(','), s))
s.sort(key=lambda x: len(x))
# 리스트 수 만큼 반복하기
# answer에 원소가 없는 경우만 넣기
for i in range(len(s)):
for n in s[i]:
if n not in answer:
answer.append(n)
return list(map(int, answer))우선 s가 문자열이므로 리스트로 변환한다. 이때 strip으로 앞뒤에 있는 '{{' 와 '}}'를 없애고, split으로 '},{' 을 없앤다. 그리고 각 문자열을 ',' 로 나누면 원래 묶음대로 리스트를 만들 수 있다.
s가 "{{1,2,3},{2,1},{1,2,4,3},{2}}" 라고 가정하면
s.strip('{''}')
# "1,2,3},{2,1},{1,2,4,3},{2"
s.strip('{''}').split('},{')
# ['1,2,3', '2,1', '1,2,4,3', '2']
# 위의 값을 s에 넣고 다음을 수행
list(map(lambda x: x.split(','), s))
#[['1', '2', '3'], ['2', '1'], ['1', '2', '4', '3'], ['2']]위에서 도출한 s 리스트를 각 원소의 길이를 기준으로 오름차순 정렬한다.
s.sort(key=lambda x: len(x))
# 결과
[['2'], ['2', '1'], ['1', '2', '3'], ['1', '2', '4', '3']]그럼 이제 리스트의 원소를 돌면서 answer 리스트에 값이 없으면 넣는다.
# 리스트 수 만큼 반복하기
# answer에 원소가 없는 경우만 넣기
for i in range(len(s)):
for n in s[i]:
if n not in answer:
answer.append(n)
# answer의 모습
['2', '1', '3', '4']마지막으로 answer의 원소는 문자이므로 정수형으로 바꿔준다.
list(map(int, answer))
# 결과
[2, 1, 3, 4]풀이 1) 회고
2중 반복문으로 리스트의 모든 원소를 탐색해야 하므로 시간 복잡도가 크다. 그리고 문자열 s를 리스트로 변환할 때 정수형으로 넣었으면 마지막에 return 할 때 각 원소를 int로 바꾸는 일은 없을 것이다.
풀이 2) 딕셔너리
질문하기에 있던 문제 푸는 팁을 보고 작성한 코드로, 해시로 숫자가 나온 횟수를 카운드하여 많이 나온 순으로 리스트를 만드는 것이다.
import re
def solution(s):
# s가 문자열이니까 리스트로 변환하기
s = re.sub('[{}]', '', s).split(',')
s = list(map(int, s))
dic = {n:0 for n in set(s)}
# # 각 문자가 나온 횟수 카운트하기
for n in s:
dic[n] += 1
dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
return [k for k, v in dic]re의 sub를 이용해서 s 문자열에서 '{'와 '}'를 한 번에 없앤다. 그러면 숫자와 ','만 남을 텐데 ','를 기준으로 나누고 값을 int형으로 변환한다.
s가 "{{1,2,3},{2,1},{1,2,4,3},{2}}" 라고 가정하면
re.sub('[{}]', '', s)
# 1,2,3,2,1,1,2,4,3,2
re.sub('[{}]', '', s).split(',')
# ['1', '2', '3', '2', '1', '1', '2', '4', '3', '2']
# 위의 값을 s에 넣고 다음을 수행
list(map(int, s))
# [1, 2, 3, 2, 1, 1, 2, 4, 3, 2]각 숫자가 key인 딕셔너리를 초기화하고, 숫자가 나오는 횟수를 카운팅 한다.
dic = {n:0 for n in set(s)}
# # 각 문자가 나온 횟수 카운트하기
for n in s:
dic[n] += 1
# dic의 모습
{1: 3, 2: 4, 3: 2, 4: 1}그다음 도출해낸 딕셔너리에서 value로 내림차순 정렬한 후 key 값을 빼내서 리스트로 만든다.
dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
return [k for k, v in dic]
# 결과
[2, 1, 3, 4]풀이 2) 회고
확실히 딕셔너리를 사용하니까 풀이 1보다 실행 속도가 빨라졌다. 왜 이 생각을 못 했나 싶다. 빨리 풀려고만 하지 말고 충분히 생각하고 풀자. 그리고 이번에 re의 sub에 대해서 처음 알았다. 한 문자만 바꿀 땐 replace를 사용하지만 여러 문자를 한 번에 바꿔야 할 땐 re의 sub를 이용하는 것을 잊지 말자.
풀이 3) Counter
다른 사람의 풀이에 있는 방법이다.
def solution(s):
# 각 숫자가 나온 횟수 세기
s = Counter(re.findall('\d+', s))
# 많이 나온 순서대로 내림차순 정렬하여 숫자만 뽑아서 리스트 만들기
return list(map(int, [k for k, v in sorted(s.items(), key=lambda x: x[1], reverse=True)]))
import re
from collections import Counterre 모듈의 findall을 이용해서 '하나 혹은 그 이상 연결된 숫자' 를 의미하는 정규 표현식 \d+ 을 적용하여 숫자들을 모두 찾아낸다. 그리고 collectioins 모듈의 Counter 클래스를 이용해서 숫자들이 나타난 횟수를 카운팅 한다.
Counter(re.findall('\d+', s))
# 결과
Counter({'2': 4, '1': 3, '3': 2, '4': 1})위에서 도출해낸 s를 카운트가 높은 순서대로 내림차순 정렬한 후, key 값인 숫자만 뽑아 int형 리스트로 만든다.
list(map(int, [k for k, v in sorted(s.items(), key=lambda x: x[1], reverse=True)]))
# 결과
[2, 1, 3, 4]풀이 3) 회고
정말 입이 떡 벌어진다. 숫자가 나온 횟수를 카운팅 하여 결과를 도출해 내는 방법은 풀이 2와 같지만, 과정이 다르다. 풀이 2에서 딕셔너리를 이용했다면 풀이 3에서는 Counter를 이용해 단 한 줄로 숫자들을 카운팅 했다. 값을 카운트해야 할 땐 Counter를 이용하면 코드가 간략해진다는 것을 잊지 말자.
