Jenikeju

문제

https://school.programmers.co.kr/learn/courses/30/lessons/388352

내가 푼 방법

비밀코드의 범위가 주어지면 해당 범위에서 만들 수 있는 모든 조합을 먼저 구한 뒤,

각 ans의 응답값을 비교해서 모두 일치하는 경우 하나의 비밀코드로 간주했다.

조합과 이중반복문으로 시간초과가 걸릴 것 같았지만, 가까스로 통과한 느낌이였다.

import Foundation

func solution(_ n:Int, _ q:[[Int]], _ ans:[Int]) -> Int {
    let targetArr = Array(1...n)
    var total = 0
    var results = [[Int]]()
    // 조합
    func combi(targetArr: [Int], targetNum: Int, index: Int, arr: [Int]) {
        if arr.count == targetNum {
            results.append(arr)
            return
        }
        for i in index..<targetArr.count {
            combi(targetArr: targetArr, targetNum: targetNum, index: i+1, arr: arr + [targetArr[i]])
        }
    }
    combi(targetArr: targetArr, targetNum: 5, index: 0, arr: [])
    
    // 각 응답값 비교
    results.forEach { element in
        for i in 0..<q.count {
            let arr = q[i]
            if !compare(lhs: arr, rhs: element, correct: ans[i]) {
                break
            }
            if i == q.count-1 {
                total += 1
            }
        }
    }
    return total
}

func compare(lhs: [Int], rhs: [Int], correct: Int) -> Bool {
    var count = 0
    for i in 0..<lhs.count {
        if rhs.contains(lhs[i]) { count += 1}
    }
    if count == correct { return true }
    return false
}

문제 설명 ▼

내가 푼 풀이

• 주어진 players배열과 크기가 같은 servers 배열을 만들었습니다.
• players배열을 반복문으로 순회하면서 각 시간마다 서버 증설이 필요한지 조건을 달았습니다.
• 증설이 필요하다면 그리디 기법으로 현재 시간의 인원을 수용할 만큼만의 서버를 증설하고 k시간까지 최대 이용자 수를 증가시켰습니다.
• 증설이 필요할 때 서버를 증설하고 증설된 수를 count 변수에 담아서 리턴했습니다.

import Foundation

func solution(_ players:[Int], _ m:Int, _ k:Int) -> Int {
    var servers = Array(repeating: 0, count: players.count)
    var count = 0
    
    for i in 0..<players.count {
        let allowPlayerCount = (servers[i] * m) + m
        if players[i] >= allowPlayerCount {
            let needServerCount = abs(servers[i] - (players[i] / m))
            count += needServerCount
            for j in i..<i+k {
                if j >= players.count { continue }
                servers[j] += needServerCount
            }
        }
    }
    
    return count
}

문제 설명▼

내가 푼 풀이

BFS를 사용해서 풀었습니다.

