Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- embed&sign
- 인프런
- Cpp
- where Self
- git status
- 깃헙
- 백준
- Swift
- 알고리즘
- 깃허브 가이드
- 2차원배열
- Algorithm
- unreal dynamic framework
- 깃허브
- 깃허브 사용법
- Problem Solving
- Unreal iOS Framework
- Git
- new int
- PS
- protocol 기본구현
- ios framework
- github
- IOS
- 동적할당
- 리눅스 명령어
- Unreal iOS
- Unreal static Framework
- 깃 명령어
- C++
Archives
- Today
- Total
Get Up & Code, MacKin Talk
[백준]18830_좌표압축 본문
1. 문제 분석
Xi의 값이 Xj보다 큰 좌표의 개수를 찾아야 한다.(좌표 압축)
Xi를 좌표 압축한 결과 = Xi'
입력: X1, X2, ..., XN
출력: X1', X2', ..., XN'
2. 풀이 계획
입력 제한
1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9
N^2으로 검증하는 순간 시간 초과는 분명.
3. 계획 검증
전체 반복문 n
개별 반복문 p
각 명령어 실행 시간 1
O(np)
4. 소스 코드
import Foundation
var set = Set<Int>()
var dic = [Int: Int]()
_ = Int(readLine()!)!
var input = readLine()!.split(separator: " ").map { Int(String($0))! } // O(N) * O(1)
for value in input {
set.insert(value)
}
input.forEach { set.insert($0) }
var sorted = Array(set).sorted(by: <)
for (idx, value) in sorted.enumerated() {
dic.updateValue(idx, forKey: value)
}
for value in input {
print(dic[value]!, terminator: " ")
}
5. 돌아보기
하단 코드에서 1번으로 할 경우엔 시간 초과가 나지 않았지만, 2번으로 실행할 경우에는 시간 초과가 발생했다.
var input = readLine()!.split(separator: " ").map { Int(String($0))! } // O(N) * O(1)
성공!
1) String.Substring -> String -> Int
1) .map { Int(String($0))! }
시간 초과!
2) String.Substring -> Int
2) .map { Int($0)! }
아직 이유를 찾지는 못했지만, SubString -> Int 보단, SubString -> String -> Int의 변환 과정이 시간적으로 빠르게 구현되어 있다는 것을 확인한 문항.
이유에 대해 분석해야겠다.
'IOS > 알고리즘 문제 풀이' 카테고리의 다른 글
[백준]1966_프린터큐 (0) | 2021.10.11 |
---|---|
[백준]11047_동전0 (0) | 2021.10.06 |
[백준]5430_AC (0) | 2021.10.01 |
알고리즘 문제 풀이 53번 : K진수 출력(stack) (0) | 2021.01.15 |
알고리즘 문제 풀이 51번 : 영지(territory)선택:(large) (0) | 2021.01.14 |