DP공부를 위해 백준 1695번을 풀다가, 팰린드롬 관련된 문제를 한번정도 풀어보긴 했지만 기억도 안나고 아예 접근법이 달랐다.
그래서 이번 기회에 백준 팰린드롬 관련 문제모음 중,
실버와 골드 문제만이라도 우선 독파해놓으면 좋을 것 같아서 (DP를 공부하다가) 풀게 됐다.
https://www.acmicpc.net/workbook/view/1128
문제집: 팰린드롬 (cocomo1316)
www.acmicpc.net
문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.06.07 업데이트
22.06.08 업데이트
22.06.09 업데이트
22.06.11 업데이트
22.06.12 업데이트
22.06.16 업데이트
22.06.20 업데이트
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
백준 Swift 10988번
문제 유형 : 팰린드롬(재귀, 반복문)
골드 문제 위주로 풀다가, 갑자기 브론즈 문제라서 뭔가 쉽다. ㅎㅎ
flag를 두고, 인덱스를 처음부터 ~ 길이의 절반까지만 돌면서 같은지 확인하면 된다.
난이도 : 브론즈1
풀이
// MARK: - 10988번
let arr = readLine()!.map{String($0)}
let length: Int = arr.count
var check: Bool = true
for i in 0..<length/2 { // 절반만 비교해도 됨.
if arr[i] == arr[length - 1 - i] {
continue
}
else {
check = false
break
}
}
if check {
print(1)
}
else {
print(0)
}
백준 Swift 10174번
문제 유형 : 팰린드롬
풀이 자체는 10988번과 같다. .lowercased()정도 차이가 있다.
난이도 : 브론즈2
풀이
// MARK: - 10174번
let n = Int(readLine()!)!
for _ in 0..<n {
let input = readLine()!.map{String($0).lowercased()}
let length: Int = input.count
var flag: Bool = true
for i in 0..<length/2 {
if input[i] == input[length - 1 - i] {
continue
}
else {
flag = false
break
}
}
if flag {
print("Yes")
}
else {
print("No")
}
}백준 Swift 4096번
문제 유형 : 팰린드롬
실버5인데 구현이 생각보다 어려웠다.
포인트 1. 무한 입력 받으면서 0일 때 종료.
포인트 2. 숫자 앞에 0을 붙여줘야 함. (String(format: "%0?d", ?)를 활용해서 해결)
풀이는 맞는데 시간초과가 난다...! Swift로 맞은 사람이 없는 걸 보니까
처리속도가 상대적으로 느린 Swift는 추가시간을 줘야만 통과할 수 있을 것 같다.
(만약 Swift로 이 문제를 통과하시는 분이 계신다면 댓글, 링크등으로 제게 꼭 좀 알려주세요! 배우고 싶습니다.)
난이도 : 실버5
참고 자료 : https://khu98.tistory.com/200
풀이 - 시간초과
// MARK: - 4096번(팰린드롬) - 50%에서 시간초과
import Foundation
while let temp = readLine() {
if temp == "0" { // 0이면 종료.
break
}
let input = temp.map{String($0)}
if isPalindrome2(input) { // 처음부터 팰린드롬이면,
print(0) // 바로 0 출력.
}
else { // 팰린드롬이 아니면,
let num: Int = Int(input.joined(separator: ""))!
let length: Int = input.count // 숫자의 개수
var rangeEnd: String = "" // "9" * 길이 -> "999..."
for _ in 0..<length {
rangeEnd += "9"
}
let end: Int = Int(rangeEnd)! // 끝 수 구해놓음.
var count: Int = 0 // 주행 거리.
for n in num+1...end { // 주어진숫자의 다음 수 ~ 끝까지 돌면서,
count += 1 // 거리 1씩 추가.
let strN = String(format: "%0\(length)d", n)
let strNArray: [String] = strN.map{String($0)}.reversed()
if isPalindrome2(strNArray) { // 팰린드롬이라면,
print(count) // 최소 거리 출력.
break
}
}
}
}
//func isPalindrome(_ strArr: [String]) -> Bool {
// return strArr == strArr.reversed()
//}
func isPalindrome2(_ strArr: [String]) -> Bool {
let length: Int = strArr.count
var flag: Bool = true // 팰린드롬 체크.
for i in 0..<length/2 {
if strArr[i] != strArr[length - 1 - i] {
flag = false
break
}
}
return flag
}풀이 개선 - 시간초과
// MARK: - 4096번(팰린드롬) - 개선 : 50% 시간초과
import Foundation
while let temp = readLine() {
if temp == "0" { // 0이면 종료.
break
}
let input = temp.map{String($0)}
if isPalindrome2(input) { // 처음부터 팰린드롬이면,
print(0) // 바로 0 출력.
}
else { // 팰린드롬이 아니면,
let num: Int = Int(input.joined(separator: ""))!
let length: Int = input.count // 숫자의 개수
// var rangeEnd: String = "" // "9" * 길이 -> "999..."
// for _ in 0..<length {
// rangeEnd += "9"
// }
// let end: Int = Int(rangeEnd)! // 끝 수 구해놓음.
var count: Int = 0 // 주행 거리.
var startNum: Int = num + 1
while true {
count += 1
let strN: [String] = String(format: "%0\(length)d", startNum).map{String($0)}
if isPalindrome2(strN) { // 팰린드롬이라면,
print(count) // 최소 거리 출력.
break
}
startNum += 1
}
// for n in num+1...end { // 주어진숫자의 다음 수 ~ 끝까지 돌면서,
// count += 1 // 거리 1씩 추가.
// let strN: [String] = String(format: "%0\(length)d", n).map{String($0)}
//
// if isPalindrome2(strN) { // 팰린드롬이라면,
// print(count) // 최소 거리 출력.
// break
// }
// }
}
}
//func isPalindrome(_ strArr: [String]) -> Bool {
// return strArr == strArr.reversed()
//}
func isPalindrome2(_ strArr: [String]) -> Bool {
let length: Int = strArr.count
var flag: Bool = true // 팰린드롬 체크.
for i in 0..<length/2 {
if strArr[i] != strArr[length - 1 - i] {
flag = false
break
}
}
return flag
}백준 Swift 8892번
문제 유형 : 팰린드롬
팰린드롬인지 확인 후, 가능하다면 팰린드롬 문자열을 출력하면 되는 문제다.
팰린드롬인지 확인 유무 함수는 10174번 문제와 똑같이 구현했다. (10174번은 왜 안돼~~)
순열로 2개를 선택하는 것과 같다. 물론 미리 모든 순열을 다 구하고 비교하는 것이 아니라, (굳이 모든 경우를 미리 만들 필요가 없다.)
이중 for문을 통해, 하나의 tempArr를 만들고 팰린드롬인지 확인을 해가는 식으로 해야 그나마 시간을 단축시킬 수 있다.
난이도 : 실버5
풀이
// MARK: - 8892번(팰린드롬)
let T = Int(readLine()!)!
for _ in 0..<T {
let k = Int(readLine()!)!
var arr: [String] = []
for _ in 0..<k {
arr.append(readLine()!)
}
var hasPalindrome: Bool = false // 팰린드롬 존재 유무.
outLoop: for i in 0..<k {
for j in 0..<k {
if i != j { // 인덱스가 다를 때에만,
let temp: String = (arr[i] + arr[j])
let tempArr: [String] = temp.map{String($0)}
if isPalindrome(tempArr) {
hasPalindrome = true // 팰린드롬 존재.
print(temp)
break outLoop
}
}
}
}
if !hasPalindrome { // 만들 수 없으면,
print(0) // 0출력.
}
}
func isPalindrome(_ strArr: [String]) -> Bool {
let length: Int = strArr.count
var flag: Bool = true // 팰린드롬 체크.
for i in 0..<length/2 {
if strArr[i] != strArr[length - 1 - i] {
flag = false
break
}
}
return flag
}백준 Swift 8611번
문제 유형 : 팰린드롬
구현 자체는 어렵지 않게 했다. 근데 런타임 오류가 뜬다.
고민해보니, n의 범위가 10^1000로 매우 크다. 그래서 런타임 오류가 뜨는 것 같다.... UInt64도 벗어나는 범위.. 해결 못했다.
난이도 : 실버5
풀이 - 런타임오류
// MARK: - 8611번(런타임오류 - n범위 초과)
let n: UInt64 = UInt64(readLine()!)!
// let n: Int = Int(readLine()!)!
var hasPalindrome: Bool = false
for i in 2...10 {
let temp: String = String(n, radix: i)
let tempArr: [String] = temp.map{String($0)}
print(i, temp, tempArr)
if isPalindrome(tempArr) {
print(i, temp)
hasPalindrome = true
}
}
if !hasPalindrome { // 팰린드롬인게 없으면,
print("NIE")
}
func isPalindrome(_ strArr: [String]) -> Bool {
let length: Int = strArr.count
var flag: Bool = true // 팰린드롬 체크.
for i in 0..<length/2 {
if strArr[i] != strArr[length - 1 - i] { // 앞부분과 뒷부분이 다르다면,
flag = false
break
}
}
return flag
}백준 Swift 1254번
문제 유형 : 팰린드롬
처음엔 어떻게 풀까 고민을 했는데, 지난번에 풀었던 백준 1695번과 같은 문제라고 생각했다. 아래 종이 풀이처럼 LCS를 활용하면 된다고 생각했다.(종이풀이 상단 회색박스)
주어진 TC도 다 맞고 해서, 호기롭게 풀어서 제출했는데 4%에서인가 틀렸다. 뭐지!!!!!! 고민을 많이 했다. (고민의 흔적은 종이풀이 최하단 빨간박스에 있다.)
잘 생각해보니, LCS를 써서 나오는 결과가 더 짧은 팰린드롬이긴 하다.
근데 이 문제에서 그건 안된다. 왜냐???
1695번은 어디에든 삽입할 수 있었지만, 1254번은 주어진 문자열의 끝부분에만 이어 붙일 수 있기 때문이다.
해결방법
i가 0부터 length-1까지 돈다.
j가 i부터 length-1까지로 [String]을 만든 뒤, 팰린드롬인지 체크한다.
만약 팰린드롬이라면, 길이 length와 움직인 i만큼 더해준 게 답이다.
왜 이렇게 되는지 예시를 통해 알아보자. 주어진 S = "abaa"에서,
i가 0 : ["a", "b", "a", "a"] => abaa는 팰린드롬X
i가 1 : [_, "b", "a", "a"] => => baa는 팰린드롬X
i가 2 : [_, _, "a", "a"] => aa는 팰린드롬O
그렇다면, 팰린드롬인 aa를 기준으로 앞2개는 뒤에 붙여지게 될 것이다. 즉, abaaba가 되고 기존길이(4) + 앞2개 = 6이 된다.
난이도 : 실버2
참고 자료 : https://ilmiodiario.tistory.com/145
풀이
// MARK: - 1524번(팰린드롬)
let S = readLine()!.map{String($0)}
let length: Int = S.count
for i in 0..<length { // 맨 앞부터 돌면서,
var strArray: [String] = []
for j in i...length-1 { // i번째부터 끝까지의 [String]을 만든 뒤,
strArray.append(S[j])
}
if isPalindrome(strArray) { // 만약 팰린드롬이면, 기존의 길이(length) + 앞쪽에서 뒤로 이동한 만큼(인덱스 i)이 정답.
print(length + i)
break
}
}
func isPalindrome(_ strArr: [String]) -> Bool {
let length: Int = strArr.count
var flag: Bool = true
for i in 0..<length/2 {
if strArr[i] != strArr[length - 1 - i] { // 앞부분과 뒷부분이 다르다면,
flag = false
break
}
}
return flag
}// MARK: - 1524번(LCS - 최장공통 부분 수열) - 틀림.
let S = readLine()!.map{String($0)}
let length: Int = S.count
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: length + 1), count: length + 1)
for i in 1...length { // 뒤 부터 돈 것과,
for j in 1...length { // 앞 부터 돌면서,
if S[length - i] == S[j - 1] { // 같으면,
dp[i][j] = dp[i - 1][j - 1] + 1
}
else { // 다르면,
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
let answer = 2 * length - dp[length][length]
print(answer)백준 Swift 1334번
문제 유형 : 팰린드롬
정답률이 19%일 때부터 느낌이 쎄하긴 했다. 결국 시간초과의 늪에서 벗어나지 못했다... 왜 안돼~~
입력 부분 : N이 최대 50자리이기 때문에, Int로는 못받고, array로 입력받아서 해결했다.
case 1 - ex) 9999 -> 10000
N의 index0자리에 [0]을 미리 붙여놔서, 09999 -> 10000이 될 때 문제 없도록 했다.
인덱스 0부터 중간까지 돌면서 팰린드롬인지 확인한다.
case 2 - ex) 1234 -> 1235
N의 0번째 자리는 쓰이지 않는다.
인덱스 1부터 중간까지 돌면서 팰린드롬인지 확인한다.
난이도 : 실버1
풀이
// MARK: - 1334번(팰린드롬) - 시간초과
var N: [Int] = [0] + readLine()!.map{Int(String($0))!}
//var newN: [Int] = N
while true {
// newN값 1 증가.
N[N.count-1] += 1 // 가장 끝부분 1증가.
for i in stride(from: N.count-1, through: 1, by: -1) {
if N[i] >= 10 {
if i == 1 { // 가장 앞부분 자리수가 바껴야 한다면, ex) 09999 -> 10000
N[i] = 0
N[0] = 1
// N.insert(1, at: 0)
// break // 있어도 되고, 없어도 됨. 어차피 for문의 가장 마지막이라.
}
else { // 그 외 자리수가 바뀐는 거라면,
N[i] = 0
N[i - 1] += 1
}
}
}
if N[0] == 1 { // ex) 09999 -> 10000
if isPalindrome0(N) { // 팰린드롬이라면,
print(N.map{String($0)}.joined(separator: "")) // joined로 정답 출력.
break
}
}
else { // ex) 01234 -> 01235
if isPalindrome1(N) { // 팰린드롬이라면,
print(N[1...N.count-1].map{String($0)}.joined(separator: "")) // joined로 정답 출력.
break
}
}
}
func isPalindrome0(_ nArray: [Int]) -> Bool { // nArray의 맨 앞 자리가 유효할 때. ex) 09999 -> 10000
let length: Int = nArray.count
var flag: Bool = true
for i in 0..<length/2 { // 처음(0)부터 중간까지 돎.
if nArray[i] != nArray[length - 1 - i] {
flag = false
break
}
}
return flag
}
func isPalindrome1(_ nArray: [Int]) -> Bool { // nArray의 맨 앞 자리가 유효하지 않을 때. ex) 01234 -> 01235
let length: Int = nArray.count
var flag: Bool = true
for i in 1...length/2 { // 1부터 중간까지 돎.
if nArray[i] != nArray[length - i] {
flag = false
break
}
}
return flag
}백준 Swift 1747번
문제 유형 : 소수(에라토스테네스의 체) + 팰린드롬
에라토스테네스의 체에 대해 몰랐다. "소수 판별 시 √n까지만 판별하면 소수인지 아닌지 알 수 있다는 사실"을 알았다.
에라토스테네스의 체와 팰린드롬을 체크하는 함수 두개를 합쳐서 풀면 된다.
난이도 : 실버1
풀이
// MARK: - 1747번(에라토스테네스의 체 + 팰린드롬)
import Foundation
var N = Int(readLine()!)!
while true {
if isPrime(N) { // 소수인데,
if isPalindrome(String(N).map{String($0)}) { // 팰린드롬이기까지 하면,
print(N)
break
}
}
N += 1
}
func isPrime(_ num: Int) -> Bool { // 소수인지 확인하는 함수.
if num < 4 {
return num == 1 ? false : true // 1은 false, 2와 3은 true
}
let end: Int = Int(sqrt(Double(num))) // Int(√n)까지만.
for i in 2...end {
if num % i == 0 { // 약수가 있다면, 소수가 아님.
return false
}
}
return true
}
func isPalindrome(_ numArray: [String]) -> Bool { // 팰린드롬인지 확인하는 함수.
let length: Int = numArray.count
var flag: Bool = true
for i in 0..<length/2 {
if numArray[i] != numArray[length - 1 - i] {
flag = false
break
}
}
return flag
}에라토스테네스의 체
문제 유형 : 에라토스테네스의 체
소수 구하는 최적의 방식에 대해 공부했다. 임의의 수(n)의 약수는 대칭이라는 특징을 이용해, √n까지만 판별하면 소수인지 아닌지 알 수 있다.
참고 자료 : https://www.youtube.com/watch?v=5ypkoEgFdH8
소수 판별 - 임의의 수만 판별할 때
// MARK: - 소수 판별
import Foundation // sqrt를 위해.
func isPrime(_ num: Int) -> Bool {
if num < 4 {
return num == 1 ? false : true // 1은 false, 2와 3은 true
}
let end: Int = Int(sqrt(Double(num))) // Int(√n)까지만.
for i in 2...end {
if num % i == 0 { // 약수가 있다면, 소수가 아님.
return false
}
}
return true
}
//print(isPrime(1)) // false
//print(isPrime(2)) // true
//print(isPrime(3)) // true
//print(isPrime(4)) // false
//print(isPrime(5)) // true
//소수 관련 문제(백준 1978번) : https://www.acmicpc.net/problem/1978에라토스테네스의 체 - 대량의 수를 한꺼번에 판별할 때
// MARK: - 에라토스테네스의 체
let N = Int(readLine()!)!
var arr: [Int] = [-1] + Array(repeating: -1, count: N)
if N >= 2 { // N == 1 방지
for i in 2...N {
arr[i] = i
}
}
if N >= 2 { // N == 1 방지
for i in 2...N {
if arr[i] != -1 { // i위치의 값이 지워지지 않았다면,
for j in stride(from: 2*i, through: N, by: i) { // i의 배수들은 모두 지워줌.
arr[j] = -1
}
}
}
}
print(arr.filter{$0 != -1}) // 지워지지 않고 남은 것들만 출력.백준 Swift 10942번
문제 유형 : 팰린드롬
문제를 딱 보고 dp를 써야 될 거 같다고 생각이 들었다.
맨 처음엔 바텀업 방식이니까 밑에부터 올라가는 식으로 해야 된다고 생각해서 못풀다가, 힌트를 보고 풀었다.
힌트 : S...E가 팰린드롬이려면, S+1...E-1도 팰린드롬이어야 한다.
풀이 방법
dp배열을 만들고,
(1,1), (2,2), (3,3), ... (N,N)은 무조건 팰린드롬이다. 미리 세팅한다.
dp[S][E]를 알기 위해선, dp[S+1][E-1]을 이용하면 빠르게 알 수 있다. 근데 만약 (3,4)라면 공식을 이용시 (4,3)이라는 필요없는 부분을 검사하게 된다.
그래서 미리 (1,2), (2,3), (3,4), ... (N-1, N) 도 미리 세팅한다.
for i in 1...N {
dp[i][i] = true // 1자리수는 무조건 팰린드롬.
}
for i in 1..<N {
if arr[i] == arr[i + 1] { // dp공식을 위해 미리 체크해놓음.
dp[i][i + 1] = true
}
}
하단 종이 풀이에서, 빨간 동그라미부터 낮은 방향으로 가면 된다. 1행은 체크표시하지 않았다. (그냥)
즉, N-2행부터 1행까지, i+2열부터 N까지 확인하면 된다.
추가적으로, arr[S]와 arr[E]도 확인해야 진짜 팰린드롬인지 알 수 있다.
(dp[S+1][E-1] == true) && (arr[S] == arr[E]) 를 모두 만족하면 팰린드롬이다.
for i in stride(from: N-2, through: 1, by: -1) {
for j in i+2...N { // i와 i+1은 미리 세팅됨.
if (dp[i + 1][j - 1]) && (arr[i] == arr[j]) {
dp[i][j] = true
}
}
}
추가적으로, 풀이 자체는 맞는데, Swift에 할당된 시간이 부족해서 시간초과가 난다.
FileIO를 써서 해결하면 된다.
틀렸습니다가 뜬 이유는..... 가장 마지막 부분에 print(answer)를 안해줘서..... 이런 실수는 Naver~~가자!
난이도 : 골드4
참고 자료 : https://4z7l.github.io/2021/04/07/algorithms-boj-10942.html
풀이 - FileIO 사용
// MARK: - 10942번(dp + 팰린드롬)
import Foundation
// 라이노님의 FileIO
final class FileIO {
private var buffer:[UInt8]
private var index: Int
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
index = 0
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer.withUnsafeBufferPointer { $0[index] }
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var str = ""
var now = read()
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
while now != 10
&& now != 32 && now != 0 {
str += String(bytes: [now], encoding: .ascii)!
now = read()
}
return str
}
}
// 풀이
let file = FileIO()
//let N = Int(readLine()!)!
let N = file.readInt()
//var arr: [Int] = [-1] + readLine()!.split(separator: " ").map{Int(String($0))!}
var arr: [Int] = [-1]
for _ in 0..<N {
arr.append(file.readInt())
}
//let M = Int(readLine()!)!
let M = file.readInt()
//var question: [(start: Int, end: Int)] = []
//for _ in 0..<M {
// let input = readLine()!.split(separator: " ").map{Int(String($0))!}
// question.append((input[0], input[1]))
//}
var dp: [[Bool]] = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)
for i in 1...N {
dp[i][i] = true // 1자리수는 무조건 팰린드롬.
}
for i in 1..<N {
if arr[i] == arr[i + 1] { // dp공식을 위해 미리 체크해놓음.
dp[i][i + 1] = true
}
}
for i in stride(from: N-2, through: 1, by: -1) {
for j in i+2...N { // i와 i+1은 미리 세팅됨.
if (dp[i + 1][j - 1]) && (arr[i] == arr[j]) {
dp[i][j] = true
}
}
}
//for q in question {
// if dp[q.start][q.end] { // 팰린드롬인 경우,
// print(1)
// }
// else { // 팰린드롬이 아닐 경우,
// print(0)
// }
//}
var answer = ""
for _ in 0..<M {
let (S, E) = (file.readInt(), file.readInt())
answer += (dp[S][E] == true ? "1\n" : "0\n")
}
print(answer)풀이 : 시간초과(FileIO 미사용)
// MARK: - 10942번(dp + 팰린드롬) : 시간초과
let N = Int(readLine()!)!
var arr: [Int] = [-1] + readLine()!.split(separator: " ").map{Int(String($0))!}
let M = Int(readLine()!)!
var question: [(start: Int, end: Int)] = []
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
question.append((input[0], input[1]))
}
var dp: [[Bool]] = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)
for i in 1...N {
dp[i][i] = true // 1자리수는 무조건 팰린드롬.
}
for i in 1..<N {
if arr[i] == arr[i + 1] { // dp공식을 위해 미리 체크해놓음.
dp[i][i + 1] = true
}
}
for i in stride(from: N-2, through: 1, by: -1) {
for j in i+2...N { // i와 i+1은 미리 세팅됨.
if (dp[i + 1][j - 1]) && (arr[i] == arr[j]) {
dp[i][j] = true
}
}
}
for q in question {
if dp[q.start][q.end] { // 팰린드롬인 경우,
print(1)
}
else { // 팰린드롬이 아닐 경우,
print(0)
}
}백준 Swift 1990번
문제 유형 : 팰린드롬
논리적으론 맞게 풀었는데, 시간 초과가 난다... 후..
Manacher 알고리즘을 적용하면 통과할 수 있을 것 같은데, 공부 후에 통과 코드를 올리도록 하겠다.
난이도 : 골드5
풀이 - 시간초과
// MARK: - 1990번(소수 + 팰린드롬) - 시간초과
import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (a, b) = (input[0], input[1])
func isPrime(_ num: Int) -> Bool {
if num < 4 {
return num == 1 ? false : true // 2와 3은 소수.
}
let end: Int = Int(sqrt(Double(num)))
for i in 2...end {
if num % i == 0 { // 나뉜다면, 소수가 아님.
return false
}
}
return true
}
func isPalindrome(_ num: [String]) -> Bool {
let length: Int = num.count
var flag: Bool = true
for i in 0..<length/2 {
if num[i] != num[length - 1 - i] {
flag = false
break
}
}
return flag
}
var answer: String = ""
for n in a...b {
if isPrime(n) { // 소수인데,
let temp = String(n).map{String($0)} // ex) 181 -> "181" -> ["1", "8", "1"]
if isPalindrome(temp) {
answer += "\(n)\n"
}
}
}
answer += "-1"
print(answer)백준 Swift 5502번
문제 유형 : 팰린드롬 / DP / LCS
비슷한 문제(백준 1695번)를 풀었어서, 쉽게 풀 수 있었다.
arr과 뒤집은 rArr의 LCS(최장 공통 부분수열)로 풀면 된다.
단, LCS(최장 공통 문자열)는 안된다.
처음엔 문제 없다고 생각했는데, 최장 공통 문자열로 했을 땐 틀려서 고민해보니, 반례가 있다.
반례 : "abca"
"abca" 일 때 최장 공통 부분수열은 3이다. => 답 : 4 - 3 = 1
"abca" 일 때 최장 공통 문자열은 1이다. => 답 : 4 - 1 = 3
answer = N - LCS
난이도 : 골드3
풀이1
// MARK: - 5502번(dp - LCS)
let N = Int(readLine()!)!
let arr: [String] = ["@"] + readLine()!.map{String($0)} // @는 인덱스 채우기용.
var dp = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
// LCS(최장 공통 부분수열)
for i in 1...N { // 뒤 부터 돌면서,
for j in 1...N { // 앞 부터 돌면서,
if arr[N + 1 - i] == arr[j] {
dp[i][j] = dp[i - 1][j - 1] + 1 // (이전 행, 이전열의 값) + 1
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) // max(이전 행의 같은 열, 같은 행의 이전 열)
}
}
}
// LCS(최장 공통 문자열) - 잘못됨. 반례 : "abca"
//for i in 1...N { // 뒤 부터 돌면서,
// for j in 1...N { // 앞 부터 돌면서,
// if arr[N + 1 - i] == arr[j] {
// dp[i][j] = dp[i - 1][j - 1] + 1
// }
// }
//}
print(N - dp[N][N]) // N - LCS값이 정답.풀이2 - .reversed() 사용 이유 = O(1)이라, 유의미한 시간 단축이 될 것이라 생각.
// MARK: - 5502번(dp - LCS) / .reversed()사용 : 눈에 띄는 시간 단축은 없네...
let N = Int(readLine()!)!
let arr: [String] = ["@"] + readLine()!.map{String($0)} // @는 인덱스 채우기용.
let rArr: [String] = arr.reversed()
var dp = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
// LCS(최장 공통 부분수열)
for i in 0..<N { // 뒤 부터 돌면서,
for j in 1...N { // 앞 부터 돌면서,
if rArr[i] == arr[j] {
dp[i + 1][j] = dp[i][j - 1] + 1 // (이전 행, 이전열의 값) + 1
}
else {
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - 1]) // max(이전 행의 같은 열, 같은 행의 이전 열)
}
}
}
print(N - dp[N][N]) // N - LCS값이 정답.백준 Swift 1053번
문제 유형 : DP, 팰린드롬
팰린드롬 문제들 중에 Swift로 한번도 풀리지 않은 문제들이 종종 있다.
공부하면서 Swift 기준 최초 풀이에 등극할 때 마다 기분이 참 좋다. ㅎㅎ
문제를 보고 사실 어떻게 풀어야 할지 모르겠어서 다른 블로그를 참고했다.
[풀이]
4개의 방법들 중, 방법4는 한번만 사용할 수 있다.
방법1,2,3은 팰린드롬을 만드는 데 이득이 되는 방향이다. 방법 1,2,3을 하고 난 뒤에 방법4를 확인하는건 이득이 없다.
최소의 횟수로 팰린드롬을 만들어야 하는 상황에서,
비유하자면 방법 1,2,3을 통해 올바르게 가고 있었는데, 방법4를 써서 후진하게 되는 것과 같다.
따라서, 방법4를 먼저 사용하고, 나머지 방법들을 통해 횟수를 기록한다.
하단 종이 풀이를 함께 참고하자.
dp[i][j] = arr[i] ~ arr[j] 까지의 문자열을 팰린드롬으로 만드는데 필요한 횟수다.
[dp배열 초기 세팅]
i부터 i까지는 이미 팰린드롬이니까 당연히 0이다.
초록 동그라미 부분도 미리 세팅한다. 값은 1 또는 0이다.
1. 방법 1이 더 필요한 경우
i부터 j-1까진 이미 팰린드롬이고, i부터 j까지 팰린드롬을 만들고 싶은 경우다. 방법1을 써서 맨 앞에 붙이면 될 것이다.
dp[i][j] = dp[i][j-1] + 1 (= 연산 횟수 1 증가)
2. 방법 2가 더 필요한 경우
i+1부터 j까진 이미 팰린드롬이고, i부터 j까지 팰린드롬을 만들고 싶은 경우다. 방법2을 써서 맨 앞(i)을 삭제하면 될 것이다.
dp[i][j] = dp[i+1][j] + 1 (= 연산 횟수 1 증가)
3. 방법 3가 더 필요한 경우
i+1부터 j-1까진 이미 팰린드롬이고, i부터 j까지 팰린드롬을 만들고 싶은 경우다.
3-1. arr[i]와 arr[j]가 같은 경우
i부터 j까지도 팰린드롬이다. 연산 횟수가 증가할 필요가 없다.(=연산할 필요가 없다.)
dp[i][j] = dp[i+1][j-1] (= 연산 횟수 증가X)
3-2. arr[i]와 arr[j]가 다른 경우
방법3을 써서 arr[i]를 arr[j]로 교체하면 될 것이다. (혹은 arr[j]를 arr[i]로.)
dp[i][j] = dp[i+1][j-1] + 1 (= 연산 횟수 1 증가)
마지막으로, 인덱스를 돌면서 최소값 of 최소값을 찾아 출력하면 된다.
var answer: Int = findMin(0, 0) // 방법4를 사용하지 않고, 방법1,2,3만을 이용해서 팰린드롬을 만드는데 필요한 횟수.
for i in 0..<N {
for j in i+1..<N {
let temp = findMin(i, j) + 1 // +1인 이유는, 방법4를 쓴 횟수 더해줌.
answer = min(answer, temp)
arr.swapAt(i, j)
}
}
print(answer)
난이도 : 골드2
참고 자료 : https://t.ly/fCF8 | https://for-development.tistory.com/96
풀이
// MARK: - 1053번(DP, 팰린드롬)
var arr: [String] = readLine()!.map{String($0)}
let N: Int = arr.count
func findMin(_ start: Int, _ end: Int) -> Int {
var dp = Array(repeating: Array(repeating: -1, count: N), count: N)
arr.swapAt(start, end) // 방법4 사용.
// 기본 세팅1.
for i in 0..<N {
dp[i][i] = 0
}
// 기본 세팅2.
for i in 0..<N-1 {
if arr[i] == arr[i + 1] { // 같으면,
dp[i][i + 1] = 0 // 방법 사용할 필요 없으니 0.
}
else { // 다르면,
dp[i][i + 1] = 1 // 방법1 사용.
}
}
for i in stride(from: N - 2, through: 0, by: -1) {
for j in i+2..<N {
if arr[i] == arr[j] { // 방법3 사용.
dp[i][j] = dp[i + 1][j - 1]
}
else { // 방법3 사용.
dp[i][j] = dp[i + 1][j - 1] + 1
}
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1, dp[i + 1][j] + 1) // 방법3, 방법1, 방법2 중 가장 작은 값 저장.
}
}
return dp[0][N - 1]
}
var answer: Int = findMin(0, 0) // 방법4를 사용하지 않고, 방법1,2,3만을 이용해서 팰린드롬을 만드는데 필요한 횟수.
for i in 0..<N {
for j in i+1..<N {
let temp = findMin(i, j) + 1 // +1인 이유는, 방법4를 쓴 횟수 더해줌.
answer = min(answer, temp)
arr.swapAt(i, j)
}
}
print(answer)
최근댓글