코딩테스트 입문 (feat. Day 9 수학, 문자열, 해시, 완전탐색, 조건문)

9일차 스탬프

1.  개미 군단

Q. 개미 군단이 사냥을 나가려고 합니다. 개미군단은 사냥감의 체력에 딱 맞는 병력을 데리고 나가려고 합니다. 장군개미는 5의 공격력을, 병정개미는 3의 공격력을 일개미는 1의 공격력을 가지고 있습니다. 예를 들어 체력 23의 여치를 사냥하려고 할 때, 일개미 23마리를 데리고 가도 되지만, 장군개미 네 마리와 병정개미 한 마리를 데리고 간다면 더 적은 병력으로 사냥할 수 있습니다. 사냥감의 체력 hp가 매개변수로 주어질 때, 사냥감의 체력에 딱 맞게 최소한의 병력을 구성하려면 몇 마리의 개미가 필요한지를 return하도록 solution 함수를 완성해주세요.

func solution(_ hp:Int) -> Int {
    return hp / 5 + hp % 5 / 3 + hp % 5 % 3
}

 

A. 전달 받은 hp를 5로 먼저 나누어 장군개미의 수를 구하고,

남은 hp를 3으로나누어 병정개미의 수를 구한 후,

나머지 hp만큼 일개미로 채워 문제를 해결했다.

2. 모스부호 (1)

Q. 머쓱이는 친구에게 모스부호를 이용한 편지를 받았습니다. 그냥은 읽을 수 없어 이를 해독하는 프로그램을 만들려고 합니다. 문자열 letter가 매개변수로 주어질 때, letter를 영어 소문자로 바꾼 문자열을 return 하도록 solution 함수를 완성해보세요. 모스부호는 다음과 같습니다. (letter의 모스부호는 공백으로 나누어져 있습니다.)

func solution(_ letter:String) -> String {
    let morse: [String: Character] = [
	".-": "a", "-...": "b", "-.-.": "c", "-..": "d", ".": "e", "..-.": "f",
	"--.": "g", "....": "h", "..": "i", ".---": "j", "-.-": "k", ".-..": "l",
	"--": "m", "-.": "n", "---": "o", ".--.": "p", "--.-": "q", ".-.": "r",
	"...": "s", "-": "t", "..-": "u", "...-": "v", ".--": "w", "-..-": "x",
	"-.--": "y", "--..": "z"
    ]
    var result = ""
    letter.split(separator: " ").forEach {
        result.append(morse[String($0)]!)
    }
    return result
}

 

A. 먼저 주어진 모스부호로 dictionary를 생성했다.

그리고 전달 받은 letter를 split을 활용해 문자열로 이뤄진 각각의 모스부호를 배열로 나누고

forEach를 통해 순회하면서 해당하는 모스부호를 key로 접근하여 value를 result에 추가하였고

그 값을 반환하여 해결했다.

 

feat.

위 문제에서 split을 활용하여 해결했는데 다른 사람들의 풀이를 보니

components(separatedBy:)를 많이 활용했다.

그래서 두 메서드의 차이점을 찾아보았는데 가장 큰 차이점은 리턴하는 타입이 다르다는 것이었다.

- compenents => [String] 반환

- split => [SubString] 반환

 

문제를 해결할 때, map을 활용해 더 간단하게 코드를 작성하고 싶었는데

split을 사용하니 type 때문에 에러가 발생해서 forEach로 문제를 해결했는데

앞으로는 문자열을 다룰 때, components를 활용한다면 map을 원활하게 사용할 수 있을 것 같다!

3. 가위 바위 보

Q. 가위는 2 바위는 0 보는 5로 표현합니다. 가위 바위 보를 내는 순서대로 나타낸 문자열 rsp가 매개변수로 주어질 때, rsp에 저장된 가위 바위 보를 모두 이기는 경우를 순서대로 나타낸 문자열을 return하도록 solution 함수를 완성해보세요.

func solution(_ rsp:String) -> String {
    return rsp.map { $0 == "2" ? "0" : $0 == "0" ? "5" : "2"}.joined()
}

 

A. 전달 받은 rsp를 고차함수 map을 통해 순회하며 가위일 때는 0, 바위일 때는 5, 보일 때는 2를 반환하여 배열로 저장하고 그 값을 joined()를 통해 문자열로 변환한 후 그 값을 반환하여 해결했다.

4. 구슬을 나누는 경우의 수

Q. 머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요. (share ≤ balls)

func solution(_ balls:Int, _ share:Int) -> Int {
    guard balls != share else { return 1 }

    return Int(round(factorial(balls) / factorial(share) / factorial(balls-share)))
}

func factorial(_ n: Int) -> Double {
    return Double((1...n).reduce(1.0){ Double($0) * Double($1) })
}

 

A. 먼저 힌트를 보며 팩토리얼 연산을 위한 함수를 만들었다.

그리고 balls와 share의 값이 같을 때, 범위를 구하는 1...0으로 에러가 발생할 수 있기 때문에

