✍️ 첫번째 접근

priority_queue를 사용해서 가장 몸무게 작은 사람들순으로 보드를 태우려고 했지만 틀린 결과를 받았다. 다음과 같은 반례로 인해 보드에 [10,20], [30], [40]으로 3개의 보드를 사용하는 것이 아닌 [10,40], [20,30]으로 2개의 보드를 태울 수 있기 때문이다. 그래서, 오름차순으로 정렬하고 가장 몸무게가 작은 사람과 가장 몸무게가 큰 사람 중 limit보다 작거나 같은 경우에 보드에 태우는 것으로 접근했다. 하지만 효율성에서 시간 초과가 발생했다.

입력
[10, 20, 30, 40], 50

출력
2

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int solution(vector<int> people, int limit) {
    if(people.size() < 2)
        return 1;
    int answer = 0;
    sort(people.begin(),people.end());
    for(int i = 0; i < people.size(); ++i) {
        if(people[i] == INF)
            continue;
        bool flag = true;
        for(int j = people.size()-1; j >= 0; --j) {
            if(people[i]+people[j] <= limit) {
                people[i] = INF; people[j] = INF;
                ++answer;
                flag = false;
                break;
            }
        }
        if(flag)
            ++answer;
    }


    return answer;
}

✍️ 두번째 접근

첫번째 접근에서 2개의 for문을 사용하는데 맨 앞과 맨 뒤에서부터 시작하여 값을 계산한다? 그럼 굳이 for문을 2개 쓰지 말고, 투 포인터 개념을 적용함으로써 해결하였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    if(people.size() < 2)
        return 1;
    int answer = 0;
    sort(people.begin(),people.end());
    int left = 0, right = people.size()-1;
    while(left <= right) {
        if(people[left] + people[right] <= limit)
            ++left;
        --right;
        ++answer;
    }

    return answer;
}

✍️ 첫번째 접근

각 편의점과 도착지 좌표를 같이 저장한다. 현재 좌표와 비교하였을 때 가장 가까운 좌표로 가게끔 우선순위를 정함으로써 접근하였지만 틀린 결과를 받게 되었다.

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int t, n;
int nx, ny;
int desX, desY;

bool compare(const pair<int,int>& a, const pair<int,int>& b) {
    int sumA = abs(a.first-nx)+abs(a.second-ny);
    int sumB = abs(b.first-nx)+abs(b.second-ny);
    return sumA > sumB;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        cin >> nx >> ny;
        vector<pair<int,int>> con;
        while(n--) {
            int conX, conY;
            cin >> conX >> conY;
            con.push_back({conX,conY});
        }
        cin >> desX >> desY;
        con.push_back({desX,desY});
        while(true) {
            sort(con.begin(),con.end(),compare);
            int sum = abs(con.back().first-nx)+abs(con.back().second-ny);
            if(sum > 1000) {
                cout << "sad" << '\n';
                break;
            }
            if(con.back().first == desX && con.back().second == desY) {
                cout << "happy" << '\n';
                break;
            }
            nx = con.back().first; ny = con.back().second;
            con.pop_back();
        }

    }

    return 0;
}

✍️ 두번째 접근

반례는 다음과 같다. 첫번째 접근은 현재 좌표와 비교하였을 때 가장 가까운 좌표가 여러개이고 무엇을 선택하냐에 따라 값이 달라질 수 있다. 반례

입력
1
9
3000 3000
3000 2000
3000 1000
2000 1000
1000 1000
4000 1000
5000 1000
5000 0
3000 0
1000 0
5000 -1000

출력
happy

따라서, 상근이의 집 좌표부터 시작해서 방문하지 않은 편의점을 순회한다. 이때 편의점을 도달할 수 없다면 즉 맨허튼 거리가 1,000을 넘어간다면 continue한다. 또한, 도달한 좌표가 페스티벌의 좌표라면 "happy"를 출력함으로써 문제를 해결하였다.

#include <iostream>
#include <queue>
#include <algorithm>

#define X first
#define Y second

using namespace std;

int t, n;
int nx, ny;
int desX, desY;
pair<int,int> con[102]; // 편의점 좌표 저장하는 배열
bool visited[102];  // 편의점 방문 여부를 저장하는 배열
bool flag;  // 페스티벌에 도착할 수 있는지 판단하는 변수

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--) {
        // 초기화
        fill(con,con+102,pair(-1,-1));
        fill(visited,visited+102,0);
        flag = true;
        cin >> n;
        cin >> nx >> ny;
        for(int i = 0; i < n; i++) {
            int conX, conY;
            cin >> conX >> conY;
            con[i] = {conX,conY};
        }
        cin >> desX >> desY;
        queue<pair<int,int>> q;
        q.push({nx,ny});    // 상근이의 집에서부터 시작
        while(!q.empty()) {
            auto cur = q.front(); q.pop();
            if(abs(cur.X-desX)+abs(cur.Y-desY) <= 1000) {   // 현재 위치에서 페스티벌에 도착할 수 있다면
                cout << "happy" << '\n';
                flag = false;
                break;
            }
            for(int i = 0; i < n; i++) {
                if(visited[i])  // 이미 방문한 편의점 제외
                    continue;
                if(abs(cur.X-con[i].X)+abs(cur.Y-con[i].Y) > 1000)  // 도달할 수 없는 편의점 제외
                    continue;
                q.push({con[i].X,con[i].Y});
                visited[i] = true;
            }
        }
        if(flag)
            cout << "sad" << '\n';
    }

    return 0;
}

✍️ 첫번째 접근

효율성을 생각하지 않고 제한사항을 제대로 확인하지 않는다면, 무작정 순회하면서 각 돌의 값을 -1을 계속 진행하는 과정을 생각할 수 있다. 하지만 이는 비효율적이다. 필자는 어쨌든간에 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수가 K개 이므로 K만큼의 범위를 넘어서지 못한다는 점에 주목했다. 슬라이딩 윈도우 기법으로 K만큼의 범위에서 합이 제일 적은 것 그리고 그 범위 중 가장 큰 값을 답이라고 생각하였지만 틀렸다는 결과를 받았다.

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var minValue = 0x3f3f3f3f
    var idx = -1
    for i in 0..<stones.count {
        if i+k-1 >= stones.count {
            break
        }
        var sum =  Array(stones[i...i+k-1]).reduce(0,+)
        if minValue > sum {
            minValue = sum
            idx = i
        }
    }
    return Array(stones[idx...idx+k-1]).max()!
}

✍️ 두번째 접근

아래와 같은 반례로 인해 필자의 첫번째 접근은 틀렸다.

K=3
555229

"555"에서 합이 15이고, "229"에서 합이 13이다. 첫번째 접근처럼 했다면, "229"의 합이 더 작으므로 정답은 9가 된다. 하지만 정답은 5이므로 잘못된 접근임을 알 수 있다. 따라서 이와 같은 접근 말고 K만큼의 범위를 돌면서 그 중 가장 큰 값을 구하고, 그 가장 큰 값들 중 가장 작은 값을 구하는 방식으로 하였다. 또한 언어를 C++로 바꿨는데 정확성 테스트케이스는 맞지만 효율성에서 시간 초과라는 결과를 받았다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0x3f3f3f3f;
    for(int i = 0; i < stones.size(); ++i) {
        if(i+k-1 >= stones.size())
            break;
        int maxValue = -1;
        for(int j = i; j < i+k; ++j) {
            if(maxValue < stones[j])
                maxValue = stones[j];
        }
        if(answer > maxValue)
            answer = maxValue;
    } 
    return answer;
}

✍️ 세번째 접근

아무래도 K만큼의 범위를 돌면서 중복되어 계산되는 값이 있는데 이에 대한 연산을 재사용하지 않아서 발생했다고 판단했다. 그리고 추가적으로 계속해서 K만큼의 범위에서 최댓값을 찾는 연산을 하지 않기 위해 grater를 사용해 내림차순으로 정렬되게 하여 그 첫번째에 해당하는 값이 최댓값이라고 계산했다. answer 변수와 현재 얻은 최댓값 중 더 작은 값이 answer라고 판단함으로써 해결했다. 이 문제로 얻은 점은 제대로된 슬라이딩 윈도우를 사용하려면 재사용할 수 있는 부분은 재사용하자는 것이고 주어진 자료형을 잘 활용하자는 것이다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    multimap<int,int,greater<int>> mp;
    multimap<int, int>::iterator iter;

    for(int i = 0; i < k; ++i)
        mp.insert({stones[i],i});

    answer = mp.begin()->first;

    for(int i = 0; i < stones.size(); i++) {
        if(i+k >= stones.size())
            break;
        iter = mp.find(stones[i]);
        mp.erase(iter);
        mp.insert({stones[i+k],i+k});
        answer = min(answer,mp.begin()->first);
    }

    return answer;
}

✍️ 첫번째 접근

