문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

 

나머지 빈 칸을 채우는 방식은 다음과 같다.

  1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

내가 푼 풀이

- 빈칸의 좌표를 기록해둔 뒤, 백트래킹을 이용해 숫자를 넣는다.

- 백트래킹을 사용할 때 이전의 기록들을 가져가야한다는점을 잊지말자.

- 이전의 기록들이 조건에 포함되어 불필요한 경우의수까지 탐색하지 않게 해야한다.

 

import Foundation

//입력받기
var board = [[Int]]()
var result = [[Int]]()
var blank = [(x: Int, y: Int)]()
for i in 0..<9 {
    board.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    for j in 0..<board[i].count {
        if board[i][j] == 0 {
            blank.append((x: i, y: j))
        }
    }
}

// 세로 비교
func col(loc: (x: Int, y: Int), num: Int) -> Bool {
    for i in 0..<9 {
        if board[i][loc.y] == num {
            return true
        }
    }
    return false
}

//가로 비교
func row(loc: (x: Int, y: Int), num: Int) -> Bool {
    return board[loc.x].contains(num)
}

// 인접된 사각형 비교
func square(loc: (x: Int, y: Int), num: Int) -> Bool {
    let leftUp = (x: loc.x / 3 * 3, y: loc.y / 3 * 3)
    for i in leftUp.x..<leftUp.x + 3 {
        for j in leftUp.y..<leftUp.y+3 {
            if board[i][j] == num {
                return true
            }
        }
    }
    return false
}
// dfs
func dfs(count: Int) {
    // 정답을 얻는다면 바로 리턴
    if !result.isEmpty {
        return
    }
    // 모든 빈칸을 조건에 맞춰 적었다면 리턴
    if count == blank.count {
        result = board
        return
    }
    // 현재 좌표
    var loc = blank[count]
    // 1부터 9까지 조건에 맞는 숫자를 넣는다.
    for i in 1...9 {
        if !row(loc: loc, num: i) && !col(loc: loc, num: i) && !square(loc: loc, num: i) {
            board[loc.x][loc.y] = i
            dfs(count: count+1)
            board[loc.x][loc.y] = 0
        }
    }
}
dfs(count: 0)

for k in 0..<result.count {
    let ans = result[k].map{String($0)}.joined(separator: " ")
    print(ans)
}

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-1004 어린 왕자 Swift  (1) 2024.04.20
BOJ-2447 별 찍기-10 Swift  (0) 2024.04.15
BOJ-1013 Contact Swift  (0) 2024.04.15
BOJ-5430 AC Swift  (1) 2024.04.15
BOJ-1253 좋다 Swift  (0) 2024.04.14

문제

“무한히 넓은 저 우주에 인류만이 홀로 존재한다면, 그건 정말 슬픈 일이 아닐까요”

푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.

이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.

