괄호회전하기

LEEHAKJIN-VV·2022년 6월 9일
algorithmprogrammersstackswift
0

프로그래머스

목록 보기
19/37

출처: 프로그래머스 코딩 테스트 연습

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • s의 길이는 1 이상 1,000 이하입니다.

입출력 예

Nresult
"{}"3
"}]()[{"2
"[)(]"0
"}}}"0

입출력 예 설명

입출력 예 #1

  • 다음 표는 "{}" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0"{}"O
1"](){}["X
2"(){}[]"O
3"){}[]("X
4"{}"O
5"}{"X

[3,4,2,1,5]

입출력 예 #2

  • 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0"}]()[{"X
1"]()[{}"X
2"()[{}]"O
3")[{}]("X
4"{}"O
5"{}]()["X
  • 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

  • s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

  • s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

내가 제출한 코드

import Foundation

struct Stack<T> {
    private var items = [T]()
    
    public mutating func push(_ item: T) {
        items.append(item)
    }
    public mutating func pop() -> T? {
        return items.popLast()
    }
    public func peek() -> T? {
        return items.last
    }
    public func isEmpty() -> Bool {
        return items.isEmpty ? true : false
    }
}

// (2회전 -> 1회전 +1회전, 3회전 -> 2회전 + 1회전 -> 1회전+1회전+1회전)
func solution(_ s:String) -> Int {
    var result = 0
    if s.count <= 1 { // 길이가 1이하 -> 올바른 괄호 x
        return result
    } 
    var bracketArray: [String] = s.map{ String($0) } // 괄호 문자열 배열
    
    if correctBracket(bracketArray) { // 0칸 회전
        result += 1
    }
    
    for _ in 1..<s.count { // 1 ~ n-1칸 회전
        let removeBracket = bracketArray.removeFirst()
        bracketArray.append(removeBracket)
        if correctBracket(bracketArray) {
            result += 1
        }
    }  
    return result
}
// true 반환 -> 올바른 괄호, false 반환 -> 올바른 괄호 X
func correctBracket(_ data: [String]) -> Bool {
    var bracketInfo: [String:Int] = ["(": 1, ")": -1, "[": 2, "]": -2, "{": 3, "}": -3] // 괄호 정보
    var bracketStack = Stack<String>() // 괄호 스택
    var top = 0 
    
    while top < data.count { // 배열의 모든 괄호를 읽을때 까지 반복
        if let bracket = bracketInfo[data[top]] { // 읽은 괄호
            if bracket < 0 { // 음수 -> 닫는 괄호
                if let popItem = bracketStack.peek() { // 스택에서 꺼낸 괄호
                    if abs(bracket) == abs(bracketInfo[popItem]!) { // 괄호 쌍이 맞으면 스택에서 꺼냄
                        _ = bracketStack.pop()
                    } else { return false } // 괄호쌍이 맞지 않는 경우
                } else { return false } // 여는 괄호 없이 닫는 괄호가 온 경우
            } else { bracketStack.push(data[top]) } // 여는 괄호는 스택에 저장
        }
        top += 1
    }
    return bracketStack.isEmpty() ? true : false // 스택이 비었으면 올바른 괄호
}

코드 설명

문제는 이전에 풀었던 괄호변환 문제와 비슷하다. 그러나 차이점은 이전 문제에서는 "()"인 소괄호만 입력으로 주어졌다면 이번 문제에서는 3가지 종류의 괄호를 모두 사용한다. 그러므로 Int 값의 변화로 올바른 괄호를 판단하는 것이 아닌 스택을 사용한다.

그러면 코드를 세부적으로 살펴본다.

 if correctBracket(bracketArray) { // 0칸 회전
        result += 1
    }

우선 문제는 괄호를 왼쪽으로 x 칸만큼 회전한 문자열을 올바른 괄호인지 판별해야 한다. 그러므로 회전하기 전에 처음 문자열이 올바른지 확인하기 위해 0칸 회전 코드를 구현하였다. correctBracket 메소드는 문자열이 올바른 괄호인지 판별하는 함수이다.

다음으로 문자열을 x 칸 만큼 회전하는 코드이다.

for _ in 1..<s.count { // 1 ~ n-1칸 회전
        let removeBracket = bracketArray.removeFirst()
        bracketArray.append(removeBracket)
        if correctBracket(bracketArray) {
            result += 1
        }
    }

