[백준 2204번] 도비의 난독증 테스트 - python

https://www.acmicpc.net/problem/2204

📌 문제 탐색하기

목표

• 대소문자를 구분하지 않고 사전순으로 가장 앞서는 단어를 출력하자.

입력값

• 매 테스트케이스마다 단어의 개수를 뜻하는 정수 n이 주어진다. (2 ≤ n ≤ 1000)
• 다음 각 n줄은 길이가 최대 20인 단어가 주어진다.
• ex)
• 3 Cat fat bAt 4 call ball All Hall 0

출력값

• 각 줄에 각 테이스케이스에서 사전순으로 가장 처음 등장하는 단어를 출력한다.
• ex)
• bAt All

📌 코드 설계하기

해결 아이디어

• 이번 문제는 sort를 사용하면 되는 문제이다.
• 입력을 받고 모든 단어를 lower로 환산해서 사전 순으로 sort하게끔 한 뒤 가장 앞에 있는 단어를 출력한다.
• 다만, 특이한 점은 0이 입력되기 전까지 지속적으로 n을 입력받아 새로운 테스트케이스를 생성하는 점이다.
• while문을 통해서 n!=0 일 때만 테스트케이스를 입력받도록 설정하자.

📌 정답 코드

import sys

n = int(sys.stdin.readline())
while(n != 0):
    arr = []
    for i in range (n):
        arr.append(sys.stdin.readline().strip())
    arr.sort(key = lambda x: x.lower())
    print(arr[0])
    n = int(sys.stdin.readline().strip())

시간 복잡도 구해보기

• for문
  • 총 n번 반복한다. → O(N)
• 정렬 후 출력
  • 입력을 다 받은 후 한 번에 정렬 → O(n log n)

최종 시간 복잡도: O(n log n)