• 1번으로부터 가장 먼 노드의 갯수를 구하기 때문에, 인접한 그래프를 이동하는 움직임을 하나의 단위로 생각했습니다.
• 한번의 움직임을 담은 needToVisit 배열과, 움직임을 통해 도착한 노드의 인접그래프가 담긴 saveNextVisitList 배열을 선언해 주었습니다.
• 한번 이동을 통해 needToVisit의 배열이 비었다면, 도착 노드와 인접한 노드들이 담긴 saveNextVisitList를 needToVisit에 할당하고 saveNextVisitList를 빈배열로 초기화했습니다.
• 이미 방문한 노드들은 다시 갈 필요가 없으므로 노드 갯수만큼의 visited 배열 크기를 만들고 선언했습니다.
• saveNextVisitList에는 Set 형변환을 통해 중복 노드들을 제거하고 다시 Array배열로 형변환 후 visited 배열을 통해 방문하지 않은 노드들로 필터링을 했습니다.
• needToVisit은 인접한 그래프로의 한 움직임 단위 이므로 이를 lastNode 2차원 배열에 담았습니다. lastNode 배열은 needToVisit의 기록을 담고있습니다.
• 최종적으로 모든 노드를 도달했다면 needToVisit은 빈 배열이 되고 빈 배열이 lastNode배열에 담기게 되므로 결과로 lastNode의 마지막에서 두번째 원소의 갯수를 리턴하도록 설계하였습니다.

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph: [Int: [Int]] = [:]
    // 그래프를 딕셔너리에 담기
    edge.forEach { (element) in
        if graph[element[0]] == nil {
            graph[element[0]] = [element[1]]
        } else {
            graph[element[0]]!.append(element[1])
        }
        if graph[element[1]] == nil {
            graph[element[1]] = [element[0]]
        } else {
            graph[element[1]]!.append(element[0])
        }
    }
    
    // 인접한 그래프로의 한번 이동을 담은 배열
    var needToVisit = [1]
    // 인접한 도착노드들의 인접노드들을 담은 배열
    var saveNextVisitList: [Int] = []
    // 방문기록
    var visited = Array(repeating: false, count: n+1)
    // needToVisit의 이전 기록들을 담는 배열
    var lastNode = [[Int]]()
    
    // BFS
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        visited[node] = true
        var nextNodes = graph[node]!
        saveNextVisitList += nextNodes
        
        if needToVisit.isEmpty {
            if saveNextVisitList.isEmpty {
                break 
            }
            let setVisitList = Array(Set(saveNextVisitList))
            for element in setVisitList {
                if !visited[element] {
                    needToVisit.append(element)
                    
                }
            }
            lastNode.append(needToVisit)
            saveNextVisitList = []
        }
    }
    return lastNode[lastNode.count-2].count
}

문제 설명

내가 푼 풀이

첫번째 방법 - DFS

한개의 물건이 주어졌을 때, 두가지 경우의 수가 있습니다.

1. A가 훔치기

2. B가 훔치기

또한 경찰에게 걸리지 않게 모든 물건을 훔쳤기에 물건을 훔치지 않는 옵션은 없습니다.

결국 A가 최소로 도둑질을 하면 흔적도 자연스럽게 최솟값을 가질 것이라 생각하고, B에게 먼저 조건을 걸어주었고, B가 최대한 훔치도록 구현하였습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    var min = Int.max
    var informations = info
    
    func dfs(count: [Int], currentIndex: Int) {
        if currentIndex >= info.count {
            min >= count[0] ? min = count[0] : nil
            return
        }
        let theifACount = [count[0] + info[currentIndex][0], count[1]]
        let theifBCount = [count[0], count[1] + info[currentIndex][1]]
        if theifACount[0] < n && theifACount[0] < min {
            dfs(count: [count[0] + info[currentIndex][0], count[1]],
            currentIndex: currentIndex + 1)
        }
        if theifBCount[1] < m {
            dfs(count: [count[0], count[1] + info[currentIndex][1]],
            currentIndex: currentIndex + 1)
        }
    }
    dfs(count: [0, 0], currentIndex: 0)
    
    return min == Int.max ? -1 : min
}

결과는 시간초과가 발생하였습니다.

이유를 확인해보면, 만약 m,n이 매우 넉넉하다면, 큰 수라면 bfs의 실행은 $2^{40}$ 번 실행되어 시간초과가 발생하였습니다.

그러면 시간만 줄여서 될까 해서 테스트케이스를 몇 개 추가했더니, 해당 케이스도 실패하는걸 볼 수 있었습니다.

info = [[1, 2], [3, 1], [3, 2]]
n = 5
m = 3
// 결과는 4가 나와야 하지만 1이 나왔습니다.

이를 통해 매번 탐색할 때 최적해를 갱신해야 할 필요가 있구나 싶었습니다.

두번째 방법 - DP