우선 회전은 문자열 삽입과 삭제로 구현하였다. 즉 배열의 첫문자 1개를 제거하고 제일 마지막에 추가하는 것은 1칸 만큼 회전하는 효과와 동일하다. 이를 반복문을 통해 (0 ≤ x < (s의 길이))만큼 회전하여 올바른 괄호인지 판별한다.

다음으로 괄호 문자열이 올바른지 판별하는 함수이다.

func correctBracket(_ data: [String]) -> Bool {
    var bracketInfo: [String:Int] = ["(": 1, ")": -1, "[": 2, "]": -2, "{": 3, "}": -3] // 괄호 정보
    var bracketStack = Stack<String>() // 괄호 스택
    var top = 0 
    
    while top < data.count { // 배열의 모든 괄호를 읽을때 까지 반복
        if let bracket = bracketInfo[data[top]] { // 읽은 괄호
            if bracket < 0 { // 음수 -> 닫는 괄호
                if let popItem = bracketStack.peek() { // 스택에서 꺼낸 괄호
                    if abs(bracket) == abs(bracketInfo[popItem]!) { // 괄호 쌍이 맞으면 스택에서 꺼냄
                        _ = bracketStack.pop()
                    } else { return false } // 괄호쌍이 맞지 않는 경우
                } else { return false } // 여는 괄호 없이 닫는 괄호가 온 경우
            } else { bracketStack.push(data[top]) } // 여는 괄호는 스택에 저장
        }
        top += 1
    }
    return bracketStack.isEmpty() ? true : false // 스택이 비었으면 올바른 괄호
}

bracketInfo 프로퍼티는 괄호에 관한 정보를 저장하는 딕셔너리 프로퍼티이다. 이 프로퍼티는 다중 if문 사용(예: if tmp == ")")의 사용을 피하기 위해 사용한다. 올바른 괄호란 여는 괄호와 닫는 괄호의 쌍이 맞아야 한다. 3가지 종류의 괄호를 구분하기 위해 각 괄호의 쌍의 절댓값은 같으나 부호가 다르게 구현하였다.

괄호를 판별하는 과정에 관해 간단하게 설명한다.

  • 여는 괄호가 입력되면 스택에 저장한다.
  • 닫는 괄호가 입력되면 스택에 있는 괄호와 비교한다.
    • 스택에 있는 괄호와 입력된 닫는 괄호의 쌍이 같으면 스택에 있는 괄호를 pop 한다.
    • 스택에 있는 괄호와 입력된 닫는 괄호의 쌍이 다르면 이는 올바르지 않은 괄호 문자열이므로 false를 반환한다.
  • 위 과정을 입력으로 주어진 문자열을 끝까지 읽을 때까지 반복한다.
  • 반복문이 종료된 후 스택에 괄호가 남아 있으면 올바르지 않은 괄호 문자열이다.
  • 반복문이 종료된 후 스택이 비어있으면 올바른 괄호 문자열이다.

몰랐던 사실 or 기억하면 도움이 될 만한 사실

Swift의 스택 사용법

struct Stack<T> {
    private var items = [T]()
    
    public mutating func push(_ item: T) {
        items.append(item)
    }
    public mutating func pop() -> T? {
        return items.popLast()
    }
    public func peek() -> T? {
        return items.last
    }
    public func isEmpty() -> Bool {
        return items.isEmpty ? true : false
    }
}

코드에 대한 생각

correctBracket 메소드의 while 문을 보면 조건문이 deep 한것을 확인할 수 있다. 이는 소프트코딩을 위해 사용한 괄호 정보 프로퍼티 bracketInfo을 선언하고, optional unwrapping을 했기 때문이다. 이 프로퍼티를 사용하지 않고 단순한 조건문으로 사용하면 코드의 deep이 낮아질 수 있으나 괄호 정보가 변경될 시 문제가 있다고 생각한다. 그리고 optional unwrapping 또한 deep을 증가시키는 요인이 되는데 error를 방지하기 위해서 불가피하다. 코드의 deep과 코드의 간결성 사이를 적절하게 조절하는 것이 어렵다고 느낄 수 있었다. 이 2가지를 적절하게 traid-off 하는 코드를 작성하도록 노력해야겠다.

profile
LEEHAKJIN-VV
이전 포스트

기능개발

다음 포스트

프린터

0개의 댓글