티스토리 뷰
반응형
문제 링크
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
문제 풀이
숫자가 존재하는지 확인하기 위한 많은 방법이 있지만 나는 이분탐색을 사용할 것이다.
이분 탐색을 위해선 탐색할 배열을 정렬해야 한다.
첫 번째 배열을 정렬하고 두번째배열에서 숫자를 하나씩 꺼내 첫번째 배열에 있는지 확인하면 문제가 해결된다.
소스코드
import Foundation
let N = Int(readLine()!)
var firstArray: Array<Int> = [Int]()
firstArray = readLine()!.split(separator: " ").map(){Int(String($0))!}
firstArray.sort()
let M = Int(readLine()!)
var secondArray: Array<Int> = [Int]()
secondArray = readLine()!.split(separator: " ").map(){Int(String($0))!}
var result = [Int]()
for i in 0..<secondArray.count {
result.append(binarySearch(firstArray,secondArray[i]))
}
for i in 0..<result.count{
print(result[i])
}
func binarySearch(_ firstArray: [Int], _ temp: Int) -> Int{
if temp < firstArray[0] {
return 0
} else if temp > firstArray[firstArray.count - 1]{
return 0
} else {
var start: Int = 0
var end: Int = firstArray.count - 1
var mid: Int = (end + start) / 2
while (end-start >= 0) {
if firstArray[mid] == temp {
return 1
} else if (firstArray[mid] < temp){
start = mid + 1
} else if (firstArray[mid] > temp){
end = mid - 1
}
mid = (start + end) / 2
}
}
return 0
}
반응형
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준] 2630번 색종이 만들기 [Swift] (0) | 2020.07.31 |
---|---|
[백준] 1931번 회의실배정 with Swift (1) | 2020.07.29 |
[백준] 10816번 숫자 카드 2 [Swift] (0) | 2020.07.29 |
[백준] 1260번 DFS와 BFS [Swift] (0) | 2020.07.28 |
[백준] 10828번 스택 [Swift] (0) | 2020.07.21 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 문법
- 백준
- 코딩테스트
- 코테
- Xcode
- IOS
- 앱개발
- 스위프트
- Publisher
- Swift
- design
- OS
- mac
- operating
- DP
- OSTEP
- 아이폰
- System
- 알고리즘
- BFS
- 동시성
- pattern
- 프로그래밍
- dfs
- 테이블뷰
- 자료구조
- Apple
- Combine
- document
- operator
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함