이전까지의 최적해를 저장하여 그다음 최적해를 구하기 위해 DP를 사용했습니다.

info배열을 돌면서 한번으로 최적해가 구해질 수 있을까? 해서 작성해보았는데 위 테스트 케이스도 통과하지 못했습니다.

B도둑이 알뜰살뜰하게 m을 넘지 않으면서 m과 가까운 수만큼 흔적을 남기는 방법이 뭐가 있을까 하다가 배낭문제가 생각났습니다.

(도둑이 배낭에 보석을 담을 때 정해진 배낭무게, 보석무게와 가치에 맞춰서 가장 가치있는 보석만 골라담는 문제)

B도둑이 최대한 흔적을 많이 남길 수 있게 배낭문제처럼 m값을 갱신하고 A흔적의 최솟값을 구하려고 합니다.

이를 1번 입력을 예시로 2차원배열로 나타내보겠습니다.

행은 m, B가 남길 수 있는 흔적 입니다. 열은 index로 info의 물건을 접근하기위한 인덱스입니다.

조건을 다시 살펴보자면,

1. 모든 물건을 훔쳤다.(물건을 훔치지 않고 건너뛰는건 불가능)

2. A는 n, B는 m 보다 같거나 클 수 없다. 만약 같거나 크다면 훔칠 수 없다고 판단한다.

위 조건을 바탕으로 배낭문제 처럼 2차원 배열을 채워가며 A의 최솟값을 구하겠습니다.

dp[i][j] = 0 은 물건을 하나도 훔치지 않을 때 값입니다.

행은 무게를 뜻하고, 열은 물건의 순서를 뜻하고, 해당 위치의 원소는 A의 흔적입니다.

첫번째는 아무것도 훔치지 않았기때문에 dp[0][1...3] = 0 입니다.

이제 첫번째 물건을 훔치겠습니다. 물건의 정보는 [1, 2] 입니다.

이때, 두가지 경우의 수가 있습니다. (1. A가 훔치기 2. B가 훔치기)

해당 DP인덱스의 원소는 A의 흔적을 의미하기에 A가 훔친다면 이전 값에서 A의 흔적을 더한값이 될 것입니다.

B가 훔친다면, (현재열 + 2) 인덱스에 이전 값을 넣게 됩니다.

이렇게 이전의 저장된 값을 바탕으로 최적해를 구하기위해 갱신하면 다음과 같습니다.

그 다음 두번째 물건을 훔치겠습니다. 물건의 정보는 [2,3] 입니다.

두번째 물건도 두가지 경우가 있습니다.

dp[2][0]에는 3이 들어가고 이 의미는 두번째 물건까지 A가 훔치는 경우입니다.

두번째 물건을 B가 훔치는 경우는 (현재 열 + 3) 인덱스에 넣게 되는데, 이 때 첫번째 물건을 넣은 값과 비교를 해야합니다.

dp[2][j + 3] = min ( dp[2][j + 3], dp[1][j] )

j = 0일때, dp[2][3] = min(dp[2][3], dp[1][0]) 을 비교하게 됩니다. (INF  > 1)

이를 m = 3까지 갱신해줍니다.

dp[2][1], dp[2][2]는 첫번째는 B, 두번째는 A가 훔친경우입니다. 첫번째와 두번째 둘다 A가 훔친 경우(dp[2][0])보다 작은 수 이므로 갱신했습니다.

마지막으로 세번째 물건을 훔치겠습니다. 물건 정보는 [2,1]입니다.

세번째 물건까지 A가 훔치면 dp[3][0] = 5입니다.

세번째 물건을 B가 훔치는 경우라면 현재 인덱스 + 1의 자리를 갱신해줍니다.

dp[3][1] = min (dp[3][1], dp[2][1]) = 3

m = 3까지 갱신해주면 아래와 같습니다.

최종적으로 dp[3][3]에 구하는 값을 나타낼 수 있음을 알 수 있습니다.

