백준 2750번 Swift 알고리즘 연습 - 수 정렬하기_정렬

브론즈2 문제인만큼 시간 복잡도를 따지지 않아도 되는 문제였다. 그래서 Swift에서 제공하는 Sort 기능을 써서 해결할 수 있는 문제였지만, 이 문제를 Sort를 사용하지 않고 풀어보기로 스터디에서 이야기가 나왔다. 확실히 정렬할 일이 있을땐 항상 Sort를 사용하여 문제를 해결하곤 했기에..! 한 번 고민해서 풀어봤다.

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. Stack의 관점에서 한 번 생각해봤다.
2. 먼저 Stack1이 비어있으면 원소를 채워준다.
3. 그 다음으로 들어올 값과 Stack1의 값을 비교해준다.
4. 다음 값이 Last값 보다 크다면 Stack1에 append해서 순서를 정해준다.
5. 만약 다음 값이 Last값보다 작다면 Last값을 remove하고 Stack2에 넣어준다.
6. 그 후 다음 Last값과 또 비교를 해서 작다면 Last를 remove... 반복한다.
7. 이렇게 자신보다 큰 값을 전부 Stack2로 이동시키고 append하여 Stack1에 새로운 값을 위치시킨다.
8. 그 후 Stack2에 있는 값들을 reverse해서 다시 append해준다.

 

 

* 2750번

let n = Int(readLine()!)!
var stack1: [Int] = []
var stack2: [Int] = []

for _ in 0..<n {
    let value = Int(readLine()!)!
    
    if stack1.isEmpty {
        stack1.append(value)
    } else {
        for _ in 0..<stack1.count {
            if stack1.last! < value {
                stack1.append(value)
                break
            } else {
                stack2.append(stack1.last!)
                stack1.removeLast()
                if stack1.isEmpty {
                    stack1.append(value)
                }
            }
        }
        stack1 = stack1 + stack2.reversed()
        stack2.removeAll()
    }
}

for i in stack1 {
    print(i)
}

 

 

정리(Today I Learned)

1. 결론적으로는 맞긴했는데 사실 이게 시간복잡성이 좋아 보이지는 않는다... 물론 Sort 메서드 자체도 대입 값이 커지면 시간 초과가 지체 없이 일어나는 구조라서 최대한 효율적으로 만들 수 있는 방법이라는게 한계가 있어 보이기도 한다. 추후 스터디를 진행하며 더 좋은 방법을 찾는다면 내용을 조금 더 추가해야겠다!