오늘의 알고리즘 코드카타!

직사각형 별찍기

---

[프로그래머스 문제 링크]

문제 설명

이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다.

별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요.

---

제한 조건

• n과 m은 각각 1000 이하인 자연수입니다.

---

예시

입력

5 3

출력

*****
*****
*****

---

나의 풀이

import Foundation

let n = readLine()!.components(separatedBy: [" "]).map { Int($0)! }
let (a, b) = (n[0], n[1])

var answer = "" 

for _ in 1...b {
    for _ in 1...a {
        answer += "*"
    }
    answer += "\n"
}

print(answer)

다른 사람 풀이

import Foundation

let n = readLine()!.components(separatedBy: [" "]).map { Int($0)! }
let (a, b) = (n[0], n[1])

for _ in 0..<b {
    print(Array(repeating: "*", count: a).joined())
}

repeating이 있었는데.. 사용을 안했다..

반복문 돌려서 문자열 추가하는 것 보다 훨씬 빠를 거 같다!

이 문제는 한 개의 값을 리턴하는 게 아니라 문자열을 출력하는 거였기때문에

\n을 사용할 필요없이 print()를 구분하여 출력하면 자동으로 한 줄 띄어졌다.

실행결과 비교

전체 실행 시간 : 6.390933632850647(s)
전체 실행 시간 : 1.8803969621658325(s)

n - 1000, m - 1000으로 10번 돌린 결과

전체 실행 시간의 합이 위처럼 나왔다.

많이 차이난다!

최대공약수와 최소공배수

---

[프로그래머스 문제 링크]

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

나의 풀이

import Foundation

func solution(_ n:Int, _ m:Int) -> [Int] {
 
    // 최대공약수 구하기
    func euclidean(_ n: Int, _ m: Int) -> Int {
        let x = max(n, m)
        let y = min(n, m)
        if x == y {
            return x
        }else if x % y == 0{
            return y
        }else {
            return euclidean( x%y, y)
        }
    }
    let g = euclidean(n,m)
    return [g, n*m/g]
}

대학교에서 배운 유클리드 호제법이 생각나서 풀었다.

유클리드 호제법은 아주 큰 수의 최대공약수를 쉽게 구할 수 있는 방법이다.

---

유클리드 호제법

$m$과 $n$의 최대공약수를 $GCD(m, n)$이라고 한다.

$m > n$ 라고 가정하자.

그러면 $m = n * x + r$ 가 성립한다. 이 때, x는 몫이고, r은 나머지이므로 둘다 정수이다.

이때 $GCD(m,~n) = GCD(n,~r)$ 이다.

만약 나머지가 0이라면 $m$은 $n$의 배수 이므로 최대 공약수는 $n$이 된다.

---

→ 이를 알고리즘으로 재귀함수로 나타내었다.

또한 최대공약수만 알면 최소공배수는 쉽게 구할 수 있다.

최소공배수는 두 수를 곱합 것에서 최대공약수를 나누면 된다.

다른 사람 풀이

func gcd(_ a: Int, _ b: Int) -> Int {
    let mod: Int = a % b
    return 0 == mod ? min(a, b) : gcd(b, mod)
}

func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

func solution(_ n:Int, _ m:Int) -> [Int] {
    return [gcd(n, m), lcm(n, m)]
}

엄청 깔끔하게 푸심.

하지만, 이렇게 되면 최대공약수의 계산을 두번 해야하기 때문에 최대공약수를 변수에 저장한뒤 최소공배수를 구하는 것이 시간 복잡도 측면에서는 더 좋을 거 같다.

예를 들면 아래처럼.

func solution(_ n:Int, _ m:Int) -> [Int] {
    let g = gcd(n,m)
    return [g, n * m / g]
}

func gcd(_ n:Int,_ m: Int)->Int {
    return n%m == 0 ? min(n, m) : gcd(m, n%m)
}

3진법 뒤집기

---

[프로그래머스 문제 링크]

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예

n	result
45	7
125	229

입출력 예 설명

입출력 예 #1

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)	n (3진법)	앞뒤 반전(3진법)	10진법으로 표현
45	1200	0021	7

• 따라서 7을 return 해야 합니다.

입출력 예 #2

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)	n (3진법)	앞뒤 반전(3진법)	10진법으로 표현
125	11122	22111	229

• 따라서 229를 return 해야 합니다.

---

나의 풀이

import Foundation

