https://www.acmicpc.net/problem/1195
1195번: 킥다운
첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는
www.acmicpc.net
완전 탐색 문제다. 두 배열 비교를 어떤 식으로 수행하는지 고민해야 하는 문제.
풀이
두 배열 중 짧은 배열을 덱을 사용하여 원소를 하나씩 담아낸 뒤 긴 배열과 비교, 짧은 배열의 원소를 모두 담아내었다면 긴 배열의 길이만큼 1을 추가하여 비교하였다. 값 갱신은 Bool 변수를 사용하여 두 원소가 모두 2일 경우에는 갱신을 하지 않는 방법으로 탐색하였다.
스위프트에는 기본적으로 제공되는 덱 구조가 없어서 배열을 사용하여 insert(_ newElement:Int , at:Int)를 사용했다. 시간 초과가 걱정되었지만 각 입력 배열의 길이가 최대 100으로 짧은 편에 속했고, 시간도 넉넉했기에 통과할 수 있었다. 이후 더 빠른 동작이 가능한지 궁금하여 배열을 합치는 방식으로 바꾸어 보았지만 큰 차이는 없었다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| var a = readLine()!.map{Int(String($0))!} | |
| var b = readLine()!.map{Int(String($0))!} | |
| var ans = a.count + b.count | |
| if a.count < b.count{ | |
| swap(&a, &b) | |
| } | |
| var temp = [Int]() | |
| while !b.isEmpty{ | |
| var flag = true | |
| temp = [b.removeLast()]+temp | |
| for i in 0..<temp.count{ | |
| if temp[i]==2 && a[i]==2{ | |
| flag = false | |
| break | |
| } | |
| } | |
| if flag{ | |
| ans = min(ans, b.count+a.count) | |
| } | |
| } | |
| var idx = 1 | |
| while idx < a.count{ | |
| temp = [1]+temp | |
| var flag = true | |
| for i in idx..<min(a.count,temp.count){ | |
| if temp[i]==2 && a[i]==2{ | |
| flag = false | |
| break | |
| } | |
| } | |
| if flag{ | |
| ans = min(ans, max(a.count, temp.count)) | |
| } | |
| idx += 1 | |
| } | |
| print(ans) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [1245] 농장 관리 (0) | 2022.11.04 |
|---|---|
| [1148] 단어 만들기 (0) | 2022.11.03 |
| [1915] 가장 큰 정사각형 (0) | 2022.11.01 |
| [1347] 미로 만들기 (0) | 2022.10.31 |
| [1388] 바닥 장식 (0) | 2022.10.31 |