여기까지 살펴본 결과 2차원 배열의 의미를 다음과 같이 나타낼 수 있습니다.

dp[i][j]

• i : 현재 물건의 인덱스
• j : 현재 B의 흔적
• dp[i][j]의 원소: i번째 물건까지 훔쳤고 현재 B의 흔적이 j일때 A의 흔적 값

점화식은 아래와 같습니다.

1. A가 훔쳤을 때 : dp[i][j] = min(dp[i][j], dp[i-1][j] + a) (a는 해당물건의 A흔적)
2. B가 훔쳤을 때 : dp[i][j+b] = min(dp[i][j+b], dp[i-1][j]) (b는 해당물건의 B흔적)

코드로 나타내면 다음과 같습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    let INF = 100000000
    
    // DP
    var dp = Array(repeating: Array(repeating: INF, count: m),
                   count: info.count+1)
    for i in 0..<m {
        dp[0][i] = 0
    }
    
    for i in 1...info.count {
        // 현재 물건에 대한 A의 흔적과 B의 흔적
        let aThief = info[i-1][0]
        let bThief = info[i-1][1]
        
        for j in 0..<m {
        	// A가 훔친 경우 값 갱신
            dp[i][j] = min(dp[i][j], dp[i-1][j] + aThief)
            
            // B가 훔친 경우 값 갱신
            if j + bThief < m { 
                dp[i][j + bThief] = min(dp[i][j + bThief], dp[i-1][j])
            }
        }
    }
	// 마지막 물건과 B의 흔적이 m보다 크거나 같지 않게 훔쳤을 때의 최소값 리턴
    return dp[info.count][m-1] >= n ? -1 : dp[info.count][m-1]
}

내가 푼 풀이

접근방법 1. DFS 백트래킹 (시간초과)

최단시간을 구하는 문제는 BFS와 맞다..

1. 미로를 진입해 레버를 찾기까지 걸린시간을 구한다.

2. 레버를 찾았다면 레버위치에서 출구까지의 걸린시간을 더한다.

3. 레버를 못찾거나, 탈출구를 못찾았다면 -1출력

-> 이방법을 처음에 생각해서 사용해봤는데, 시간초과를 피할 수 없었다.

최악의 경우 모든 길을 찾아야하므로 BFS를 이용하기로 했다.

접근방법 2. BFS

DFS를 실패하고 바로 BFS를 설계했지만, BFS도 시간초과가 좀 났었다.

BFS는 인접한 지점 먼저 탐색이지만, 이미 탐색한곳은 재탐색을 하지 않게 해줘야한다.

재탐색여부를 저장하는 visited[Bool]에 값을 넣는 시점에따라 완전탐색, 조건에맞는 부분탐색을 하게 되었다.

BFS는 탐색시작지점에서 인접한 노드를 저장한다.

저장한 노드를 선입선출(큐와 같이)방식으로 빼내서 탐색을 실시한다.

여기서 탐색된곳임을 지정하는 과정이 다음노드를 넣을때 설정해줘야한다.

예로 [노드: 인접한노드]로 주어졌을때, [1: 2345] [2: 3456] [3: 45678] 이라면

1번 노드를 탐색했을때, 다음탐색은 2 - 3 - 4 - 5 를 탐색한다.

2번 노드를 탐색했을때, 다음탐색은 3 - 4 - 5 - 3 - 4 - 5 - 6 이된다.

2번과 인접한 노드는 이미 다음순서로 지정되있어서 중복탐색하게된다.

이렇게 큐에 쌓이지 않도록 하려면 인접한 노드를 넣을때, 그 노드는 이미 탐색이 되었다 라고 지정해줘야한다.

그러면 조건속에서 2번 노드를 탐색할때, 2번의 인접노드들은 이미 탐색된 노드들로 판단되므로, 큐에 쌓이지않는다.