func solution(_ n:Int) -> Int {
    var n = n
    var ternary = ""
    var answer = 0
    while n != 0 {
        ternary += "\(n % 3)"
        n = n/3
    }
    for (i,a) in ternary.reversed().enumerated() {
        answer += Int(String(a))! * Int(pow(3.0,Double(i)))
    }
    return answer
}

진법 처리로 풀면 된다라는 건 알았지만, 코드가 기억이 나지 않았다.

그래서 정석적인 방법대로 3진법으로 바꾸고 다시 돌려 십진법으로 바꾸는 방법을 택했다.

다른 사람 풀이

func solution2(_ n:Int) -> Int {
    let flipToThree = String(n, radix: 3)
    let answer = Int(String(flipToThree.reversed()),radix:3)!
    return answer
}

⭐️ k진법으로 바꾸는 코드!!!!!

**String(n, radix: k)**

절대 잊어버리지 않겠다.

Int → String으로 바꾸면 n 진법

String → Int로 바꾸면 십진법

이상한 문자 만들기

---

[프로그래머스 문제 링크]

문제 설명

문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요.

제한 사항

• 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다.
• 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다.

입출력 예

s	return
"try hello world"	"TrY HeLlO WoRlD"

입출력 예 설명

"try hello world"는 세 단어 "try", "hello", "world"로 구성되어 있습니다. 각 단어의 짝수번째 문자를 대문자로, 홀수번째 문자를 소문자로 바꾸면 "TrY", "HeLlO", "WoRlD"입니다. 따라서 "TrY HeLlO WoRlD" 를 리턴합니다.

---

나의 풀이

func solution(_ s:String) -> String {
    var arrayS = [String]()
    for i in s.components(separatedBy: " "){
        arrayS.append(i.enumerated().map{ $0.offset % 2 == 0 ? $0.element.uppercased() : $0.element.lowercased() }.joined())
    }
    return arrayS.joined(separator: " ")
}

처음엔 전체 문자열에 대한 짝수번째 홀수번째인줄 알고 풀었는데,

문제를 다시 읽어보니 “ “ 뛰어쓰기가 된 단어마다의 짝/홀수 인덱스를 파악하는 문제였다.

그래서 빈칸까지 인식하여 Array로 바꿔주는 components를 택하여 나눠주고

joined의 separator을 사용하여 다시 “ “ 로 붙여주었다.

사실 joined(separator: )라는 함수가 있는지 모르고, joined( “ “ ) 이렇게 하면 되지 않을 까 싶어 실행하였지만,

separator: 를 빼먹었다는 오류 내용을 보고 확신했다.히히

삼총사

---

[프로그래머스 문제 링크]

문제 설명

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

제한사항

• 3 ≤ number의 길이 ≤ 13
• 1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

입출력 예

number	result
[-2, 3, 0, 2, -5]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 학생들의 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2) 이 삼총사가 될 수 있으므로, 5를 return 합니다.

입출력 예 #3

• 삼총사가 될 수 있는 방법이 없습니다.

---

나의 풀이

import Foundation

func solution(_ number:[Int]) -> Int {
    var count = 0
    for i in 0..<number.count-2{
        for j in (i+1)..<number.count-1{
            for z in (j+1)..<number.count{
                if number[i] + number[j] + number[z] == 0{
                    count += 1
                }
            }
        }
    }
    return count
}

이 문제는 저번에 한 번 풀고 두번째 푸는 것이다.

저번에 풀었던 풀이를 찾아보았다.

import Foundation

func solution(_ number:[Int]) -> Int {
    var answer = 0
    (0...number.count-3).forEach { i in
        if i+1 <= number.count-2 {
            (i+1...number.count-2).forEach { j in
                if j+1 <= number.count-1 {
                    (j+1...number.count-1).forEach { k in
                        answer += number[i] + number[j] + number[k] == 0 ? 1 : 0 
                    }
                }
            }
        }
    }
    return answer
}

이제는 for-in이 forEach 보다 더 빠르고, 보기도 편하다는 사실을 아니까 ㅎㅎ 발전했다 나자신!

다른 사람 풀이

import Foundation

func solution(_ number:[Int]) -> Int {
    var answer = 0
    func dfs(_ now: Int, _ sum: Int, _ count: Int) {
        if count == 3 {
            if sum == 0 { answer += 1 }
            return
        }
        for i in now..<number.count {
            dfs(i+1, sum + number[i], count + 1)
        }
    }
    dfs(0, 0, 0)
    return answer
}

dfs를 이용하여 문제를 풀었다.

사실 재귀함수 인건 알겠는데.. 풀이를 잘 이해하지 못하겠다..

dfs를 공부한 뒤에 다시 봐야겠다.