[프로그래머스] 쇠막대기 (Level 2, Python)

 

온라인에서 코딩테스트 문제를 풀 수 있는 프로그래머스의 Level2 쇠막대기 문제.

(https://programmers.co.kr/learn/courses/30/lessons/42585)

 

 

 

문제 설명

 

해당 문제는 끝 점이 겹치지 않는 쇠막대기를 아래에서 위로 겹친 후 레이저를 위에서 수직으로 발사하여 쇠막대기를 자르는 문제이다.

반환 값(answer)은 잘린 쇠막대기의 총 개수이다.

 

문제의 조건은 다음과 같다.

 

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

다음은 입력(input)에 대한 설명이다.

 

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현한다. 또한 모든 '()'는 반드시 레이저를 표현한다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.

 

 

처음 문제를 읽었을 때는 조금 난해한 문제가 아닐까 했지만 그림을 보니 쉬운 문제라는 것을 알 수 있었다.

 

그림을 보면 알 수 있듯 괄호 쌍은 레이저를 표현하며, 쇠막대기는 여는 괄호와 닫는 쌍으로 표현된다.

 

나는 쇠막대기의 양 끝점이 겹치지 않는 다는 점과 레이저가 쌓인 쇠막대기의 수직 방향에서 발사된다는 것을 이용했다.

 

먼저 쇠막대기의 양 끝점이 겹치지 않기 때문에 여는 괄호를 통해 쇠막대기의 개수를 구할 수 있다. (괄호쌍 제외)

 

그리고 괄호쌍이 들어오면 레이저는 수직으로 발사되기 때문에 쇠막대기의 개수 만큼 잘린 조각이 생긴다. 쇠막대기의 개수 만큼 잘린 조각을 세는 이유는 반대편 끝점이 존재하기 때문에 시작점 방향에서 잘려 나간 조각만 계산하면 되기 때문이다.

 

그리고 닫는 괄호가 나타나면 쇠막대기의 개수를 하나 빼고 잘린 조각을 하나 더한다.

 

 

작성한 코드는 다음과 같다.

 

def solution(arrangement):
  answer = 0 # 잘린 쇠막대기의 총 개수
  arrangement = list(arrangement)
  bong = 0 # 쇠막대기 개수

  while arrangement:
    if arrangement[0] == "(": # 여는 괄호
      bong += 1
      arrangement.pop(0)
      if arrangement[0] == ")": # 괄호쌍 일 경우
        bong -= 1
        answer += bong
        arrangement.pop(0)
    else: # 닫는 괄호
      arrangement.pop(0)
      bong -= 1
      answer += 1

  return answer

 

 

 

마무리

 

해당 문제는 사실 누가봐도 스택을 사용해서 풀라고 만든 문제이다.

 

나도 처음에 스택을 이용해서 문제를 풀었지만 코드를 제출한 후  다른 사람의 풀이를 보니 이미 대부분이 스택을 활용해서 다양한 코드를 작성했다. (프로그래머스 사이트는 정답을 제출해야 다른 사람의 코드를 볼 수 있다.)

 

하지만 재밌는 문제인거 같아서 블로그에 포스팅을 하려고 보니 다른 사람과 비슷한 풀이를 올리는 것은 의미가 없을 것 같았다. 그래서 스택을 사용하지 않고 단순하고 직관적인(?) 코드를 작성했고, 실제로 스택을 사용한 다른 사람들의 코드와 실행 시간을 비교해보니 비슷하거나 최대 5배 정도 빨랐다.

 

입력 값이 크지 않은 케이스로 비교했기 때문에 크게 의미있는 차이는 아니지만 시간이 된다면 다양한 방법으로 문제를 풀어보는 것도 재밌는 것 같다.

 

---

 

 

 

안녕하세요. 평범한 대학생 개발자 yorr입니다.

포스팅을 읽고 궁금한 점 또는 문의가 있으신 분은 메일 또는 댓글을 남겨주세요.

 

Mail: twysg@likelion.org

Github: https://github.com/sangyeol-kim