2중 for문을 사용하고 싶은 마음이 근질근질하지만..4 ≤ numbers의 길이 ≤ 1,000,000라는 조건을 보면 싹 사라진다. N이 최대 1,000,000이므로 최대 O(NlogN)으로 끊어야한다. stack 개념을 사용함으로써 접근하였는데 예를 들어 stack 안에 2가 있으면 현재 2보다 뒤에 있는 큰 수를 찾지 못했서 stack에 있을 의미한다. numbers에 있는 각 원소를 접근할 때마다 stack에 넣는다. 넣기 전에, stack에 무언가 있으면 제일 최근에 들어간 값과 현재 접근한 값과 비교를 하여 현재 접근한 값이 더 크다면 뒤에 있는 큰 수를 찾은 것이다. 찾았으므로 stack에 있는 제일 최근에 들어간 값을 remove해준다. 이러한 방식으로 푼다면 stack에는 값이 남아있을 수도 있는데 남아있는 값은 자신보다 뒤에 있는 큰 수가 없음을 의미한다. 맨처음에 result 배열을 -1로 초기화했기 때문에 따로 구현하지도 않아도 된다.

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var result: [Int] = Array(repeating: -1, count: numbers.count)  // 큰 수가 될 수 없을 수도 있으므로 -1로 초기화
    var s: [(x:Int, idx: Int)] = []
    for i in 0..<numbers.count {
        while !s.isEmpty {
            let cur = s.last!
            if numbers[i] > cur.x { // 큰 수 찾음
                s.removeLast()
                result[cur.idx] = numbers[i]
            }
            else {
                break
            }
        }
        s.append((x:numbers[i],idx: i))
    }

    return result
}

✍️ 첫번째 접근

현재 층에서 0층으로 가기 위해 필요한 마법의 돌의 최소값을 찾는 문제이다. 엘리베이터가 움직일 때마다 항상 최적의 결정을 하면서 접근해야겠다고 생각했다. 필자는 아래와 같은 논리로 접근하였다. 현재 층이 2554층이고, 목표는 0층이라고 생각하자. 현재 층에서 맨 오른쪽 자릿수 즉, 일의 자리부터 0으로 바꿀 것이다. 각 자릿수를 모두 0으로 만들면 목표 층으로 갈 수 있기 때문이다. 하지만 이렇게 할 경우 예외를 생각하지 못해 틀린 결과를 받았다.

import Foundation

func solution(_ storey:Int) -> Int {
    var result = 0
    var storey = "\(storey)".map{Int(String($0))!}

    for i in (0..<storey.count).reversed() {
        if storey[i] > 5 {  // 6, 7, 8, 9
            while storey[i] != 10 {
                storey[i] += 1
                result += 1
            }
            storey[i] = 0
            if i-1 >= 0 {
                storey[i-1] += 1
            }
        }
        else if storey[i] < 5 { // 0, 1, 2, 3, 4
            while storey[i] != 0 {
                storey[i] -= 1
                result += 1
            }
        }
        else {  // 5
            if i-1 >= 0 {
                if storey[i-1] >= 5 {
                    while storey[i] != 10 {
                        storey[i] += 1
                        result += 1
                    }
                }
                else {
                    while storey[i] != 0 {
                        storey[i] -= 1
                        result += 1
                    }
                }
            }
            else {
                result += 5
            }
        }
    }

    return result
}

✍️ 두번째 접근

만약 현재 자릿수에 있는 수가 5보다 커서 앞 자릿수의 수가 1 증가되어야하는데 그 수가 10이 되어버리면? 말이 어려우니 아래 그림을 보면 쉽게 이해될 것이다. 현재 층은 999층으로 3자리인데 계산하다보니 4자리로 계산되었다. 따라서, 필자는 다시 논리를 세웠다.

• 현재 층의 모든 자릿수에 있는 수가 0이 될 때까지 탐색한다. ex) 0000이 될 때까지
• 일의 자리에서부터 0이 아닌 위치를 찾는다. ex) 1230일 때 3의 index
• 찾은 위치에 있는 값이 5보다 큰 경우, 작은 경우, 같은 경우를 따져서 계산한다.
• 주의해야 할 점은 자릿수가 넘어갈 때 해당 위치의 앞에 있는 값을 +1 해줘야한다. 이때 해당 위치가 제일 앞에 있는 경우라면 자릿수를 늘려준다. ex) 800 -> 1000 즉, 3자리에서 4자리로 증가

import Foundation

func solution(_ storey:Int) -> Int {
    var result = 0
    var storey = "\(storey)".map{Int(String($0))!}

    while storey.filter{$0 == 0}.count != storey.count {    // storey가 모두 0일 떄까지
        // storey 맨 오른쪽부터 0이 아닌 위치를 찾는다
        var idx = storey.count - 1
        while storey[idx] == 0 && idx > 0 {
            idx -= 1
        }
        if storey[idx] > 5 {    // 찾은 수가 5보다 크다면
            result += 10-storey[idx]    // (10-찾은 수)를 result에 추가
            storey[idx] = 0 // 해당 위치를 계산하였으므로 0으로 설정
            if idx > 0 {    // 맨 왼쪽 자리가 아닐 경우
                storey[idx-1] += 1  // 찾은 수에서 자릿수가 넘어가서 0이 되었으니 찾은 수의 앞 자리 수 증가 
            }
            else {
                storey.insert(1, at: 0) // 맨 왼쪽 자리인 경우에서 자릿수가 넘어갔으니 1 추가
            }
        }
        else if storey[idx] < 5 {   // 찾은 수가 5보다 작다면
            result += storey[idx]   // result에 추가
            storey[idx] = 0 // 해당 위치를 계산하였으므로 0으로 설정
        }
        else {  // 찾은 수가 5라면 찾은 수의 앞 자리 수를 조건에 따라 비교해야한다
            if idx-1 > 0 {
                if storey[idx-1] >= 5 {
                    result += 10-storey[idx]
                    storey[idx] = 0
                    storey[idx-1] += 1                
                }
                else {
                    result += storey[idx]
                    storey[idx] = 0
                }
            }
            else {
                result += 5
                storey[idx] = 0
            }
        }
    }
    return result
}

우리는 심심치 않게 Extension을 활용한다. 필자는 문자열이 주어졌을 때, 해당 문자열의 각 요소에 접근하기 위해 사용한 경우가 있다.

import Foundation