이 점을 새기며, 코드를 수정하니 시간초과가 뜨지 않았다.

import Foundation

func solution(_ maps:[String]) -> Int {
    // 입력
    var map = [[String]]()
    var visited = [[Bool]]()
    var counted = [[Int]]()
    var start = (x: 0, y: 0)
    var lever = (x: 0, y: 0)
    var end = (x: 0, y: 0)
    for i in 0..<maps.count {
        let s = maps[i].map{String($0)}
        visited.append(Array(repeating: false, count: s.count))
        counted.append(Array(repeating: 10000000, count: s.count))
        map.append(s)
        for j in 0..<s.count {
            if map[i][j] == "S" {
                start = (x: j, y: i)
            }
            if map[i][j] == "L" {
                lever = (x: j, y: i)
            }
            if map[i][j] == "E" {
                end = (x: j, y: i)
            }
        }
    }
    // BFS
    var needVisit = [(x: start.x, y: start.y)]
    var index = 0
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    var copyVisited = visited
    var copyCounted = counted
    copyCounted[start.y][start.x] = 0
    // lever위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        
        index += 1
        if cur.x == lever.x && cur.y == lever.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            needVisit.append((x: mx, y: my))
        }
    }
    // 레버에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveLeverTime = copyCounted[lever.y][lever.x]
    if arriveLeverTime >= 10000000 { return -1 }
    
    needVisit = [(x: lever.x, y: lever.y)]
    index = 0
    copyCounted = counted
    copyCounted[lever.y][lever.x] = 0
    copyVisited = visited
    // end위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        

        index += 1
        if cur.x == end.x && cur.y == end.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            needVisit.append((x: mx, y: my))
        }
    }
    // 출구에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveEndTime = copyCounted[end.y][end.x]
    if arriveEndTime >= 10000000 { return -1 }

    return arriveLeverTime + arriveEndTime
}

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

 

입출력 예시

rows	columns	queries	result
6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

내가 푼 풀이

- 회전을 구현하여 해당 범위를 교체하고, 최솟값을 저장한다.

- 따로 다른 알고리즘 없이 회전하는 동작을 구현하면 된다.

import Foundation

func solution(_ rows:Int, _ columns:Int, _ queries:[[Int]]) -> [Int] {
    var board = Array(repeating:Array(repeating: 0, count: columns+1), count: rows+1)
    var answer = [Int]()
    // 입력
    for i in 1...rows {
        for j in 1...columns {
            board[i][j] = ((i-1) * columns + j)
        }
    }
    
    // 쿼리 돌리기
    var b = board
    for query in queries {
        var a = moveNums(query, b)
        var minNum = a.removeLast()
        answer += minNum
        b = a
    }
    
    return answer
}

func moveNums(_ query: [Int],_ arr: [[Int]]) -> [[Int]] {
    var dx = [1, 0, -1, 0]
    var dy = [0, 1,  0, -1]
    var a = arr
    var mx = query[1]
    var my = query[0]
    var rc = query[3] - query[1]
    var cc = query[2] - query[0]
    var previous = a[my][mx]
    var minNum = a[my][mx]
    // 회전하며, 저장된 값과 그 다음의 값을 비교해 최솟값 갱신
    for i in 0..<4 {
        if i == 0 || i == 2 {
            for j in 0..<rc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        } else {
            for j in 0..<cc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        }
    }
    
    a.append([minNum])
    return a
}

내가 푼 풀이

- 주어진 연산자의 우선순위를 모든 경우의수로 탐색해본다.

import Foundation

