[1920/Swift] 수 찾기

*** 언어는 Swift! ***

 

드디어 3회차 스터디가 시작됐다. 이번 문제들은 조금 어려운 문제들밖에 없어서 조금 애먹었지만 그래도 이번에는 다른 사람의 블로그를 참고하면서 푸는 방법을 배웠다.

물론 그 사람들의 코드를 그대로 베껴오는 것은 안되지만 그래도 참고 정도로 사용하는 방법을 배워서 좋았던 회차였던 것 같다!🥰

이번에 풀어볼 문제는 1920번 수 찾기 라는 문제였다.

이번 문제도 문제를 이해하는데 조금 시간이 걸렸다. 진짜 문제 이해하는게 너무 어려워서 조금 슬펐다🥲

그래도 포기하지 말고 다른 사람의 블로그를 보면서 조금씩 이해해보자! 가보자고!

 

자 먼저 항상 했던 문제 쪼개기를 해보자.

1. 첫째 줄에는 N이 주어지고, 다음 줄에는 N개의 정수 A[N]이 주어진다.

2. 다음 줄에는 M이 주어지고, 그 다음 줄에는 M개의 수들이 주어진다.

3. M의 값이 A에 있는지 찾는다.

 

이렇게만 봤을 땐 무슨 내용인지 모르겠어서 다른 사람의 블로그를 찾아보았다. 그리고 난 이 문제가 이분탐색에 관련된 문제라는 것을 알 수 있었다.

 

그렇다면 이분 탐색이란 무엇일까?

이분 탐색은 말 그대로 2로 나눠서 탐색하는 것이다. 예를 들어 [1, 2, 3, 4, 5] 의 배열이 있다고 하자 그런데 우리는 여기서 5를 찾는다고 할 때 간단하게 찾는다면 처음부터 하나 하나 비교해가며 5를 찾을 것이다.

그러나 이 방법은 5를 찾기까지 많은 시간이 걸릴 수 밖에 없다. 찾는 숫자가 2라면 2번만 돌면 되겠지만 만약 배열의 갯수가 100,000개가 넘고 그 중에서 99,999번째를 찾으라면? 굉장히 많은 시간이 걸릴 것이다.

 

이분 탐색은 처음부터 하게 되는 탐색을 가운데부터 하는 것이다. 말 그대로 배열의 갯수에서 딱 반을 쪼개 그 반 부터 탐색하는 것이다.

찾으려는 숫자가 배열 갯수 반에 들어있는 숫자보다 크다면 그 이후부터 찾으면 될 것이고, 작으면 그 전부터 찾으면 될 것이다.

 

자 그럼 이제 어떻게 해야할지 알았으니 본격적으로 코딩을 시작해보자😎

 

1. 첫째 줄에는 N이 주어지고, 다음 줄에는 N개의 정수 A[N]이 주어진다.

마찬가지로 N을 입력받고 N개의 정수를 입력받자.

 let n = Int(readLine()!)!
    
/// 다음 줄에는 N개의 정수 A[N] 이 주어진다.
var nArray: [String] = []
let nNumber = readLine()!
nArray = nNumber.components(separatedBy: " ")

그 전에 탐색을 하기 위해서는 정렬이 필요하다. 왜냐하면 찾으려는 숫자보다 작거나, 크거나 의 기준으로 탐색을 하기 때문이다.

/// 탐색을 위해 정렬한다.
nArray = nArray.sorted(by: <)

 

2. 다음 줄에는 M이 주어지고, 그 다음 줄에는 M개의 수들이 주어진다.

/// 다음 줄에는 M이 주어진다.
let m = Int(readLine()!)!

/// 다음 줄에는 M개의 수들이 주어진다.
var mArray: [String] = []
let mNumber = readLine()!
mArray = mNumber.components(separatedBy: " ")

 

3. M의 값이 A에 있는지 찾는다.

이제 여기서 이분 탐색을 시작한다.

먼저 이분 탐색을 위해 for 문을 이용해 M의 갯수만큼 돈다.

