[Algorithm] Swift 백준 14467번

 

https://www.acmicpc.net/problem/14467

14467번: 소가 길을 건너간 이유 1

 

문제접근

 

 

만약 관찰 횟수가 3번이고 입력이 3 1, 3 0, 6 0이라면 cowNumber배열을 만들어주어 소의 번호를 넣어주고 cowLeftRight배열을 만들어주어 길의 왼쪽과 오른쪽을 의미하는 0과 1을 넣어준다. 반복문을 사용하여 cowNunber배열에 들어있는 소의 번호가 같을 떼 소의 위치마저 달라졌다면( 0 -> 1 or 1 -> 0) crossCount를 1씩 증가시켜 준다! 

 

var crossCount = 0
var cowNumber:[Int] = []
var cowLeftRight: [Int] = []

let N = Int(readLine()!)!

for i in 0..<N {
    var cow = readLine()!.split(separator: " ").map{ Int($0)! }
    cowNumber.append(cow[i-i])
    cowLeftRight.append(cow[i+1-i])
}

for j in 0..<cowNumber.count {
    for k in j+1..<cowNumber.count {
        if cowNumber[j] == cowNumber[k] {
            if cowLeftRight[j] != cowLeftRight[k] {
                crossCount += 1
            }
        }
    }
}
print(crossCount)

 

하지만 예시를 입력해 보면 

 

내가 작성한 코드에서는 소가 건넌 횟수기 5번이 나왔다! 왜 5번이나 나왔지 잘 생각해 보니깐 (중복이라는 표현을 쓰는 것이 맞는지 모르겠지만) 중복돼서 계산이 된다는 것을 알 수 있었다. 

 

 

 

예시를 배열로 만들어보면 코드를 보면 반복문을 이중으로 돌려서 구하고 있는데 위와 같이 모든 자리에서 다 계산하다 보니 3번 소의 초기위치가 계속 변경되면서 소가 건넌 횟수가 계산이 되었다!! 이 부분을 해결하기 위해 배열에서 계산 후  제거하는 방법을 이용해 보고 또 다른 방법이 떠오르지 않아 블로그를 참고해 보았다! 위 코드풀이를 다른 방법을 찾아 해결하면 다시 글을 수정해 보겠다!!! 

 

정답풀이

 

let N = Int(readLine()!)!
var answer: Int = 0
var cows: [Int] = Array(repeating: -1, count: 11)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (num, location) = (input[0], input[1])
//    if cows[num] == -1 { // 첫 등장이면,
//        cows[num] = location
//    }
//    else {
//        if cows[num] != location { // 위치가 달라졌다면,
//            answer += 1
//            cows[num] = location
//        }
//    }
    
    if cows[num] != -1 && cows[num] != location { // 첫 등장이 아니고 + 위치가 달라졌으면,
        answer += 1
    }
    cows[num] = location
    
}
print(answer)

 

 

cows라는 배열에 -1을 11번 넣어줬다.

소의 번호는 1부터 10까지 10개인데 왜??  11번을 넣어주는지 알아보자!!  

 

우선 관찰 횟수만큼 반복을 한다. 소의 번호와 위치를 입력받는다. map {Int(String($0))!}에서 왜?? 뜬금없이 String으로 변환하는지 궁금하다면 👇🏻

 

https://h2kangrok.tistory.com/9

[Swift] map{ Int($0)! } vs map{ Int(String($0))! }

 

 

 

 

만약 3 1이 입력이 된다면 cows [num]의 num에 3을 넣어주고  (cows [3]은 처음에 -1이므로). 이는 거짓이므로 아무 일도 일어나지 않으며 cows [3]은 1로 업데이트됩니다.

다음으로 3 0이 입력된다면 cows [3]!= -1 && cows [3]!= 0인지 확인! (cows [3]는 1로 업데이트 됐기 때문에) 두 조건에 참이기 때문에 answer이 1씩 증가한다. 

 

여기서!! 왜 11번을 넣어주었냐면!! 소의 번호가 10번이라면 cows [10]이 되는데 이것은 cows 배열의 10번째를 의미한다. 

배열은 0번부터 개수를 세기 때문에 0 1 2 3 4 5 6 7 8 9 10 즉 배열. count가 11개가 되어야지 10번째를 가져올 수 있다!! 

 

이런 식으로 반복한다면 처음 들어간 소는 소의 위치로 저장이 되고, 다시 들어간 소는 위치가 변경이 되었는지 확인 후 변경이 되었으면 건넌 횟수(answer)를 증가시켜 준다. 

 

 

참고자료 

 

https://developer-p.tistory.com/210