99클럽 코테 스터디 13일차 TIL [04/16]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰░                     ] 13/29일 (45%)

본 글에서 다룬 문제 : 백준 1181번 : 단어 정렬

문제 푸는 데 걸린 시간 : 코드 2개 작성하고 글 작성하는 것 포함 34분

내 풀이 : 중복제거(set) + 정렬(sorted)

 

 

 

[오늘의 문제]

 

 

 

[문제 해석]

까다로운 조건이 있지는 않아서 무난한 문제다.

알파벳 소문자로 이루어진 N개의 단어가 입력되는데

그 단어들을 길이가 짧은 것부터, 길이가 같으면 사전순으로 정렬해서 출력하면 된다.

물론 중복된 단어는 하나만 남겨야 한다.

 

문제를 읽자마자 정렬은 sorted를 사용하고, 중복은 set을 사용해서 처리하면 되겠다고 생각했다.

 

 

 

[구현]

▶ 구현할 코드 흐름

1. N개의 단어를 입력받는다.
2. 입력과 동시에 중복 제거
3. 단어들 사전 순 정렬
4. 단어들 길이 기준 정렬
   • 길이가 같으면 기존 정렬 유지
5. 문제 조건에 맞게 출력

 

 

 

[코드]

코드는 2개를 작성해서 제출했다.

차이점은 import sys 사용 유무

# 코드 1번
words = set(input() for _ in range(int(input())))
words = sorted(words)
words = sorted(words, key = lambda x : len(x))
for i in words: print(i)

코드 1번은 최대한 간소하게 코드를 작성하려 했고, 그러다 보니 import sys를 사용하지 않았다.

우선 lambda: 는 이름 없는 함수를 만들 때 사용한다.

한 줄짜리 계산식을 함수처럼 쓰고 싶을 때 사용한다.

기본 사용법은 lambda 매개변수: 표현식

 

set은 리스트/문자열 등에서 중복을 제거하고 고유한 값만 저장할 때 사용한다.

사용은 set(리스트) 이런 식으로 하면 된다.

 

sorted()는 정렬 함수인데, 리스트나 문자열을 정렬한 새로운 리스트를 반환한다.

기본 사용법은 sorted(iterable객체, key=정렬기준함수, reverse=False)

(tmi. iterable = for문으로 하나씩 꺼낼 수 있는 반복 가능한 자료형. 예시로 문자열, 리스트, 딕셔너리 등)

key는 어떤 기준으로 정렬할지 설정하는데 나는 길이 기준으로 정렬할 거라 위 코드처럼 작성했다.

reverse=True로 적으면 내림차순 정렬이 된다. 생략하면 기본값인 False가 될 거다.

 

# 코드 2번
import sys
input = sys.stdin.readline
N = int(input())
words = set()
for _ in range(N):
    word = input().strip()
    words.add(word)
a_list = sorted(words, key = lambda x : (len(x), x))
for i in a_list : print(i)

코드 2번은 평소 하던 대로 import sys를 통해 빠른 입력처리를 하려 했다. (백준 문제이니까)

코드 흐름은 위 코드와 다를 바 없고 차이점은 위 코드에 비해 실행 시간이 매우 짧다는 것

소요 시간은 아래 제출 결과를 보면 된다.

 

 

 

[제출 결과]

코드 1번 제출 결과 : 걸린 시간 544ms

 

코드 2번 제출 결과 : 걸린 시간 80ms

 

 

 

[시간복잡도]

 

• int(input()) → O(1)
• set(input() for _ in range(N))
  • 입력 N번 → O(N)
  • set()에 추가할 때마다 평균 O(1) → 전체 O(N)
• sorted(words)
  • 사전순 정렬 → O(M log M), M = 고유 단어 수 (≤ N)
• sorted(..., key=lambda x: len(x))
  • 길이 기준 정렬 → O(M log M)
• 출력 → O(M)

 

총 시간복잡도 : O(N + M log M) (M ≤ N)

 

코드 1번과 2번은 입력속도는 훨씬 빠르지만, 총 시간복잡도는 동일하다.

 

 

[다른 접근 방법]

생각나는 건 dict 정도?

그런데 나는 set과 sorted 조합이 편해서 dict로 풀진 않았다.

다른 사람들의 코드를 백준에서 봤는데 나와 비슷한 방식으로 작성한 케이스가 많은 것을 보니

저 조합이 효율적인 듯하다.

 

 

 

[회고]

비슷한 해결법을 요구하는 문제들을 많이 풀다 보니

어떻게 풀어야 할지 고민하는 시간도 짧아지고 코드로 구현하는 시간 또한 짧아지고 있다.

코테 스터디에서 배운 내용 + 비슷한 카테고리 문제 혼자 풀기 = 풀이 방법 잘 기억남

역시 초보일 때는 어려운 문제보다는 많은 문제로 머리에 각인시키는 게 효율이 좋은 것 같다.

(나처럼 머리가 좋지 않다면 ㅎㅎ;)