guard 구문으로 예외 처리를 해준 후, 힌트의 식을 만들어둔 함수를 활용해 작성하고 그 값을 반환하여 해결했다.

 

feat.

위 문제에서 두 가지의 이야기를 하고 싶은데

먼저, Double과 round를 사용한 이유다.

Int로만 문제를 해결하면 swift에선 오버플로우가 발생한다.

왜냐하면 Swift의 기본 Int는 64비트 시스템에서 최대값이 2⁶³ - 1 이기 때문이다.

예를 들어 21! = 51,090,942,171,709,440,000 와 같은 값들을 Int 타입의 변수에는 저장할 수 없기 때문에 에러가 발생한다.

따라서 Double을 사용해서 오버플로우가 발생하는 케이스를 제거했다.

 

하지만 Double을 사용해 큰 수를 연산할 때, 부동소수점의 연산에서 오차가 발생할 수 있기 때문에

정확한 답을 위해서 round를 통해 반올림을 진행한 후 Int로 값을 변환한 후 반환하였다.

// Oliver님 코드
func solution(_ balls:Int, _ share:Int) -> Int {
    var result = (balls - share + 1...balls)
        .map { Double($0) }
        .reduce(1.0, *)

    (1...share)
        .map { result /= Double($0) }

    return Int(result)
}

 

그래서 두번째로 하고 싶은 이야기는 round를 사용하지 않는 방법이다.

위 코드는 다른 사람의 풀이를 참고한 코드인데

먼저, 분자의 값을 구한 후, 분모의 값을 팩토리얼 연산이 아닌 1부터 share까지 차근차근 나눠주는 방법이다.

이 방법을 사용한다면 부동소수점으로 큰 수를 연산하는 경우가 없기 때문에 round를 사용하지 않더라도

오차 없이 문제에서 요구하는 값을 얻을 수 있다.

---

8일차 스탬프

어제 해결하지 못한 두 문제의 풀이도 작성하고자 한다.

1.  외계행성의 나이

Q. 우주여행을 하던 머쓱이는 엔진 고장으로 PROGRAMMERS-962 행성에 불시착하게 됐습니다. 입국심사에서 나이를 말해야 하는데, PROGRAMMERS-962 행성에서는 나이를 알파벳으로 말하고 있습니다. a는 0, b는 1, c는 2, ..., j는 9입니다. 예를 들어 23살은 cd, 51살은 fb로 표현합니다. 나이 age가 매개변수로 주어질 때 PROGRAMMER-962식 나이를 return하도록 solution 함수를 완성해주세요.

func solution(_ age:Int) -> String {
    var result = ""
    String(age).forEach {
        result.append(convertToString(num: String($0)))
    }
    return  result
}

func convertToString(num: String) -> String {
    switch num {
        case "0":
            return "a"
        case "1":
            return "b"
        case "2":
            return "c"
        case "3":
            return "d"
        case "4":
            return "e"
        case "5":
            return "f"
        case "6":
            return "g"
        case "7":
            return "h"
        case "8":
            return "i"
        case "9":
            return "j"
        default:
            return ""
    }
}

 

A. switch문을 통해 각 정수에 맞는 알파벳을 반환하여 결과값에 추가하고 그 값을 반환하여 해결했다.

 

feat.

막상 해결한 후, 다른 사람들의 풀이를 보니 너무 생각을 덜 하고 문제를 푼 것 같았다.

func solution(_ age:Int) -> String {
    let alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
    return String(age).map{alphabet[Int(String($0))!]}.joined()
}

 

특히 위 해결법을 보고 너무 깔끔하게 풀 수 있는 문제를

어렵게 돌아가서 푼 것 같아서 아쉬웠다.

2. 진료순서 정하기

Q. 외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.

func solution(_ emergency: [Int]) -> [Int] {
    let sortedEmergency = emergency.sorted(by: >)
    return emergency.map { sortedEmergency.firstIndex(of: $0)! + 1 }
}

 

A. 전달 받은 emergency를 고차함수 map으로 순회하며

내림차순으로 정렬한 배열에서 기존 배열의 응급도의 값과 일치하는 index를 firstIndex()로 찾은 후,

그 값들을 배열로 반환하여 해결했다.

---

이제부터 푸는 문제들이 생각을 좀 해야 풀 수 있을 정도의 난이도까지 올라온 것 같다.

어제 약속으로 인해 오늘 2문제를 더 풀었는데,

주말이어서 그렇지 평일이었으면 또 미루게 됐을 것 같다.

문제가 어려워지는 만큼 시간 배분을 잘해서

꼭 미루지 않고 그날 그날 해결할 수 있도록 노력해야할 것 같다.

그리고 문제를 해결하더라도 조금 더 좋은 방향으로 코드를 작성할 수 있도록

생각을 깊게 하며 문제를 해결한다면 더 의미있는 시간이 될 것이라 느낀 하루였다.

내일도 화이팅!