extension String {
    subscript(_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

var name = "silverCastle"
print(name[0])

결과

s

그렇다면 "이 Extension은 도대체 무엇이고, 어떻게 사용할 수 있을까?"에 대해 알아보자.

익스텐션을 이용해 클래스, 구조체, 열거형 혹은 프로토콜 타입에 기능을 추가할 수 있다. 원본 코드를 몰라도 그 타입에 대한 기능을 확장할 수 있다.

라고 공식 문서에서 설명하고 있다. 또한, 이 Extension으로 다음과 같은 기능을 사용할 수 있다고 한다.

• 연산 인스턴스 프로퍼티와 연산 타입 프로퍼티의 추가
• 인스턴스 메서드와 타입 메서드의 추가
• 새로운 생성자 제공
• 서브스크립트 정의
• 중첩 타입의 선언과 사용
• 특정 프로토콜을 따르는 타입 만들기

한마디로 Extension은 확장한다. 무엇을? 특정 타입을!

✍️ Extension 문법

Extension은 extension 키워드를 사용하여 선언한다.

let beforeNum = 5
print(beforeNum)    // 5
print(beforeNum.ten)    // 10

extension Int {
    var ten: Int { return 10 }
}

let afterNum = 5
print(afterNum)  // 5
print(afterNum.ten)  // 10

위 예시는 특정 타입 즉, Int 타입을 확장한 것인데 예시와 같이 연산 프로퍼티를 사용할 수 있다. 연산 프로퍼티니까 ten은 상수 let이 아닌 변수 var 키워드를 사용해야겠다. 잘 모르겠다면? 또한, Extension을 정의하여 특정 타입에 새 기능을 추가하면 Extension을 사용하기 전인 beforeNum도 해당 기능을 사용할 수 있다. 즉, Extension의 위치는 상관없다.

연산 프로퍼티는 가능하지만 저장 프로퍼티와 프로퍼티 감시자는 사용할 수 없음을 알아두자.

extension Int {
    var ten = 10    // Extensions must not contain stored properties
}

✍️ 생성자(Initializer)

🔍 Class일 경우

Extension은 designated initializers와 deinitializers를 추가할 수 없다. 단, deinitializers는 추가할 수 있다.

class Person {
    var name: String = ""
    var age: Int = 0
}

extension Person {
    deinit {    // Deinitializers may only be declared within a class or actor
        print("deinit")
    }
    init {    // Designated initializer cannot be declared in an extension of 'Person'; did you mean this to be a convenience initializer?
        print("init")
    }
    convenience init(_: String) {    // 가능
        print("convenience init")
    }
}

🔍 Struct일 경우

사용자가 생성한 구조체에 대해 새로운 생성자를 정의하지 않았다면? Memberwise Initializer + 새로운 생성자

struct Person {
    var name: String
    var age: Int
}

extension Person {
    init(exName: String, exAge: Int) {
        self.name = exName
        self.age = exAge
    }
}

let person1 = Person(exName: "silverCastle", exAge: 26)
let person2 = Person(name: "silverCastle", age: 26)

구조체에 대해 생성자를 생성하지 않았으므로 기본으로 제공해주는 Memberwise Initializer + extension을 통해 생성한 생성자 둘 다 사용할 수 있다.

사용자가 생성한 구조체에 대해 새로운 생성자를 정의했다면? 새로운 생성자

struct Person {
    var name: String
    var age: Int
    init(exName: String, exAge: Int) {
        self.name = exName
        self.age = exAge
    }
}

let person1 = Person(exName: "silverCastle", exAge: 26)
let person2 = Person(name: "silverCastle", age: 26)    // Incorrect argument labels in call (have 'name:age:', expected 'exName:exAge:')

이번에는 구조체에 생성자를 정의하였으므로 person2와 같이 Memberwise Initializer를 사용할 수 없다.

Memberwise Initializer는 모든 프로퍼티를 초기화할 수 있게 해주고 자동으로 제공되는 생성자임을 알아두자.

✍️ 메서드(Method)

Extension을 이용해 존재하는 타입에 Instance Method와 Type Method를 추가할 수 있다.

extension Int {
    func printNum() {
        print("num: \(self)")
    }
}

100.printNum()    // num: 100

위의 예시는 인스턴스 메서드를 추가한 예이다.

extension Int {
    mutating func multiple() {
        self = self * 2
    }
}

var num = 10
num.multiple()
print(num)    // 20

위의 예시처럼 Mutating 키워드를 사용함으로써 자기 자신의 값을 바꿀 수 있다.

✍️ 중첩 타입 (Nested Type)

Extension을 이용해 존재하는 클래스, 구조체, 열거형에 중첩 타입을 추가할 수 있다.

extension Int {
    enum Kind {
        case negative, zero, positive
    }
    var kind: Kind {
        switch self {
        case 0:
            return .zero
        case let x where x > 0:
            return .positive
        default:
            return .negative
        }
    }
}

var num: Int = 10
print(num.kind)    // positive

공식 문서에 있는 위 예제는 Int에 중첩형 enum을 추가한 예제이다. Kind라고 불리는 열거형은 Int를 음수, 0, 양수로 표현한다고 한다.

✍️ 첫번째 접근

탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있다. 각 사람의 무게와 시소 중심으로부터 2m, 3m, 4m 경우를 따져가면서 문제를 접근하였지만 시간 초과가 발생하였다.

import Foundation

func solution(_ weights:[Int]) -> Int64 {
    var result: Int64 = 0
    for i in 0..<weights.count {
        for j in i+1..<weights.count {
            let first = weights[i]
            let second = weights[j]
            if first == second {
                result += 1
                continue
            }
            if first*2 == second*3 {
                result += 1
                continue
            }
            if first*2 == second*4 {
                result += 1
                continue
            }
            if first*3 == second*4 {
                result += 1
                continue
            }
            if first*3 == second*2 {
                result += 1
                continue
            }
            if first*4 == second*2 {
                result += 1
                continue
            }
            if first*4 == second*3 {
                result += 1
                continue
            }            
        }
    }
    return result
}

✍️ 두번째 접근

weights의 길이가 최대 100,000이므로 2중 for문을 사용하면 당연히 시간초과가 발생한다. 따라서, 1번의 for문을 사용해서 사람의 몸무게를 key, 해당 몸무게가 등장한 사람 수를 value로 판단함으로써 맵핑하였고 아래와 같은 논리를 적용하여 해결하였다. 느낀 점은 구현하는 데에 시간을 단축하기 위해 범위를 먼저 확인하고 곱셈, 나눗셈 연산할 때 조건을 잘 따지자..

import Foundation

func solution(_ weights:[Int]) -> Int64 {
    func calculate(_ num: Int) -> Int { // 같은 몸무게인 사람이 여러명일경우
        var sum = 0
        for i in 1..<num {
            sum += i
        }
        return sum
    }
    var result: Int = 0
    var arr: [Int] = Array(repeating: 0, count: 1000*4+1)
    var multiplier = [2,4,3]
    var divider = [1,3,2]
    for weight in weights {
        arr[weight] += 1
    }
    for i in 0..<arr.count {
        // 몸무게 범위를 벗어날 경우
        if i < 100 || i > 1000 {
            continue
        }
        // 존재하지 않는 몸무게일 경우
        if arr[i] == 0 {
            continue
        }
        // 같은 몸무게인 사람이 여러명일 경우
        if arr[i] > 1 {
            result += calculate(arr[i])
        }
        // 각 조건을 따진다.
        for j in 0..<3 {
            if (i % divider[j] != 0) {  // 이 조건을 지켜줘야 한다.
                continue
            }
            result += arr[i] * arr[(i / divider[j]) * multiplier[j]]
        }
    }
    return Int64(result)
}

✍️ 첫번째 접근

예전에 풀다가 시간 초과로 인해 해결하지 못한 문제인데 그때 당시에 접근은 이랬다.

• 철수의 카드 배열에 해당하는 모든 원소를 접근하면서 각 원소의 약수를 구한다.
• 이미 등장했던 약수라면 해당 약수의 개수를 count하면서 Dictionary에 저장한다.
• 이때, 대칭성을 이용해 1부터 제곱근까지의 범위를 적용하여 약수를 구할 수 있다.
• 마찬가지로 영희도 같은 논리를 적용한다.

이렇게 접근하였는데 각 원소에 해당하는 모든 약수를 구하다보니 시간 초과가 발생하였다.

import Foundation

func divisor(_ arr: [Int], _ d: inout [Int:Int])  {
    for i in arr {
        let end = Int(sqrt(Double(i)))
        for j in 1...end {
            if i % j == 0 {
                if d[j] == nil {
                    d.updateValue(1, forKey: j)
                }
                else {
                    d[j]! += 1
                }
                if d[i/j] == nil {
                    d.updateValue(1, forKey: i/j)
                }
                else {
                    d[i/j]! += 1
                }
            }
        }
    }
}


func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    let n = arrayA.count
    var d1: [Int:Int] = [:]
    var d2: [Int:Int] = [:]
    divisor(arrayA, &d1)
    divisor(arrayB, &d2)
    for i in d1 {
        if i.value == n && !d2.keys.contains(i.key) {
            return i.key
        }
    }
    for i in d2 {
        if i.value == n && !d1.keys.contains(i.key) {
            return i.key
        }
    }

    return 0
}

✍️ 두번째 접근

카드 배열에 있는 모든 원소의 약수를 구하지 말고, 카드 배열에 있는 모든 원소의 최대공약수를 구하는 방식으로 접근하여 해결하였다. 문제에서 가장 큰 양의 정수를 구한다고 하였으니 최대공약수를 구하는 것이 적합하다고 생각했기 때문.

import Foundation

// 최대공약수
func GCD(_ min: Int, _ max: Int) -> Int {
    let res = min % max
    if res == 0 {
        return max
    }
    return GCD(max,res)
}

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    // 최대공약수를 구하기 위해 수를 정렬
    let arr1 = arrayA.sorted{$0 < $1}   // 철수
    let arr2 = arrayB.sorted{$0 < $1}   // 영희
    let n = arr1.count
    if n == 1 { // 크기가 1이라면
        if arr1.first! == arr2.first! { // 중복된 원소일 수 있으므로
            return 0
        }        
        return arr1.first! > arr2.first! ? arr1.first! : arr2.first!    // 가장 큰 수를 리턴
    }
    // 각 배열의 최대공약수를 구함
    var gcd1 = GCD(arr1[0],arr1[1])
    var gcd2 = GCD(arr2[0],arr2[1])
    for i in 2..<n {
        gcd1 = GCD(gcd1,arr1[i])
        gcd2 = GCD(gcd2,arr2[i])
    }
    let cnt1 = arr2.filter{$0 % gcd1 == 0}.count    // 철수의 최대공약수가 영희의 카드 중에서 나눌 수 있는 개수
    let cnt2 = arr1.filter{$0 % gcd2 == 0}.count    // 영희의 최대공약수가 철수의 카드 중에서 나눌 수 있는 개수
    if cnt1 == 0 && cnt2 == 0 { // 주어진 조건을 만족하는 가장 최대공약수를 리턴
        return max(gcd1,gcd2)
    }
    if cnt1 == 0 {
        return gcd1
    }
    if cnt2 == 0 {
        return gcd2
    }

    return 0
}

이번 게시글은 피자에 대한 예시로 설명할 것이다. 피자를 친구랑 같이 먹고 싶은데, 피자 인치에 따라서 피자 조각이 달라지게 하고 싶다고 가정하자.

💡 연산 프로퍼티(Computed Properties)