전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ ( ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.

(xyx)+ ( ) 는 괄호 내의 xyx의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.

  • 1+ = { 1, 11, 111, 1111, 11111, … }
  • 10+ = { 10, 100, 1000, 10000, 100000, … }
  • (01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
  • (1001)+ = { 1001, 10011001, 100110011001, … }
  • 10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
  • (10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }

반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.

  • (100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }

최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.

  • (100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ N ≤ 200)의 범위를 갖는다.

출력

각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.

내가 푼 풀이

- 처음엔 그리디기법으로 입력받는수 100, 01 에따라 다음에 올 수 있는 수들만 넣었더니 틀렸다.

- 그리디로 하니까 반례들이 너무많았고 정확히 답을 구할 수 없었다.

- 다른사람의 풀이를 참고해봤는데, 다양하게 풀이 방법이 있었다..

- 이 문제는 완전탐색 dfs를 이용했지만 조건을맞춰서 탐색하였다.

 

맨처음에 올수있는 문자는 100혹은 01이다.

100이 온다면 0, 1이 올 수 있다

01이 온다면 다시 100이 오거나, 01이 올 수 있다.

100다음에 0이 온다면 0또는 1이 올수있다 이는 위의 100이 왔을때의 조건과 같다.

100다음에 1이 온다면 1 또는 01 또는 100이 올 수 있다.

이렇게 각각 문자간의 관계가 형성되는데, 관계만 따지고 다음에 올 수 있는 모든 경우의 수를 탐색한다면 시간초과가 날 것이다.

조건을 더 추가해서, 앞의 문자를 미리 받고 해당문자와 이전문자의 관계있는문자가 동일하다면 탐색하는 방향으로 지었다.

 

예) 100101

1. 첫번째 올 수 있는 문자: [100, 01] , 앞의 문자 스캔: 100 , 10

100이 동일하므로 100 배치 -> 100

 

2. 100다음에 올 수 있는문자: [0,1] , 앞의 문자 스캔 1

1이 동일하므로 1 배치 -> 1001

 

3. 1다음에 올 수 있는문자: [1, 01, 100] , 앞의 문자 스캔 [0, 01, 01x]

01이 동일하므로 01 배치 -> 100101 결과 YES

 

코드로 구현하면 다음과 같다.

 

import Foundation

// 문자 해당 범위를 출력하기위해 별도의 메서드 생성
// 문자를 받는중 주어진 문자열을 초과한다면 임의의 문자(여기선 2)를 더 붙여준다.
extension String {
    func getRangeString(start: Int, end: Int, max: Int) -> String {
        var result = ""
        for i in start...end {
            if i >= max {
                result += "2"
            } else {
                result += "\(self[self.index(startIndex, offsetBy: i)])"
            }
        }
        return result
    }
}

// 테스트케이스 수
let T = Int(readLine()!)!
var result = String()

// dfs
func dfs(str: String, targetStr: String, count: Int, compare: String) {
    var target = targetStr
    // 찾는도중에 이미 찾았거나, 찾는범위가 주어진 문자열을 넘어버린경우 종료
    if result == "YES" || count > target.count {
        return
    }
    // 배치한 문자가 주어진 문자열과 동일하다면 YES
    // 하지만 마지막문자가 100으로 끝난다면 주어진 규칙과 맞지않는다.
    if str == target && compare != "100" {
        result = "YES"
        return
    }
    
    // 이전 문자와의 관계에 따라서 다음에 올 문자를 찾는다.
    // 맨 처음시작할때나 이전문자가 01 일때 올수있는문자 100, 01
    if compare == "" {
        var s1 = ""
        var s2 = ""
        
        //뒤의문자를 탐색
        if count+2 <= target.count {
            s1 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        if count+1 < target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        
        //앞의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
    } else if compare == "100" {
        // 이전문자가 100일때, 올수있는문자 0,1
        var s = ""
        
        //뒤의문자 탐색
        if count+1 <= target.count {
            s = target.getRangeString(start: count, end: count, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s == "0" {
            dfs(str: str + "0", targetStr: target, count: count+1, compare: "100")
        }
    } else if compare == "1" {
        // 이전문자가 1일때, 올수있는문자 100, 01, 1
        var s1 = ""
        var s2 = ""
        var s3 = ""
        
        //뒤의 문자 탐색
        if count <= target.count {
            s1 = target.getRangeString(start: count, end: count, max: target.count)
        }
        if count + 1 <= target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        if count + 2 <= target.count {
            s3 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
        if s3 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
    }
    
}
for i in 0..<T {
    result = "NO"
    var target = readLine()!
    dfs(str: "", targetStr: target, count: 0, compare: "")
    print(result)
}

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-2447 별 찍기-10 Swift  (0) 2024.04.15
BOJ-2580 스도쿠 Swift  (0) 2024.04.15
BOJ-5430 AC Swift  (1) 2024.04.15
BOJ-1253 좋다 Swift  (0) 2024.04.14
BOJ-5052 전화번호 목록 Swift  (0) 2024.04.14

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

내가 푼 풀이

- 해당 기능 R, D를 구현하면 된다.

- 문제는 주어지는 함수가 최대 100,000에 테스트케이스는 최대 100개이므로 O(N^2)의 시간복잡도를 갖는 알고리즘은 아마 시간초과가 날것이다.

- 문자열과는 사이가 나쁜 Swift..

- R: 뒤집는 기능이지만 실제로 뒤집진 않는다(뒤집으면 최대 10만번 뒤집어야함)

- D: 첫째 수를 빼지만 실제로 removefirst()를 하지않는다(배열 특성상 첫번째수를 빼려면 모든 배열의 수를 읽어야함 N번)

 

다양하게 구현하는방법이 있겠지만, 이번문제는 배열의 첫번째인덱스 start,와 마지막인덱스 end를 이용해서 풀었다.

만약 뒤집혀있는배열이라면 end의 문자를 빼야하므로 end-1

뒤집혀있지않는 배열이라면 start+1

모두 빼내면 결국 start...end 범위의 배열만 남는다.

여기서 뒤집는함수 R이 짝수번 발생했다면 뒤집기의뒤집기는 결국 그대로라 그대로 출력하지만

홀수번 발생했다면 end...start 로 출력하면된다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 테스트케이스 수
let T = Int(readLine()!)!

for i in 0..<T {
    // 입력받기
    let p = readLine()!
    let n = Int(readLine()!)!
    var arr = [Int]()
    let strNum = readLine()!
    var str = ""
    
    // 입력받은 배열의문자열을 숫자배열로 변환
    for j in strNum {
        if let num = Int(String(j)) {
            str += String(j)
        } else {
            if str != "" {
                arr.append(Int(str)!)
                str = ""
            }
        }
    }
    
    // start, end
    var start = 0
    var end = arr.count - 1
    // reversed: 뒤집혀있는가?
    // check는 문제에 정의된 조건으로 빈배열일때 첫번째수를 빼려고한다면 error, 이를 판단하기위해
    var reversed = false
    var check = true
    
    // 주어진 함수의문자열 실행
    for k in p {
        // 뒤집혀있는지 확인
        if k == "R" {
            reversed = !reversed
        } else if k == "D" {
            // 배열이 비어있거나, 배열수 이상으로 빼내서 start인덱스가 end를 넘어버렸다면
            if arr.isEmpty || start > end {
                check = false
            } else {
                // 뒤집힘에 따라 인덱스 조절
                if reversed {
                    end -= 1
                } else {
                    start += 1
                }
            }
        }
    }
    // 결과 출력 문자열
    var result = ""
    
    // 빈배열에서 D함수 실행했다면 error
    if check {
        if arr.isEmpty || start > end{
            print("[]")
        } else {
            // 뒤집혀있다면 범위 거꾸로 출력
            if reversed {
                for j in (start...end).reversed() {
                    if j == start {
                        result += "\(arr[j])"
                    } else {
                        result += "\(arr[j]),"
                    }
                }
            } else {
                // 그대로라면 그대로 출력
                for j in start...end {
                    if j == end {
                        result += "\(arr[j])"
                    } else {
                        result += "\(arr[j]),"
                    }
                }
            }
            print("[\(result)]")
        }
    } else {
        print("error")
    }
}

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-2580 스도쿠 Swift  (0) 2024.04.15
BOJ-1013 Contact Swift  (0) 2024.04.15
BOJ-1253 좋다 Swift  (0) 2024.04.14
BOJ-5052 전화번호 목록 Swift  (0) 2024.04.14
BOJ-2470 두 용액 Swift  (0) 2024.04.14

최근에 앱을 만들때, 로컬저장소 UserDefaults를 이용하다가 SQLite로 변경한 적이 있었다.

오토레이아웃을 확인하고, 앱 사용자의 느낌을 받기위해 핸드폰에 직접 넣고 돌려봤는데 DB생성오류가 계속 뜨는것이었다.

 

열심히 구글링 해본 결과 아래 사이트에서 도움을 받았다.

https://stackoverflow.com/questions/67097212/sqlite-db-create-error-in-real-ios-device

 

SQLite db create error in real iOS device

I'm trying to learning swiftUi and I've included SQLIte in my project. I've successfully created db, tables and func to read and insert records and I tested it in Xcode emulator and all works fine....

stackoverflow.com

 

이전코드:

        let filePath = try! FileManager.default.url(for: .documentDirectory,
                                                    in: .userDomainMask,
                                                    appropriateFor: nil,
                                                    create: false).appendingPathExtension(databaseName).path

 

 

바꾼코드:

        let path = try! FileManager.default.url(for: .applicationSupportDirectory,
                                                in: .userDomainMask,
                                                appropriateFor: nil,
                                                create: true).appendingPathComponent(databaseName).path

 

 

.documentDirectory: 사용자 대상파일, .applicationSupportDirectory: 앱의 지원파일로 후자가 적합하다고 한다.

applicationSupportDirectory로 바꿔주니 데이터베이스가 정상적으로 만들어졌다.

 

https://developer.apple.com/documentation/foundation/filemanager/searchpathdirectory

 

FileManager.SearchPathDirectory | Apple Developer Documentation

The location of significant directories.

developer.apple.com

https://developer.apple.com/documentation/foundation/filemanager

 

FileManager | Apple Developer Documentation

A convenient interface to the contents of the file system, and the primary means of interacting with it.

developer.apple.com

 

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

내가 푼 풀이

- N개의 수를 순회하면서 투포인터 알고리즘으로 합이 같은지 찾았다.

- 투포인터 알고리즘을 사용하기 전에 A정렬을 오름차순으로 정렬후, start: 첫번째 end: 마지막번째 위치로 이용했다.

- 합산한 값이 크다면 end를 줄이고, 작다면 start를 늘려 찾고, 같은 인덱스(같은원소인경우) 패스했다.

 

import Foundation

// 입력받기
let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map{Int(String($0))!}
var count = 0
A.sort()

for i in 0..<N {
    var num = A[i]
    var start = 0
    var end = A.count - 1
    // 투포인터 알고리즘을 이용
    // 합산한 값이 작다면 start + 1
    // 합산한 값이 크다면 end - 1
    while start < end {
        if start == i {
            start += 1
            continue
        } else if end == i {
            end -= 1
            continue
        }
        let sum = A[start] + A[end]
        
        if sum == num {
            count += 1
            break
        }
        if sum > num {
            end -= 1
        } else {
            start += 1
        }
    }
    
}
print(count)

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-1013 Contact Swift  (0) 2024.04.15
BOJ-5430 AC Swift  (1) 2024.04.15
BOJ-5052 전화번호 목록 Swift  (0) 2024.04.14
BOJ-2470 두 용액 Swift  (0) 2024.04.14
BOJ-14503 로봇 청소기 Swift  (0) 2024.04.13

투포인터 알고리즘

- 리스트에 순차적으로 접근할 때 두 원소의 위치를 기록하는 알고리즘

- 일반적으로 정렬된 리스트나 배열에서 사용한다.

- 보통 정해진 두 위치(첫번째: start, 마지막:end)는 start <= end를 만족한다.

 

 

투포인터 단계

- 배열또는 리스트에 두개의 위치를 지정한다(보통 맨 앞 위치 start, 맨 뒤 위치 end)

- 두 포인터 사이의 구간을 확인하고 조건과 비교한다.

- 해당 조건을 만족한다면, 추가로 위치를 움직이거나, 결과를 리턴한다.

- 해당 조건을 만족하지 않는다면, 위치를 움직여 재탐색후 조건과 비교한다.

 

시간복잡도: 포인터를 배열이나 리스트의크기(N)만큼 증가시키므로 O(N)

 

예시: BOJ-2470 두 용액

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var result = Int.max
var resultArr = [Int]()
var start = 0
var end = arr.count - 1
arr.sort(by: <)

// 왼쪽인덱스 start, 오른쪽인덱스 end가 서로 만날때 까지
while start < end {
    let leftNum = arr[start]
    let rightNum = arr[end]
    let sum = leftNum + rightNum
    
    // 더한값이 양수라면 오른쪽인덱스를 왼쪽으로 움직여 오른쪽 원소값을 더 작게만든다
    // 더한값이 음수라면 왼쪽인덱스를 오른쪽으로 움직여 왼쪽 원소값을 더 크게만든다.
    if sum > 0 {
        end -= 1
    } else if sum < 0 {
        start += 1
    } else {
        resultArr = [leftNum, rightNum]
        break
    }
    // 더한값의 절댓값이 이전에 구한 값보다 작아지면 갱신
    if abs(sum) < result {
        result = abs(sum)
        resultArr = [leftNum, rightNum]
    }
    
}
print(resultArr.map{String($0)}.joined(separator: " "))

 

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

  • 긴급전화: 911
  • 상근: 97 625 999
  • 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

내가 푼 풀이

- 전화번호가 차례로주어지는것이 아니라 이미 목록에 있고, 정렬할 수 있다.

- 전화번호를 숫자형식으로 오름차순 정렬하는것과 문자형식으로 정렬하는것이 결과가 다르다.

"""
113
12340
123440
12345
98346
문자열배열 오름차순정렬: ["113", "12340", "123440", "12345", "98346"]
숫자배열 오름차순정렬:   [113, 12340, 12345, 98346, 123440]
"""

- 이전의 번호가 접두사로 존재한다면 이 목록은 일관성이 없다고 한다.

- 숫자배열과 다르게 문자열배열의 정렬은 각각 자리마다의 문자를 비교하므로 접두사를 찾기에 더 알맞은 정렬방법이 된다.

- 이렇게 정렬된 문자열배열을 순회하며 i+1번째 문자열의 접두사가 i번째문자인지만 파악하면 된다.

 

import Foundation

// 입력받기
let t = Int(readLine()!)!

for i in 0..<t {
    let n = Int(readLine()!)!
    var str = [String]()
    var result = true
    for j in 0..<n {
        let num = readLine()!
        str.append(num)
    }
    str.sort(by: <)
    for j in 0..<str.count-1 {
        if str[j+1].hasPrefix(str[j]) {
            result = false
            break
        }
    }
    if result {
        print("YES")
    } else {
        print("NO")
    }
}

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-5430 AC Swift  (1) 2024.04.15
BOJ-1253 좋다 Swift  (0) 2024.04.14
BOJ-2470 두 용액 Swift  (0) 2024.04.14
BOJ-14503 로봇 청소기 Swift  (0) 2024.04.13
BOJ-1011 Fly me to the Alpha Centauri Swift  (0) 2024.04.13

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

내가 푼 풀이

- N은 최대 100,000으로 O(N^2)로는 무조건 시간초과가 뜰꺼라 생각했다.

- 투포인터 알고리즘을 이용해서 각각 원소끼리 더해주고,

더한값이 양수라면 0에 가까워지기 위해 오른쪽인덱스를 왼쪽으로, 더한값이 음수라면 0에 가까워지기 위해 왼쪽인덱스를 오른쪽으로 이동한다.

- 더한값의 절댓값이 0에 가까워지면 따로 원소를 저장하고, 0이라면 바로 저장 후 탈출한다.

 

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var result = Int.max
var resultArr = [Int]()
var start = 0
var end = arr.count - 1
arr.sort(by: <)

// 왼쪽인덱스 start, 오른쪽인덱스 end가 서로 만날때 까지
while start < end {
    let leftNum = arr[start]
    let rightNum = arr[end]
    let sum = leftNum + rightNum
    
    // 더한값이 양수라면 오른쪽인덱스를 왼쪽으로 움직여 오른쪽 원소값을 더 작게만든다
    // 더한값이 음수라면 왼쪽인덱스를 오른쪽으로 움직여 왼쪽 원소값을 더 크게만든다.
    if sum > 0 {
        end -= 1
    } else if sum < 0 {
        start += 1
    } else {
        resultArr = [leftNum, rightNum]
        break
    }
    // 더한값의 절댓값이 이전에 구한 값보다 작아지면 갱신
    if abs(sum) < result {
        result = abs(sum)
        resultArr = [leftNum, rightNum]
    }
    
}
print(resultArr.map{String($0)}.joined(separator: " "))

'코딩테스트 > 백준' 카테고리의 다른 글

BOJ-1253 좋다 Swift  (0) 2024.04.14
BOJ-5052 전화번호 목록 Swift  (0) 2024.04.14
BOJ-14503 로봇 청소기 Swift  (0) 2024.04.13
BOJ-1011 Fly me to the Alpha Centauri Swift  (0) 2024.04.13
BOJ-10974 모든 순열 Swift  (0) 2024.04.13

+ Recent posts