사용 언어: python 3.7.4

❓ Problem

문제 설명

백준 1181번: 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

🚩 Solution

1. 접근법

1. 중복되는 단어 제거하기
   • 파이썬의 딕셔너리 자료형은 중복되는 key값은 하나만 저장되므로 따로 제거 코드는 없다.
2. 알파벳순으로 정렬하기
3. 단어의 길이순으로 정렬하기

2. 코드

n = int(input())

dic = {} # 중복되는 단어는 하나만 저장됨
for i in range(n):
  key = input()
  dic[key] = len(key) # dic = {단어: 단어길이}

# 정렬
dic2 = dict(sorted(dic.items(), key= lambda x : x[0]))
list1 = sorted(dic2.items(), key= lambda x : x[1])

for item in list1:
  print(item[0])

3. 결과

채점 결과

correct

메모리	시간	코드길이
33724 KB	884 ms	291B

시간 복잡도 분석

O(NlogN)

📕 피드백

1. 검색한 내용

1. 딕셔너리 자료형 사용법

   1) 요소 추가하기: dic[key] = value

   2) 정렬: 내장함수 sorted() 사용

   key 기준: sorted(dic.items(), key= lambda x : x[0])

   value 기준: sorted(dic.items(), key= lambda x : x[1])

   ※ list 타입으로 반환된다. 딕셔너리로 바꾸고 싶으면 dict()으로 묶어주면 된다.

2. 실수

x

3. 발전 방향

백준에 제출된 100ms 코드 분석

import sys
N= int(sys.stdin.readline())
words= []
for _ in range(N):
    words.append(sys.stdin.readline().strip())
words=sorted(list(set(words)))
words.sort(key=len)
for word in words:
    print(word)

👉1) 입력받기 시간 줄이기: sys.stdin.readline() 사용

sys.stdin.readline()은 한 줄 단위로 입력받으며, 문자열 타입으로 저장되므로 개행문자(\n)가 같이 입력된다.

1. 한 개의 정수를 입력받을 때

import sys
n = int(sys.stdin.readline())

2. 정해진 개수의 정수를 한 줄에 입력받을 때

import sys
a,b,c = map(int,sys.stdin.readline().split())

3. 문자열 n줄을 입력받아 리스트에 저장할 때

import sys
n = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(n)]

strip()은 문자열 맨 앞과 맨 끝의 whitespace(띄어쓰기 ' ', 탭 '\t', 엔터 '\n')를 제거한다.

입력

3 
오늘은
기분이
좋다

출력

['오늘은', '기분이', '좋다']

4. 임의의 개수의 정수를 n줄 입력받아 2차원 리스트에 저장할 때

import sys
data = []
n = int(sys.stdin.readline())
for i in range(n):
    data.append(list(map(int,sys.stdin.readline().split())))

입력

3
0 1 2 3
4 5
6 7

출력

[[0, 1, 2, 3], [4, 5], [6, 7]]

출처: https://velog.io/@yeseolee/Python-파이썬-입력-정리sys.stdin.readline

👉2) 리스트에서 중복된 값을 제거하는 2가지 방법

1. set()

list1 = ['A', 'B', 'C', 'D', 'B', 'D', 'E']
list1 = list(set(lsit1)) 

출력

['A', 'D', 'E', 'B', 'C']

집합 자료형은 중복을 허용하지 않고, 순서가 없다.

※ set의 방식으로 중복을 제거할 경우, 순서가 뒤죽박죽이 된다는 단점이 있다.

만약 순서를 지켜야 하는 경우, 반복문을 사용한다.

2. for문

my_list = ['A', 'B', 'C', 'D', 'B', 'D', 'E']
new_list = []
for v in my_list:
    if v not in new_list:
        new_list.append(v)

출력

['A', 'B', 'C', 'D', 'E']

출처: https://velog.io/@daybreak/Python에서-리스트-중복제거

👉3) _(언더바) 사용

1. 인터프리터에서 마지막 값을 저장하고 싶을 때
2. 값을 무시하고 싶을 때
3. 변수나 함수 명에 특별한 의미 부여하고 싶을 때
4. 숫자 리터럴 값의 자릿수 구분을 위한 구분자로 사용할 때

(2번 예시)

for _ in range(5):
	print('hi')

변수 _ 가 0, 1, 2, 3, 4 값을 가지고 반복을 수행한다.

실제 사용되지는 않기 때문에  " _ " 를 사용한다.

👉4) list.sort() 와 sorted() 차이점

1. list.sort()

• 리스트만 적용됨(리스트의 내장 함수니까)
• 원본 리스트를 정렬하되, 반환 값은 None이다.

list1 = [1, 3, 2]
print(list1.sort())
# None
print(list1)
# [1, 2, 3]

새로운 복사본을 만들지 않기 때문에 sorted()보다 빠르다.

거꾸로 정렬: list.sort(reverse=True)

key 옵션 정렬: list.sort(key = len)

2. sorted()

• 모든 이터러블한 자료형(list, tuple, dict, 문자열 등)에 적용 가능함(파이썬 내장 함수)
• 원본 리스트 변형 없이, 정렬한 새로운 리스트를 반환함(※ 항상 리스트 타입을 반환한다.)

list2 = [1, 3, 2]
print(sorted(list2))
# [1, 2, 3]
print(list2)
# [1, 3, 2]

출처: https://inma.tistory.com/137

4. 느낀점

어떤 도구가 있는지 잘 알아두자.