let pizzaInInches: Int = 10

var numberOfSlices: Int = 6

위 프로퍼티는 단순히 값을 저장하고 접근할 수 있는 저장 프로퍼티(Stored Properties)이다. pizzaInInches는 피자 인치, numberOfSlices는 피자 조각 수라고 생각하면 된다.

만약, 우리가 피자 조각 수를 다르게 하고 싶다면 어떻게 해야 할까?

numberOfSlices = 4

당연하게도 위와 같이 작성한다면 4조각으로 변경할 수 있다. 하지만, 피자를 14인치로 하고 피자 조각 수를 10조각으로 하고 싶다면? 일일이 코드를 작성할 것인가? 이것을 automatical하게 업데이트할 수는 없을까? 여기서 나온 개념이 연산 프로퍼티(Computed Properties)이다.

✍️ getter

우리의 목표는 14인치 피자와 그에 맞게 10조각으로 나누는 것이다.

let pizzaInInches: Int = 14

var numberOfSlices: Int {
    return pizzaInInches - 4
}

print(numberOfSlices)

결과

10

이 property에게 값을 돌려주기 위해 return를 작성한다. 이것은 마치 함수처럼 보인다.. 연산 프로퍼티를 사용하기 위해서는 알아야할 점이 있다.

• let이 아니라 var를 사용하자. 만약 상수인 let를 사용한다면 값을 바꿀 수 없고 연산 프로퍼티에 맞지 않는다!
• 자료형을 명시해주자. 위와 같이 Int 타입이라고 명시하지 않고 추론을 한다면 값을 계산할 때 혼란을 줄 수 있다!

자 그럼 피자 인치를 바꿨을 때 automatical하게 바뀌는지 확인해보면?

let pizzaInInches: Int = 12

var numberOfSlices: Int {
    return pizzaInInches - 4
}

print(numberOfSlices)

결과

8

잘 바뀌는 걸 확인할 수 있다.

연산 프로퍼티는 우리가 많은 작업을 수행할 때 일어날 수 있는 잠재적 에러를 줄이는 데에 효과적이다.

func calcPizaaSlices() {
    numberOfSlices = pizzaInInches - 4
}

calcPizaaSlices()

물론 위와 같이 메서드를 생성한다면 같은 동작을 수행하겠지만..! input도 없고 output도 없고, block 안에 있는 코드만 실행하는 거라면 굳이 더 많은 코드를 작성하지 않고 연산 프로퍼티를 쓰는 것이 적합하겠다.

우리가 작성한 것은 get을 명시하지만 않았지 short version의 getter라고 생각하면 된다.

var numberOfSlices: Int {
    get {
        return pizzaInInches - 4
    }
}

명시하려면 위와 같이 작성하면 된다.

✍️ setter

우리가 property의 값을 get할 때마다 즉, 가져올 때마다 실행되는 코드인 getter에 대해 배웠다. 이제는 property가 새로운 값으로 set될 때마다 즉, 설정될 때마다 실행되는 코드인 setter에 대해 알아보자.

let pizzaInInches: Int = 12

var numberOfSlices: Int {
    get {
        return pizzaInInches - 4
    }
    set {
        print("numberOfSlices의 새로운 값: \(newValue)")
    }
}

numberOfSlices = 12

결과

numberOfSlices의 새로운 값: 12

newValue는 우리가 따로 생성해주지 않아도 자동 생성된다. 새로운 값으로 업데이트될 때 그 즉시 set이 실행된다.

만약, 저기에서 setter를 없애버리면 어떻게 될까?

Cannot assign to value: 'numberOfSlices' is a get-only property

에러를 내뱉게 된다. why? 새로운 값에 대해 set을 할 수 없기 때문! 오직 get-only만 되는 것이다.

💡 프로퍼티 감시자(Property Observers)

getter를 사용해서 value를 계산하고 싶지 않고 단지 value가 변화할 때만 관찰하고 싶을 때 사용하는 것이 프로퍼티 감시자(Property Observers)이다. property의 값이 바뀔 때 code를 트리거한다. 예를 들어, 피자 인치가 33인치라면 말도 안 되는 크기이기 때문에 최대 18인치를 넘어가게끔 하고 싶지 않다. 이때 우리는 프로퍼티 감시자를 사용하면 된다.

var pizzaInInches: Int = 10 {
    willSet {
    }
    didSet {
        if pizzaInInches >= 18 {
            print("pizzaInInches가 너무 큽니다.")
            pizzaInInches = 18
        }
    }
}

pizzaInInches = 33
print(pizzaInInches)

결과

pizzaInInches가 너무 큽니다.
18

observer 중 하나는 willSet이라고 부르고 다른 하나는 didSet이라고 부른다. pizzaInInches의 값이 바뀌기 바로 직전에 willSet이 트리거되고 값이 바뀐다. 그 후 didSet이 실행된다. 순서: willSet 트리거 -> 값 변화 -> didSet 트리거 프로퍼티 감시자를 사용하기 위해서는 연산 프로퍼티와 마찬가지로 let 대신 var를 사용하자.

willSet에서는 newValue, didSet에서는 oldValue를 사용할 수 있다.

var pizzaInInches: Int = 10 {
    willSet {
        print("pizzaInInches: \(pizzaInInches)")
        print("새로운 값: \(newValue)")
    }
    didSet {
        print("pizzaInInches: \(pizzaInInches)")
        print("예전 값: \(oldValue)")
    }
}

pizzaInInches = 15

결과

pizzaInInches: 10    // 1
새로운 값: 15    // 2
pizzaInInches: 15    // 3
예전 값: 10    // 4

1에서는 실행 순서가 값 변화 이전에 willSet이 트리거되었기 때문에 여전히 10이다. 2에서는 newValue는 새로 바뀐 값이므로 15이다. 3에서는 값 변화 이후에 didSet이 트리거되었기 때문에 15이다. 4에서는 oldValue는 바뀌기 이전 값이므로 10이다.

✍️ 첫번째 접근

조건이 까다로운 BFS문제이다. 문제에서 주어진대로 조건을 생각해서 구현하면 되는데 필자는

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

해당 조건에 대해 BFS를 돌 때, 아래와 같이 순서를 상 -> 좌 -> 하 -> 우로 결정하여 BFS를 돌았다.

let dx = [-1,0,1,0]
let dy = [0,-1,0,1]

하지만 이 경우 예제 입력 4에서 잘못된 출력이 나온다. 그 이유는 아래 그림에서 (0,2)에서 (0,4)로 가야 올바른 출력이 나오는데 (1,1)로 가기 때문이다.

✍️ 두번째 접근

약간의 힌트를 받아 1번의 BFS로 상 -> 좌 -> 하 -> 우의 순서로만 도는 것이 아닌, BFS를 돌면서 먹을 수 있는 물고기를 모두 저장하고 저장한 물고기를 조건에 맞게 sort하였다. 현재 상어 위치를 정렬된 맨 앞 물고기와 바꾸고 다시 BFS를 돌면서 문제를 해결하였다.

import Foundation

func findShark() {
    for i in 0..<N {
        for j in 0..<N {
            if arr[i][j] == 9 {
                arr[i][j] = 0
                now = (i,j)
            }
        }
    }
}

