백준 1181번 단어 정렬 - SWIFT

문제

---

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

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

 

입력

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

 

출력

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

 

문제 링크

1181번: 단어 정렬

 

풀이

---

Swift의 `sort(by: )` 함수를 사용하면 한 번에 해결된다.

자료를 `(Int, String)` 튜플 배열에 저장하는데, 첫번째 값은 문자열의 길이를 저장하고 두번째 값은 문자열을 저장한다.

그리고 `sort(by: <)` 메소드를 사용해주면 첫번째 값이 첫번째 기준, 두번째 값이 두번째 기준이 되어 정렬이 된다.

그러면 문제에서 원하는 대로 길이가 짧은 것 부터 정렬되고, 그 다음에 같은 길이는 사전순으로 정렬해준다.

처음에는 시간초과로 틀렸었는데, 같은 원소를 넣지 않는다는 조건을 잘못 구현해서 틀렸었다.

처음에는 `contains()`로 튜플 배열에 곂치는 원소가 있나 검사했는데, 20000개가 들어올 경우 contains()의 시간복잡도가 O(n)이므로 등차수열의 합 공식으로 간단하게 계산해보면 20000 * 20001 / 2 = 200010000 번 만큼 연산하게 된다.

1억당 대략 1초니까 2초 정도가 걸려서 시간초과가 발생한다.

그래서 데이터를 넣을 때 검사하는게 아니라 출력할 때 검사하기로 했다.

만약 같은 데이터가 여러 개 들어왔다고 하면, 정렬하는 과정에서 그 데이터들이 뭉칠것이다.▼

 

 

그러면 출력하기 전에 출력할 문자열을 이전에 출력했던 값과 비교해서 같으면 넘기고, 다르면 출력하면 된다.

 

 

Swift 코드

---

let N = Int(readLine()!)!
var arr = [(Int, String)]()
var tmp = ""
for _ in 0..<N {
    let str = readLine()!
    arr.append((str.count, str))
}
arr.sort(by: <)
for (x, y) in arr {
    if tmp == y { continue }
    tmp = y
    print(y)
}