[백준/Ruby] 2800번: 괄호 제거

문제

https://www.acmicpc.net/problem/2800

아래 예제와 같이 올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전순으로 출력하는 문제이다.

풀이 과정

올바른 괄호쌍을 제거하는건 Stack 자료구조를 사용하면 간단히 해결할 수 있다. 문제는 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 어떻게 구하느냐였다.

예제 출력 3을 보면 규칙을 파악할 수 있는데, 괄호가 하나 제거된 경우 -> 두 개 제거된 경우 -> 세 개 제거된 경우 순으로 출력된다.

이때 조합을 사용하면 괄호쌍을 제거해서 나올 수 있는 서로 다른 식을 하나도 빠짐없이 구할 수 있다는 것을 알 수 있다.

풀이

조만간 Ruby로 라이브 코딩테스트가 예정되어 있는 관계로 이번 풀이는 루비로 진행해보았다.

• count
  • 입력받은 수식에 존재하는 괄호쌍의 개수를 의미한다.
• findPair()
  • 입력받은 수식에서 알맞은 괄호쌍들을 찾아낸다.
  • Stack 자료구조의 특성을 활용했다.
• combination 활용부
  • findPair()에서 찾아낸 괄호쌍들에 대해, 1부터 count 까지의 개수만큼 조합을 구한다.
  • 아래처럼 알맞은 괄호쌍들의 인덱스가 조합으로 구성되어 있는 것을 확인할 수 있다.

  [[[6, 10]], 
  [[3, 11]], 
  [[0, 12]], 
  [[6, 10], [3, 11]], 
  [[6, 10], [0, 12]], 
  [[3, 11], [0, 12]], 
  [[6, 10], [3, 11], [0, 12]]]

• output()
  • 입력받은 수식에 대해서, 위 조합을 한줄씩 순회하며 괄호쌍과 일치하는 인덱스이면 pass하고, 일치하지 않으면 수식으로 출력하기 위해 result 배열에 저장한다.
• 사전순 정렬
  • 조합으로 구한 모든 수식은 result 배열에 담겨 있다.
  • 문제 출력 조건을 만족하기 위해, 이 배열을 정렬하는 과정이 필요하다.

def findPair(input)
  tmp = []
  stack = []

  for i in 0...input.length do
    if input[i] == "("
      tmp.push(i)
    elsif input[i] == ")"
      open = tmp.pop()
      close = i
      stack.push([open, close])
    end
  end
  return stack
end

def output(input, arr)
  result = []

  arr.each do |pair|
    idx = Array.new(input.length, 0)

    pair.each do |a, b|
      idx[a] = 1
      idx[b] = 1
    end

    ans = ""
    for i in 0...input.length do
      if idx[i] == 1
        next
      end
      ans += input[i]
    end
    result << ans
  end

  return result
end

input = gets.chomp
count = input.count("(")
stack = findPair(input)

comb = []
for i in 1..count do
  comb.concat(stack.combination(i).to_a)
end

result = output(input, comb)
result.uniq.sort.each {|result| puts result}

사담

조건문, 반복문 끝날 때마다 end 붙여줘야 되는거 진짜 열받는다..