let dx = [-1,0,1,0]
let dy = [0,-1,0,1]
let N = Int(readLine()!)!
var arr: [[Int]] = []
var shark = 2   // 가장 처음 상어의 크기
var cnt = 0
var result = 0
for _ in 0..<N {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
var queue: [(x: Int, y: Int)] = []
var size = Array(repeating: Array(repeating: 0, count: N), count: N)
var fish = [(Int, Int, Int)]() // 먹힌 물고기의 (x 좌표, y 좌표, 아기 상어와의 거리)들을 저장할 배열
var now = (0,0)
findShark()
func bfs() {
    queue.append((now.0,now.1))
    size[now.0][now.1] = 1
    while !queue.isEmpty {
        let cur = queue.first!
        queue.removeFirst()
        if arr.flatMap({$0}).filter({$0 != 0 && $0 < shark}).count < 1 {   // 잡아먹을 수 있는 물고기가 없으므로
            break
        }
        for dir in 0..<4 {
            let nx = cur.x + dx[dir]
            let ny = cur.y + dy[dir]
            if nx < 0 || nx >= N || ny < 0 || ny >= N {
                continue
            }
            if size[nx][ny] != 0 {
                continue
            }
            if arr[nx][ny] > shark {    // 자신보다 큰 크기는 지나갈 수 없으므로
                continue
            }
            if arr[nx][ny] != 0 && arr[nx][ny] < shark {    // 자신보다 작으면 먹을 수 있으므로
                size[nx][ny] = size[cur.x][cur.y] + 1
                fish.append((nx, ny, size[nx][ny]))
                continue
            }
            queue.append((nx,ny))
            size[nx][ny] = size[cur.x][cur.y] + 1
        }
    }
}


while true {
    fish = [(Int, Int, Int)]()
    size = Array(repeating: Array(repeating: 0, count: N), count: N)
    queue = []
    bfs()
    if fish.isEmpty { print(result); break }
    cnt += 1
    fish = fish.sorted {
        if $0.2 <= $1.2 {
            if $0.0 == $1.0 { return $0.1 < $1.1 }
            else { return $0.0 < $1.0 }
        }
        else { return false }
    }
    arr[fish[0].0][fish[0].1] = 0
    result += size[fish[0].0][fish[0].1] - 1
    if shark == cnt {
        shark += 1
        cnt = 0
    }
    now = (fish[0].0, fish[0].1) // 먹은 물고기와 현재 상어 위치 교체
}

✍️ 첫번째 접근

이 문제는 전형적인 Parametric Search 유형 문제이다. 이분 탐색은 주어진 값 중에서 원하는 값을 찾는 것이 목적이라면, Parametric Search는 주어진 범위 내에서 원하는 조건 중 가장 최적화된 값을 찾는 것이 목적이다. 문제에서 요구하는 것이 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 찾는 것이 목적이니 Parametric Search로 풀 수 있다고 생각하였다. 예제를 통한 필자의 논리는 이러하였지만 틀린 결과를 받게 되었다.

import Foundation

let n = Int(readLine()!)!
let arr =  readLine()!.split(separator: " ").map{Int(String($0))!}.sorted()
var start = 0, end = n-1
var sum = 0x3f3f3f3f
var answer: (first: Int, second: Int) = (0,0)
while start < end {
    if abs(arr[start] + arr[end]) < sum {
        sum = arr[start] + arr[end]
        answer.first = arr[start]
        answer.second = arr[end]
        start += 1
    }
    else {
        end -= 1
    }
}
print("\(answer.first) \(answer.second)")

✍️ 두번째 접근

예제는 운좋게도 통과하였지만 sum을 기준으로 start와 end의 값을 바꾸는 것이 아니라 start와 end에 있는 특성값의 절댓값을 기준으로 start, end의 값을 바꿔야 함을 다음 반례를 통해 알게 되었다.

5
1 2 3 4 5

또한, 특성값의 범위를 생각하면 -1,000,000,000 이상 1,000,000,000 이하이므로 sum의 초기값을 0x3f3f3f3f가 아닌 더 큰 수로 지정해주어 해결할 수 있었다.

import Foundation

let n = Int(readLine()!)!
let arr =  readLine()!.split(separator: " ").map{Int(String($0))!}.sorted() // 용액의 특성값을 정렬하며 저장
var start = 0, end = n-1    // 시작과 끝을 지정
var sum = UInt.max  // 용액의 범위를 생각하여 최댓값 설정
var answer: (first: Int, second: Int) = (0,0)
while start < end {
    if abs(arr[start] + arr[end]) < sum {
        sum = UInt(abs(arr[start] + arr[end]))  // sum 갱신
        // 출력해야 하는 답을 저장
        answer.first = arr[start]
        answer.second = arr[end]
    }
    if abs(arr[start]) > abs(arr[end]) {    // 절댓값을 기준으로 하여 start 위치에 존재하는 특성값이 더 크다면 start를 오른쪽으로 한칸 이동
        start += 1
    }
    else {  // 반대라면 end를 왼쪽으로 한칸 이동
        end -= 1
    }
}
print("\(answer.first) \(answer.second)")

✍️ 첫번째 접근

visited라는 Array에 입력으로 주어진 기지국이 도달할 수 있는 아파트 번호를 true로 저장한다. 아파트는 1번부터 n번까지 있으므로 while문을 돌면서 해당 아파트가 이미 도달할 수 있다면 인덱스를 하나 증가시킨다. 그렇지 않다면, 한개의 기지국은 양방향으로 w만큼의 아파트에 도달할 수 있으므로 해당 범위만큼 visited 배열을 true로 만들면서 answer를 하나씩 추가한다. 하지만, 효율성 테스트에서 시간 초과가 발생하였다.

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0
    var visited: [Bool] = Array(repeating: false, count: n+1) // 전파 전달 여부
    for s in stations {
        for i in s-w...s+w {
            if i < 1 || i > n {
                continue
            }
            visited[i] = true
        }
    }
    // start부터 end까지 도달하지 않은 아파트가 있다면 기지국 설치하는 메서드    
    func check(_ start: Int, _ end: Int) {
        if visited[start...end].filter{$0 == false}.count > 0 {
            for j in start...end {
                visited[j] = true
            }
            answer += 1
        }
    }

    var idx = 1
    while idx <= n {
        if visited[idx] {   // 이미 도달한 아파트이면 다음 아파트로 이동
            idx += 1
            continue
        }
        else {  // check 메서드에서 for문 범위 예외 처리를 위해 if문으로 범위 처리
            idx += w    // idx에서 양방향으로 w만큼 전파가 도달할 수 있으므로
            if idx-w < 1 {
                check(1,idx+w)
            }
            else if idx+w > n {
                check(idx-w,n)
            }
            else {
                check(idx-w,idx+w)                
            }
        }
    }

    return answer
}

✍️ 두번째 접근

아래 해설을 참고하여 해결할 수 있었다. https://school.programmers.co.kr/questions/27785 n이 최대 200,000,000으로 충분히 크고 한번에 할 수 있는 연산을 생각해내지 못했기 때문에 시간 초과가 발생한 거 같았다. 문제를 단순화하는 것을 항상 염두에 두어야겠다.

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0
    var start = 1   // 1번 아파트부터 시작
    var end = 0
    for s in stations {
        end = s-w-1 // 현재의 기지국에서 왼쪽 방향으로 도달하지 못한 아파트 위치
        if end >= start {   // 도달하지 못한 아프트가 존재
            let length = end-start+1    // 길이 저장
            if length <= 2*w+1 {    // 한개의 기지국으로 커버할 수 있을 경우
                answer += 1
            }
            else {
                answer += Int(ceil(Double(length)/Double((2*w+1))))
            }
        }
        start = s+w+1   // 현재의 기지국에서 오른쪽 방향으로 도달하지 못한 아파트 위치로 갱신
    }
    // n이 start보다 크거나 같다면, 아직 도달하지 못한 아파트가 존재한다는 의미
    if n >= start {
        let length = n-start+1
        if length <= 2*w+1 {
            answer += 1
        }
        else {
            answer += Int(ceil(Double(length)/Double((2*w+1))))
        }        
    }
    return answer
}

✍️ 첫번째 접근

입력으로 들어온 [2, 1, 1, 2, 3, 1, 2, 3, 1]을 하나의 문자열로 만들고 해당 문자열에서 "1231"이 있으면 "1231" 대신 ""을 넣고 answer를 하나씩 추가하는 방식으로 처리하였다. [2, 1, 1, 2, 3, 1, 2, 3, 1] -> "211231231" -> "21231" -> "2" 이렇게 말이다. 하지만 시간 초과가 발생하였다.

import Foundation

extension String {
    func replacingFirstOccurrence(of target: String, with replacement: String) -> String {
        guard let range = self.range(of: target) else { return self }
        return self.replacingCharacters(in: range, with: replacement)
    }
}

func solution(_ ingredient:[Int]) -> Int {
    var answer = 0
    var ingredient: String = ingredient.map{String($0)}.joined()
    while true {
        if !ingredient.contains("1231") {
            break
        }
        ingredient = ingredient.replacingFirstOccurrence(of: "1231", with: "")
        answer += 1
    }
    return answer
}

✍️ 두번째 접근

첫번째 접근에서 특정 문자열을 대치할 때 ingredient의 크기만큼 비교하기 때문에 시간 초과가 발생한 거 같았다. stack이라는 Array를 선언하고 ingredient의 원소 하나씩 저장하면서 stack의 크기가 4이상일 경우, stack의 맨 뒤에 있는 4개의 값이 "1231"가 동일하다면 그 4개를 없애고 answer를 하나씩 추가하는 방식을 취했다. 결론적으로 첫번째 접근은 ingredient의 길이만큼 "1231"이 있는지 비교하는 것에 반해, 두번째 접근은 stack의 맨 뒤에 있는 4개의 값이 "1231"인지 비교하면 되기 때문에 시간 초과가 발생하지 않은 것 같다.

import Foundation

func solution(_ ingredient:[Int]) -> Int {
    var answer = 0
    var stack: [String] = []
    var ingredient = ingredient.map{String($0)}
    for i in ingredient {
        stack.append(i)
        while stack.count >= 4 {
            if stack[stack.count-4...stack.count-1].joined() == "1231" {
                stack.removeLast()
                stack.removeLast()
                stack.removeLast()
                stack.removeLast()
                answer += 1
            }
            else {
                break
            }
        }
    }
    return answer
}

✍️ 첫번째 접근

필자가 처음 작성한 코드르 보면서 설명하기 애매하게 논리가 부족함을 느껴 첫번째 작성한 코드는 생략하고 테스트 케이스를 작성한다.

