본문 바로가기

Algorithm39

[Algorithm/BOJ] 2910 - 빈도 정렬 Swift 문제풀이: 처음에 딕셔너리를 쓰지 않고 0 ~ c+1 까지 개수의 배열을 만들어 정렬시켰다. 하지만 메모리 초과로 인해 런타임 에러가 발생했고 딕셔너리를 통해 해결했다. 딕셔너리의 해당 숫자에 따른 빈도와 순서 정보를 저장했다. 숫자, 빈도, 순서 정보를 배열에 할당해서 빈도가 같으면 순서가 빠른 순서, 같지 않다면 빈도가 많은 순서로 정렬시켰다. 코드: // fq: 빈도, v: 값, s: 순서 typealias Count = (fq: Int, v: Int, s: Int) let input = readLine()!.split(separator: " ").map { Int(String($0))! } let n = input[0] let c = input[1] var nums = readLine()!.spl.. 2021. 7. 1.
[Algorithm/BOJ] 9466 - 텀 프로젝트 Swift 문제 풀이: 텀 프로젝트를 위한 팀을 만들면서 원하는 팀원을 각자 고른다. 여기서 중요한건 DFS를 이용해서 Cycle을 확인해야 하는 것이다. 위 표에서 4 -> 7 -> 6 -> 4와 같은 Cycle을 확인할 수 있고 4, 6, 7은 같은 팀이 된다. 3번은 자기 자신을 선택했으므로 1번과 5번은 3번을 선택했지만 팀을 이룰 수 없고 3번 혼자 팀이 된다. 그리고 전체 인원에서 팀이 된 모든 번호의 개수를 제외하면 팀을 이루지 못한 인원의 수가 나와 답이 된다. 코드: func dfs( _ num: Int, _ nums: [Int], _ check: inout [Bool], _ team: inout [Int], _ teams: inout [[Int]] ) { check[num] = true team... 2021. 6. 17.
[Algorithm/BOJ] 6593 - 상범 빌딩 Swift 문제 풀이: 빌딩이 정육면체이므로 동서남북상하로 BFS를 돌려서 이동하는 시간을 구해야 한다. BFS를 쓸 줄 안다면 쉽게 해결할 수 있는 문제이다. 코드: typealias Coord = (l: Int, r: Int, c: Int) let d: [Coord] = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)] func bfs( _ start: Coord, _ exit: Coord, _ check: inout [[[Int]]], _ building: [[[String]]], _ b: Coord ) { var q = [Coord]() q.append(start) check[start.l][start.r][start.c] = 1 var index = 0.. 2021. 6. 17.
[Algorithm/BOJ] 1431 - 시리얼 번호 Swift Python 문제 풀이: A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 문제에 명시된데로 정렬하면 된다. 2번에서 Int로 캐스팅되는 것만 더해서 비교하는 것만 따로 구현해준다. 코드: Swift var serials = [String]() for _ in 0 .. Int { let str = Array(s).map { Strin.. 2021. 6. 3.
[Algorithm/BOJ] 14500 - 테트로미노 Swift Python 문제 풀이: 모든 도형을 일일이 회전하고 싶지 않아서 고민을 하다가 인터넷에서 접근 방법만 확인하고 풀었다. ㅜ, ㅏ, ㅗ, ㅓ를 제외한 모든 도형은 dfs로 해결할 수 있다는 것을 깨달았다. ㅜ 형태의 테트로미노는 (0,0)을 기준으로 다음 그림과 같이 만들 수 있다. 한 좌표를 기준으로 dfs로 ㅜ형태의 테트로미노를 제외한 모든 도형의 최댓값을 갱신하고 ㅜ형태의 테트로미노를 따로 계산하여 최댓값을 갱신하면 된다. 코드: Swift typealias Coord = (r: Int, c: Int) let nm = readLine()!.split(separator: " ").map { Int(String($0))! } let n = nm[0] let m = nm[1] var paper = [[Int]]() .. 2021. 6. 2.
[Algorithm/BOJ] 4889 - 안정적인 문자열 Swift Python 문제풀이: 문제에서 말하는 안정적인 배열로 만드는 연산 횟수를 구하면 된다. 스택을 사용해서 "}" -> "{"로 바꾸고 연산 횟수를 증가시키고 반대로 "{" -> "}"로 바꾸는 연산 횟수는 연산 처리후 스택에 남아 있는 개수의 절반이 곧 연산 횟수가 된다. why? 스택에 "{{{{"가 남아 있을 때 "{}{}"처럼 2번만 바꿔주면 안정적인 배열이 된다. "-"가 나오면 반복문을 빠져 나온다. 코드: Swift var index = 0 while true { let data = Array(readLine()!) if data.first == "-" { break } var stack = [Character]() var cnt = 0 for d in data { if d == "{" { stack.ap.. 2021. 5. 21.
[Algorithm] Queue 구현 Swift Swift로 Queue 구현에 관한 두 가지 방법을 기록합니다. 큐를 구현하는 이유는 다음과 같다. 1. Swift에서는 Queue를 지원해주지 않는다. 2. 배열 하나만을 이용해서 큐를 구현할 수 있지만 효율성이 떨어져 다음과 같은 방법을 사용한다. -> why? append()를 이용해서 enqueue하고 removeFirst()로 dequeue하는데 removeFirst()의 복잡도가 O(n)이다. 1. 인덱스를 이용한 큐 구현 struct Queue1 { var q = [T]() var index = 0 var count: Int { q.count - index } var isEmpty: Bool { q.count == index } var first: T? { index < q.count ? q.. 2021. 5. 13.
[Algorithm/BOJ] 18258 - 큐2 Swift Python 문제 풀이: 스위프트에서 큐를 지원해주지 않아 직접 구현해야 합니다. 하지만 배열 하나로 구현했을 때 시간상 효율이 좋지 않아 두개의 배열(스택)을 이용해서 큐를 구현했습니다. 그래도 시간초과가 나므로 라이노님의 빠른 입력 클래스를 사용했습니다. 또한, push, pop, empty, size, front, back에 해당하는 아스키 코드를 미리 구해 넣어 시간을 줄였습니다. 파이썬은 collections의 deque를 사용해서 쉽게 풀 수 있었습니다. 코드: Swift import Foundation // 라이노님 빠른 입력 FileIO final class FileIO { private var buffer:[UInt8] private var index: Int init(fileHandle: FileH.. 2021. 5. 12.
[Algorithm/BOJ] 1406 - 에디터 Swift Python 문제 풀이: 이 문제의 핵심은 2개의 스택을 사용하는 것이다. L: 왼쪽 스택에서 pop하고 그 값을 오른쪽 스택에 추가한다. D: 오른쪽 스택에서 pop하고 그 값을 왼쪽 스택에 추가한다. B: 왼쪽 스택에서 pop한다. P: 왼쪽 스택에 값을 추가한다. 오른쪽 스택은 문자열이 거꾸로 추가되었으므로 마지막에 오른쪽 스택을 reversed해줘야 한다. 처음에 배열로 접근해서 풀었을 때 스위프트는 시간초과가 나고 파이썬은 같은 풀이로 푼 문제가 맞았다. 원인은 스위프트에서 readLine()!.split(separator: " ").map { Int(String($0))! } 를 통해 Int형 배열로 입력을 받는 과정에서 시간이 더 소모된 것이 영향이 있는 것 같다. 그래서 스위프트는 배열로 입력을 받지 .. 2021. 5. 11.
[Algorithm/BOJ] 1302 - 베스트셀러 Swift Python 문제 풀이: Python은 Counter 클래스를 사용하면 쉽게 풀 수 있는 문제이다. 하지만, Swift는 따로 지원해주지 않기 때문에 딕셔너리를 카운터로 사용해야 한다. 이 방법은 이 문제가 아니더라도 쓸 일이 있어서 알아두면 좋다. 마지막에 정렬은 팔린 횟수가 많은 순으로 정렬하고 같다면 사전순으로 정렬한다. 코드: Swift let n = Int(readLine()!)! var soldCounter = [String:Int]() for _ in 0 ..< n { let book = readLine()! soldCounter[book, default: 0] += 1 } print(soldCounter) let result = soldCounter.sorted { $0.value == $1.value.. 2021. 5. 9.

티스토리툴바