func solution(_ expression:String) -> Int64 {
    var operation = ["+", "-", "*"]
    var arr = [String]()
    var oop = [[String]]()
    var num = ""
    var answer = Int.min
    // 우선순위의 모든 경우의수 뽑기
    func combi(_ targetArr: [String],_ arr: [String]) {
        if arr.count == 3 {
            oop.append(arr)
        }
        for i in 0..<targetArr.count {
            if !arr.contains(targetArr[i]) {
                combi(targetArr, arr + [targetArr[i]])
            }
        }
    }
    combi(operation, [])
    
    // 연산자와 피연산자 구분하여 저장
    for i in expression {
        if operation.contains(String(i)) {
            arr.append(num)
            arr.append(String(i))
            num = ""
        } else {
            num += String(i)
        }
    }
    arr.append(num)
    
    // 모든경우의수 탐색하여 최댓값 구하기
    for i in oop {
        var a = arr
        for j in i {
            a = operate(String(j), a)
        }
        answer = max(answer, abs(Int(a[0])!))
    }
    
    return Int64(answer)
}

// 주어진 연산자로 계산
func operate(_ op: String,_ expression: [String]) -> [String] {
    var ex = [String]()
    var index = -1
    for i in 0..<expression.count {
        if i == index {
            index = -1
            continue
        }
        if expression[i] != op {
            ex.append(expression[i])
        } else {
            var n1 = Int(ex.removeLast())!
            var n2 = Int(expression[i+1])!
            switch op {
                case "*":
                ex.append(String(n1 * n2))
                case "-":
                ex.append(String(n1 - n2))
                case "+":
                ex.append(String(n1 + n2))
                default :
                continue
            }
            index = i+1
        }
    }
    return ex
}

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

내가 푼 풀이

- 주어진 동작들을 함수로 구현한 뒤, 재귀호출 형식으로 구현한다.

import Foundation

func solution(_ p:String) -> String {
    return correctSameString(p)
}

// 전체적인 동작
func correctSameString(_ str: String) -> String {
    // 올바른문자열이라면 재귀 탈출
    if isCorrectString(str) {
        return str
    } else {
        var arr = divideString(s: str)
        // 분리한 문자열 u가 올바른 문자열이면 v는 다시 재귀호출
        if isCorrectString(arr[0]) {
            return "\(arr[0])" + "\(correctSameString(arr[1]))"
        } else {
            // 분리한 문자열 u가 올바른 문자열이 아니라면, v는 재귀호출하고, (v)u 형식으로 출력
            var s = ""
            var cs = ""
            var sarr = arr[0]
            // u문자열의 앞뒤 자르기
            if sarr.count != 0 {
                s = String(sarr.prefix(sarr.count-1))
                s.remove(at: s.startIndex)
            }
            // u문자열 뒤집기
            for i in s {
                if i == "(" {
                    cs += ")"
                } else {
                    cs += "("
                }
            }
            // 형식에 맞게 재귀호출
            return "(" + correctSameString(arr[1]) + ")" + "\(cs)"
        }
    }
}

// 문자열을 두개의 올바른 괄호문자열로 나눈다.
func divideString(s: String) -> [String] {
    var str = s
    var leftStr = ""
    var rightStr = ""
    for i in 1...str.count/2 {
        var index = i * 2
        leftStr = String(str.prefix(index))
        rightStr = String(str.suffix(str.count - index))
        if isSameCountString(leftStr) && isSameCountString(rightStr) {
            return [leftStr, rightStr]
        }
    }
    return [leftStr, rightStr]
}

// 균형잡힌 문자열인지 판단
func isSameCountString(_ p: String) -> Bool {
    var str = p
    var count = 0
    for i in str {
        if i == "(" {
            count += 1
        } else if i == ")" {
            count -= 1
        }
    }
    
    if count != 0 {
        return false
    } else {
        return true
    }
}

// 올바른 문자열인지 판단
func isCorrectString(_ p: String) -> Bool {
    var stack = [String]()
    for i in p {
        switch i {
            case "(":
            stack.append("(")
            case ")":
            if !stack.isEmpty {
                stack.removeLast()
            }
            default:
            continue
        }
    }
    if stack.isEmpty {
        return true
    } else {
        return false
    }
}