그리고 종료되는 기준을 구하기 위해 배열의 첫번째 인덱스와 마지막 인덱스를 변수로 따로 빼놓는다.

/// M의 값이 A 값에 있는지 찾는다
for i in 0..<m {
    /// 이분 탐색을 위해 첫번째 index와 마지막 index를 구해놓는다.
    var firstIndex = 0
    var lastIndex = nArray.count - 1

그 다음에는 while문을 이용해 lastIndex가 firstIndex보다 클 때만 반복하도록 만들어놓는다.

lastIndex가 firstIndex 보다 작다는 것은 모든 index를 다 돌았다는 뜻이기 때문이다.

 while(firstIndex <= lastIndex) {

자 이제 가운데 값을 구한 후 하나씩 조건문을 실행한다.

let mid = (firstIndex + lastIndex) / 2

먼저 M값이 mid 값 보다 작으면 mid 이전의 값들만 탐색하면 되기 때문에 lastIndex를 mid 에서 하나씩 줄인다.

if mArray[i] < nArray[mid] {
	lastIndex = mid - 1
}

만약 M 값이 mid 보다 크다면 mid 이후의 값들만 탐색하면 되기 때문에 firstIndex를 mid 보다 하나씩 늘린다.

else if mArray[i] > nArray[mid] {
    firstIndex = mid + 1
}

위 모두 해당하지 않고 만약 M의 값이 mid 의 값과 같다면 찾은 것이기 때문에 1을 출력하고 탐색을 종료한다.

else if mArray[i] == nArray[mid] {
    print("1")
    break
}

만약 while을 다 돌았는데, firstIndex 가 lastIndex 보다 큰데 break 가 되지 않았으면 배열 안에 포함되어있지 않기 때문에 0을 출력한다.

 if firstIndex > lastIndex {
    print("0")
}

이렇게 하면 4 1 5 2 3 을 입력했을 때 정렬을 한 후 (1 2 3 4 5)의 상태는 A라 하면, 1 3 7 9 5 를 입력하면

1은 A에 포함되어있기 때문에 1

3은 A에 포함되어있기 때문에 1

7은 A에 포함되어있지 않기 때문에 0

9는 A에 포함되어있지 않기 때문에 0

5는 A에 포함되어있기 때문에 1

을 출력하게 된다!

 

for문 안의 전체 코드는 아래와 같다.

for i in 0..<m {
    /// 이분 탐색을 위해 첫번째 index와 마지막 index를 구해놓는다.
    var firstIndex = 0
    var lastIndex = nArray.count - 1
    /// firstIndex가 lastIndex 보다 작을 때만 반복한다.
    while(firstIndex <= lastIndex) {
        /// 찾으려는 값을 찾기 위해 가운데 index부터 탐색을 시작한다.
        let mid = (firstIndex + lastIndex) / 2

        /// 만약 M 값이 mid 값보다 작으면 끝 범위를 중간보다 하나 작게 만든다
        if mArray[i] < nArray[mid] {
            lastIndex = mid - 1
        }
        /// 만약 M 값이 mid 값보다 크면 첫 범위를 중간보다 하나 크게 만든다
        else if mArray[i] > nArray[mid] {
            firstIndex = mid + 1
        }
        /// M의 값과 mid 값이 같다면 찾았기 때문에 1을 출력한다.
        else if mArray[i] == nArray[mid] {
            print("1")
            break
        }
    }

    /// firstIndex가 lastIndex보다 큰데 break가 되지 않았을 경우 못찾았기 때문에 0을 출력한다.
    if firstIndex > lastIndex {
        print("0")
    }
}

 

문제를 이해하는데 조금 어려워서 푸는데 어려웠지만 여러 블로그를 참고하여 풀 수 있었다! 

다른 사람의 코드를 아예 보지 않으려하는 것 보다는 푸는데 어려움이 있고, 잘 모르겠다면 다른 사람의 블로그를 참고사항으로 보고 풀어도 나쁘지 않을 것 같다는 생각이 들었다!

 

이렇게 오늘도 한 건 해결!😜