Text Case

[3, 5, 1, 2, 6, 4]
2

[2, 1, 6, 7, 5, 8, 4, 9, 3, 10]
10

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9]
10

[1]
1

[2, 1, 3, 5, 4]
5

[2, 1, 6, 4, 3, 5]
3

✍️ 두번째 접근

기존 컨테이너 벨트는 1부터 상자 개수까지의 Array, 보조 컨테이너 벨트는 빈 Array 선언한다. 보조 컨테이너 벨트가 비어있다면 기존 컨테이너의 앞에 있는 상자부터 택배 기사님이 원하는 상자 번호의 이전까지의 상자를 보조 컨테이너에 넣는다. 기존 컨테이너 벨트 앞에 있는 상자가 택배 기사님이 원하는 상자 or 보조 컨테이너 벨트 마지막에 있는 상자가 택배 기사님이 원하는 상자일 경우 answer를 하나씩 증가한다. 기존 컨테이너 벨트에 있는 상자라면 인덱스를 하나 증가해주고, 보조 컨테이너 벨트에 있는 상자라면 removeLast()를 해준다. 만약 원하는 상자가 없을 때 기존 벨트에 있는 상자가 택배 기사님이 원하는 상자보다 값이 작을 경우 보조 벨트에 더 넣을 수 있으므로 더 넣고 기존 컨테이너 벨트에 있는 상자가 원하는 상자인지 비교한다. 그럼에도 원하는 상자가 없다면 더이상 찾을 수 없으므로 종료하는 방식으로 문제를 해결하였다.

import Foundation

func solution(_ order:[Int]) -> Int {
    if order.count == 1 {   // order의 길이가 1이라면 택배 기사님이 원하는 순서로 바로 실을 수 있기 때문
        return 1
    }
    var answer = 0
    let n = order.count // 상자의 개수
    var arr = Array(1...n)  // 기존 컨테이너 벨트
    var support: [Int] = [] // 보조 컨테이너 벨트
    var idx = 0 // 기존의 컨테이너 벨트에 대한 인덱스
    for o in order {
        // 보조 컨테이너 벨트에 삽입
        if support.isEmpty {
            if o-2 >= idx && idx < n {
                support = Array(arr[idx...o-2])
                idx = o-1
            }
        }
        // 기존의 컨테이너 벨트에 있는 상자가 택배 기사님이 원하는 상자일 경우
        if idx < n && arr[idx] == o {
            answer += 1
            idx += 1
        }
        // 보조 컨테이너 벨트에 있는 마지막 상자가 택배 기사님이 원하는 상자일 경우
        else if !support.isEmpty && support.last! == o {
            answer += 1
            support.removeLast()    // 벨트에 있는 마지막 상자를 택배에 실었으니 뺀다.
        }
        else {
            // 기존 벨트에 있는 상자가 택배 기사님이 원하는 상자보다 값이 작을 경우 보조 벨트에 더 넣을 수 있으므로
            if idx < n && arr[idx] < o {
                while idx < n && arr[idx] < o {
                    support.append(arr[idx])
                    idx += 1
                }
                // 보조 벨트에 넣었으면 기존 벨트에 있는 상자가 원하는 상자인지 비교
                if idx < n && arr[idx] == o {
                    answer += 1
                    idx += 1
                }
            }
            // 기존 벨트와 보조 벨트 모두에서 원하는 상자가 없을 경우
            else {
                break                
            }
        }
    }

    return answer
}

잡담 최근 코딩테스트를 2번 참가하였는데 모두 C++로 봐야해서 오랜만에 문법 공부를 했는데 나름 기억이 새록새록 났다. 코딩테스트가 C++과 Swift 모두 지원해준다면 다익스트라, 플로이드 등 문제가 나왔을 때는 C++로 풀고 그 외 문제는 Swift로 풀어야겠다는 생각을 하였다.

✍️ 첫번째 접근

롤케이크를 잘랐을 때 나오는 두 개의 롤케이크가 같은 토핑 종류의 수가 나오게끔 자르면 된다. 철수의 롤케이크에 대한 정보를 갖고 있는 배열 arr1과 동생의 롤케이크에 대한 정보를 갖고 있는 배열 arr2를 선언했다. 롤케이크를 자를 수 있는 인덱스를 돌면서 arr1과 arr2의 토핑의 종류의 수가 같은지 판단하였는데 시간 초과가 발생하였다. 매번 arr1, arr2 배열을 초기화하고 topping의 길이가 최대 1,000,000이기 때문에 2중 for문으로 인해 발생한 것이라고 판단하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    let maxValue = topping.max()!   // 배열의 최대 크기를 지정하기 위해
    var arr1 = Array(repeating: 0, count : maxValue+1)
    var arr2 = Array(repeating: 0, count : maxValue+1)
    for i in 0..<topping.count-1 {
        arr1 = Array(repeating: 0, count : maxValue+1)
        arr2 = Array(repeating: 0, count : maxValue+1)
        for j in 0...i {
            arr1[topping[j]] += 1
        }
        for j in i+1..<topping.count {
            arr2[topping[j]] += 1
        }
        if arr1.filter{$0 == 0}.count == arr2.filter{$0 == 0}.count {
            answer += 1
        }        
    }

    return answer
}

✍️ 두번째 접근

Array로 선언하지 않고 Set으로 선언하여 접근했다. 하지만, 이번에도 시간 초과가 발생하였다. for문은 비록 한개를 사용하였지만, 그 안에서 Array를 Set으로 계속해서 형변환하였고 매번 인덱스가 증가할 때마다 새로 구하기 때문에 발생한 것이라고 판단하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    for i in 0..<topping.count-1 {
        var s1: Set<Int> = []
        var s2: Set<Int> = []
        s1 = Set(topping[0...i])
        s2 = Set(topping[i+1..<topping.count])
        if s1.count == s2.count {
            answer += 1
        }
    }

    return answer
}

✍️ 세번째 접근

철수는 빈 Set인 s1에서 시작하고 동생은 모든 토핑에 대한 Set인 s2에서 시작한다. 롤케이크를 자를 수 있는 인덱스에 대한 for문을 돌기 전에 미리 각 토핑이 몇개 있는지에 대한 idxArr 배열을 선언하였다. 이제 롤케이크를 자를 수 있는 인덱스를 돌면서 s1에 토핑을 하나씩 추가하고, s2에는 idxArr 배열과 비교하여 해당 토핑이 idxArr 배열 값에 0보다 작거나 같다면 s2에서 해당 토핑을 삭제한다. s1의 크기와 s2의 크기가 같으면 answer를 하나씩 증가하여 문제를 해결하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    if topping.count == 1 {
        return 0
    }
    var answer = 0
    var s1: Set<Int> = []   // 철수
    var s2: Set<Int> = Set(topping)   // 동생
    let maxValue = topping.max()!   // 배열의 최대 크기를 지정하기 위해
    var idxArr = Array(repeating: 0, count: maxValue+5)
    for i in 0..<topping.count {
        idxArr[topping[i]] += 1
    }
    for i in 0..<topping.count-1 {
        s1.insert(topping[i])   // 철수는 토핑 하나 증가        
        idxArr[topping[i]] -= 1 // 해당 토핑의 개수 하나 감소
        if idxArr[topping[i]] <= 0 {    // 해당 토핑의 개수가 0 이하이면, s2에는 해당 토핑이 존재하면 안된다.
            s2.remove(topping[i])    // 동생은 토핑 하나 감소
        }
        if s1.count == s2.count {    // 토핑의 가짓수가 같으면 answer 증가
            answer += 1
        }
    }

    return answer
}

✍️ 첫번째 접근

예제 입력을 통해 문제를 해석하면 아래 그림을 만들 수 있다. 예시 하나를 든다면, 1번 지점부터 2번 지점까지 거리는 1이다. 완전탐색으로 i지점부터 j지점까지 시계방향의 경로와 반시계반향의 경로를 구한 뒤, 그 둘 중에 최솟값을 answer에 넣는다. 모든 지점에 대하여 탐색을 끝냈으면 answer에 있는 값 중 최댓값을 출력하게끔 하였다. 논리에는 문제가 없다고 생각했지만 N이 최대 50000이므로 O(n^2)에다가 그 안에 합을 계산하기 위한 2개의 while문이 존재하므로 시간 초과가 발생하였다.

import Foundation

let n = Int(readLine()!)!
var arr: [Int] = []
for _ in 0..<n {
    let num = Int(readLine()!)!
    arr.append(num)
}
var answer: [Int] = []
for i in 0..<n {
    for j in i+1..<n {
        var forwardSum = arr[i]
        var backwardSum = 0
        var idx = i+1
        while idx < j {
            forwardSum += arr[idx]
            idx += 1
        }
        var cnt = n-j+i
        idx = i-1
        while cnt > 0 {
            if idx < 0 {
                idx = n-1
            }
            backwardSum += arr[idx]
            cnt -= 1
            idx -= 1
        }
        answer.append(min(forwardSum,backwardSum))
    }
}
print(answer.max()!)

✍️ 두번째 접근

먼저 i번째 지점을 1부터 N까지의 지점으로 정하지 않고 그 절반까지만 돌면 된다고 판단하였다. 그 이유는 시계방향의 경로와 반시계반향의 관계를 생각하면 된다. 또한, 경로를 매번 처음부터 구하는 경우를 누적합을 사용하여 구현하였다. idx는 인덱스, arr은 입력으로 받은 값들을 저장한 배열, sum은 누적합을 저장한 배열이다. 1번 지점부터 2번 지점까지의 경로를 생각해보자. 1번 지점부터 2번 지점까지 시계 방향의 경로는 (1번 지점부터 2번 지점까지의 누적합) - (1번 지점까지의 누적합)이다. 반시계 방향의 경로는 (1번 지점부터 5번 지점까지의 누적합) - (1번 지점부터 2번 지점까지의 누적합)이다. 즉, 시계 방향은 sum[1] - sum[0]이고 반시계 방향은 sum[5] - sum[1]이다. 이하 동문이다. 이해하기 더 쉽게 i번째 지점을 2로 해보자. 2번 지점부터 3번 지점까지의 경로를 생각해보자. 2번 지점부터 3번 지점까지 시계 방향의 경로는 (1번 지점부터 3번 지점까지의 누적합) - (2번 지점부터 1번 지점까지의 누적합)이다. 반시계 방향은 (1번 지점부터 5번 지점까지의 누적합) - (1번 지점부터 3번 지점까지의 누적합) + (1번 지점부터 2번 지점까지의 누적합)이다. 반시계 방향일 경우가 조금 까다로운데 수식 옆에 그림을 보면 그나마 이해하기 빠를 것이다. 이렇게 하여 다음과 같은 일반항을 만들 수 있다.

시계 방향: sum[j-1]-sum[i-1]
반시계 방향: sum[n]-sum[j-1]+sum[i-1]

도출해낸 일반항으로 해결할 수 있었다. 얻은 점은, N의 범위를 보고 나서 시간 초과를 미리 예상해야한다는 것이고 같은 연산을 피하자는 것이다.

import Foundation

let n = Int(readLine()!)!
var arr: [Int] = Array(repeating: 0, count: n+1)
var sum: [Int] = Array(repeating: 0, count: n+1)
var answer = 0
for i in 1...n {
    arr[i] = Int(readLine()!)!
    sum[i] = sum[i-1]+arr[i]
}
for i in 1...n/2+1 {
    if i+1 > n {    // i+1이 n보다 크면 런타임 에러 발생하므로
        break
    }
    for j in i+1...n {
        answer = max(answer, min(sum[j-1]-sum[i-1],sum[n]-sum[j-1]+sum[i-1]))
    }
}
print(answer)

✍️ 첫번째 접근

문제를 봤을 때, 이해하는데 시간이 오래 걸렸다. 내가 독해력이 부족한 것인가 생각까지 했다. 예시에 대한 그림은 아래와 같다. 따라서, 예제에서의 입력으로 인한 출력으로 2가 나오는 것이다. 필자는 각 좌표를 쉽게 사용하기 위해 구조체를 선언하였고 목초지를 잇는 길에 대한 각각의 좌표를 Dictionary 타입으로 저장하였다. 예를 들어 입력으로 3 3 3 2과 3 3 2 3이 들어왔다면 [3,3] key에 [[3,2], [2,3]]을 value로 저장한다. 소의 좌표를 저장한 배열을 2중 for문 돌려 길을 건널 수 있는지 없는지를 판단하여 길을 건너야지만 만날 수 있는 쌍의 개수를 출력하려 했다. 하지만 틀리게 되었는데 길이 있는 좌표에 소가 길을 건널 수 있다는 의미가 무조건 길을 건너야지만 건널 수 있다는 의미가 아니기 때문이다. 즉, 논리가 부족하였다.

import Foundation

struct Point: Hashable {
    var x: Int
    var y: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var arr: [Point: Set<Point>] = [:]
var cows: [Point] = []
var cnt = 0
for _ in 0..<input[2] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x1 = point[0], y1 = point[1], x2 = point[2], y2 = point[3]
    if arr[Point(x: x1, y: y1)] == nil {
        arr.updateValue([Point(x: x1, y: y1)], forKey: Point(x: x1, y: y1))
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    else {
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    if arr[Point(x: x2, y: y2)] == nil {
        arr.updateValue([Point(x: x2, y: y2)], forKey: Point(x: x2, y: y2))
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
    else {
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
}
for _ in 0..<input[1] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    cows.append(Point(x: point[0], y: point[1]))
}
for i in cows {
    for j in cows {
        if arr[i] == nil || arr[j] == nil {
            cnt += 1
            continue
        }
        if !arr[i]!.contains(j) {
            cnt += 1
        }
    }
}
print(cnt)

✍️ 두번째 접근

소의 좌표를 저장한 배열을 2중 for문 돌 때, BFS를 돌려 A라는 소에서 출발하였을 때 길을 사용하지 않고 B라는 소를 만날 수 없다면 즉, A, B 소의 한쌍은 길을 건너야하지만 만날 수 있으면 그 한쌍이 우리가 원하는 한쌍이라고 판단하였다. 각 쌍에 대하여 반복문을 돌 때, visited를 초기화해줘야함을 잊어서는 안된다. 이렇게 구현하여 문제를 해결하였다.

import Foundation

let dx = [1,0,-1,0]
let dy = [0,1,0,-1]

func BFS(_ i: Int, _ j: Int) {
    var queue: [Point] = []
    queue.append(Point(x: i, y: j))
    visited[i][j] = true
    while !queue.isEmpty {
        let cur = queue.first!
        queue.removeFirst()
        for dir in 0..<4 {
            let nx = cur.x + dx[dir]
            let ny = cur.y + dy[dir]
            if arr[Point(x: cur.x, y: cur.y)] != nil && arr[Point(x: cur.x, y: cur.y)]!.contains(Point(x: nx, y: ny)) {
                continue
            }
            if nx <= 0 || nx > input[0] || ny <= 0 || ny > input[0] {
                continue
            }
            if visited[nx][ny] == true {
                continue
            }
            queue.append(Point(x: nx, y: ny))
            visited[nx][ny] = true
        }
    }
}

struct Point: Hashable {
    var x: Int
    var y: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var arr: [Point: Set<Point>] = [:]
var cows: [Point] = []
var cnt = 0
for _ in 0..<input[2] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    let x1 = point[0], y1 = point[1], x2 = point[2], y2 = point[3]
    if arr[Point(x: x1, y: y1)] == nil {
        arr.updateValue([Point(x: x2, y: y2)], forKey: Point(x: x1, y: y1))
    }
    else {
        arr[Point(x: x1, y: y1)]?.insert(Point(x: x2, y: y2))
    }
    if arr[Point(x: x2, y: y2)] == nil {
        arr.updateValue([Point(x: x1, y: y1)], forKey: Point(x: x2, y: y2))
    }
    else {
        arr[Point(x: x2, y: y2)]?.insert(Point(x: x1, y: y1))
    }
}
for _ in 0..<input[1] {
    let point = readLine()!.split(separator: " ").map { Int(String($0))! }
    cows.append(Point(x: point[0], y: point[1]))
}

var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: input[0]+1), count: input[0]+1)
for i in 0..<cows.count {
    visited = Array(repeating: Array(repeating: false, count: input[0]+1), count: input[0]+1)
    BFS(cows[i].x,cows[i].y)
    for j in i+1..<cows.count {
        if visited[cows[j].x][cows[j].y] == false {
            cnt += 1
        }
    }
}
print(cnt)

✍️ 첫번째 접근

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족하는 부분 바이토닉 수열이면서 그 중 가장 긴 수열을 구하면 된다. LIS를 구하는 방식 중 2중 for문을 사용하는 방법과 이분탐색을 통해 구하는 방법이 있는데 첫번째 방법은 시간 복잡도가 O(n^2)이다. 따라서, 시간초과를 피하기 위해 시간 복잡도가 O(logn)인 두번째 방법을 택하였다. 입력으로 받은 수열에 대해서,

• 앞->뒤 방향으로 LIS 구하기(why? 정방향에서 봤을 때 Sk를 기준으로 증가하므로)
• 뒤->앞 방향으로 LIS 구하기(why? 역방향에서 봤을 때 Sk를 기준으로 증가하므로)

먼저 위와 같은 논리를 계획하였다.

• 1번) 앞->뒤 방향으로 LIS구하고 LIS에 값이 들어가는 마지막 인덱스로부터 뒤->앞 방향으로 LIS를 구해 이 둘의 LIS합이 곧 부분 바이토닉 수열의 합이다.
• 2번) 뒤->앞 방향으로 LIS구하고 LIS에 값이 들어가는 마지막 인덱스로부터 앞->뒤 방향으로 LIS를 구해 이 둘의 LIS합이 곧 부분 바이토닉 수열의 합이다.

둘 중 큰 값이 길이가 가장 긴 바이토닉 부분 수열의 길이라고 판단하여 구현하였지만 틀렸다는 결과를 받았다.

import Foundation

func binary_search(_ LIS: [Int], _ left: Int, _ right: Int, _ target: Int) -> Int {
    var left = left
    var right = right
    var mid = 0
    while left < right {
        mid = (left+right)/2
        if LIS[mid] < target {
            left = mid + 1
        }
        else {
            right = mid
        }
    }
    return right
}

func findLIS(_ arr: [Int]) -> (Int,Int) {
    var LIS = Array(repeating: 0, count: arr.count+1)
    var i = 1, j = 0
    var maxI = 0
    LIS[0] = arr[0]
    while i < arr.count {
        if arr[i-1] == arr[i] {
            maxI = i
        }
        if LIS[j] < arr[i] {
            j += 1
            LIS[j] = arr[i]
            maxI = i
        }
        else {
            let index = binary_search(LIS, 0, j, arr[i])
            LIS[index] = arr[i]
        }
        i += 1
    }
    return (j+1,maxI)
}

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var answer1 = 0, answer2 = 0
// 앞에서부터 시작하는 LIS -> 뒤에서부터 시작하는 LIS
var (a,b)  = findLIS(arr)
answer1 += a
if b+1 < arr.count {
    (a,b) = findLIS(Array(arr[b+1..<arr.endIndex].reversed()))
    answer1 += a
}
// 뒤에서부터 시작하는 LIS -> 앞에서부터 시작하는 LIS
(a,b) = findLIS(arr.reversed())
answer2 += a
if b < arr.count-1 {
    (a,b) = findLIS(Array(arr[0..<arr.count-b-1]))
    answer2 += a
}
print(max(answer1,answer2))

✍️ 두번째 접근

아래의 반례를 찾아 내 논리가 부족하다는 것을 깨달았다.

10
10 1 3 5 7 6 3 2 1 10
ans: 8

내 논리대로라면, 1번)의 결과는 1 3 5 7 10이고 2번)의 결과는 1 2 3 6 7 10이므로 정답이 6이라는 틀린 판단을 하게 된다. 따라서, 입력받은 각각의 인덱스에 대해서 정방향 LIS와 역방향 LIS를 구하는 방식을 선택하였다. 위의 반례를 들어서 설명하면, i=4라고 했을 때 10 1 3 5 7의 정방향 LIS와 7 6 3 2 1 10의 역방향 LIS를 구한다. 이 둘의 길이를 더하고 7이 중복되므로 1을 뺀다. i는 0부터 9까지 위와 같은 작업을 진행해 나온 값 중에 가장 큰 값을 출력하여 해결할 수 있었다.

import Foundation

func binary_search(_ LIS: [Int], _ left: Int, _ right: Int, _ target: Int) -> Int {
    var left = left
    var right = right
    var mid = 0
    while left < right {
        mid = (left+right)/2
        if LIS[mid] < target {
            left = mid + 1
        }
        else {
            right = mid
        }
    }
    return right
}

func findLIS(_ arr: [Int]) -> Int {
    var LIS = Array(repeating: 0, count: arr.count+1)
    var i = 1, j = 0
    LIS[0] = arr[0]
    while i < arr.count {
        if LIS[j] < arr[i] {
            j += 1
            LIS[j] = arr[i]
        }
        else {
            let index = binary_search(LIS, 0, j, arr[i])
            LIS[index] = arr[i]
        }
        i += 1
    }
    return j+1
}

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var answer: [Int] = []
for i in 0..<arr.count-1 {
    let forward = findLIS(Array(arr[0...i]))    // 0번째부터 i번째까지의 LIS
    let backward = findLIS(Array(arr[i...arr.count-1]).reversed())    // i번째부터 마지막까지의 Longest Decreasing Subsequence를 구해야하므로 마지막부터 i번째까지에서 LIS를 구함.
    answer.append(forward+backward-1)
}
print(answer.max() ?? 1)

✍️ 첫번째 접근

첫번째 문자열과 두번재 문자열에 대한 LCS를 구하고, 그 결과와 세번째 문자열에 대한 LCS를 구하는 접근을 하였다. 하지만, 틀리게 되어 반례가 있나 생각해보았더니 반례가 존재하였다.

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let str3 = readLine()!.map { String($0) }
var LCS1 = Array(repeating: Array(repeating: 0, count: str2.count+1), count: str1.count+1)
var LCS_str = ""
for i in 1...str1.count {
    for j in 1...str2.count {
        if str1[i-1] == str2[j-1] {
            LCS1[i][j] = LCS1[i-1][j-1] + 1
        }
        else {
            LCS1[i][j] = max(LCS1[i][j-1],LCS1[i-1][j])
        }
    }
}
var i = str1.count
var j = str2.count
let maxValue = LCS1.flatMap{$0}.max() ?? 0
while true {
    if LCS_str.count >= maxValue {
        break
    }
    if LCS1[i][j] == LCS1[i][j-1] {
        j = j-1
    }
    else if LCS1[i][j] == LCS1[i-1][j] {
        i = i-1
    }
    else {
        i = i-1
        j = j-1
        LCS_str += str1[i]
    }
}
let str4 = String(LCS_str.reversed()).map { String($0) }
if str4.count < 1 {
    print("0")
}
else {
    var LCS2 = Array(repeating: Array(repeating: 0, count: str3.count+1), count: str4.count+1)
    for i in 1...str4.count {
        for j in 1...str3.count {
            if str4[i-1] == str3[j-1] {
                LCS2[i][j] = LCS2[i-1][j-1] + 1
            }
            else {
                LCS2[i][j] = max(LCS2[i][j-1],LCS2[i-1][j])
            }
        }
    }
    print(LCS2.flatMap{$0}.max()!)
}

✍️ 두번째 접근

다음과 같이 문자열이 들어올 경우가 반례이다. 따라서, 첫번째 접근과 다르게 첫번째 문자열, 두번째 문자열, 세번째 문자열에 대한 LCS를 한번에 구해 해결할 수 있었다.

A: dababcf
B: ababdef
C: df

LCS(A,B): ababf
LCS(LCS(A,B),C):  f
LCS(A,B,C): df

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let str3 = readLine()!.map { String($0) }
var LCS = Array(repeating: Array(repeating: Array(repeating: 0, count: str3.count+1), count: str2.count+1), count: str1.count+1)
for i in 1...str1.count {
    for j in 1...str2.count {
        for k in 1...str3.count {
            if str1[i-1] == str2[j-1] && str2[j-1] == str3[k-1]{
                LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1
            }
            else {
                LCS[i][j][k] = max(LCS[i][j][k-1],LCS[i-1][j][k],LCS[i][j-1][k])
            }
        }
    }
}
print(LCS.flatMap{$0}.flatMap{$0}.max()!)

✍️ 첫번째 접근

문제 제목에서도 알 수 있듯이, LCS(Longest Common Substring) 알고리즘을 적용하는 문제이다. 어째서인지...시간 초과가 발생하였다. Swift는 문자열에 대한 접근이 안 좋다는 기억이 되살아났다.

import Foundation

extension String {
    subscript(_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

let str1 = readLine()!
let str2 = readLine()!
let maxLength = max(str1.count,str2.count)
var LCS = Array(repeating: Array(repeating: 0, count: maxLength+1), count: maxLength+1)
for i in 0..<str1.count {
    for j in 0..<str2.count {
        if i == 0 || j == 0 {
            continue
        }
        if String(str1[i]) == String(str2[j]) {
            LCS[i][j] = LCS[i-1][j-1] + 1
        }
        else {
            LCS[i][j] = 0
        }
    }
}
print(LCS.flatMap{$0}.max() ?? 0)

✍️ 두번째 접근

첫번째 접근에서 extension을 사용해 Int형으로 원하는 위치의 문자열 요소에 접근할 수 있는 기능을 구현하였다. 문자열 각각의 인덱스를 접근하지 말고, 입력받을 때 String 타입이 아니라 Array 타입으로 저장하였다. 또한 for문 안에서 i 또는 j가 0일 때 continue를 하게 되면 각 문자열의 첫번째 글자를 무시하게 되므로 이를 삭제하여 해결하였다.

import Foundation

let str1 = readLine()!.map { String($0) }
let str2 = readLine()!.map { String($0) }
let maxLength = max(str1.count,str2.count)
var LCS = Array(repeating: Array(repeating: 0, count: maxLength+1), count: maxLength+1)
for i in 1...str1.count {
    for j in 1...str2.count {
        if str1[i-1] == str2[j-1] {
            LCS[i][j] = LCS[i-1][j-1] + 1
        }
        else {
            LCS[i][j] = 0
        }
    }
}
print(LCS.flatMap{$0}.max() ?? 0)