TIL38 | CodeKata 숫자 중에서 과반수가 넘은 숫자 찾기, 여러 괄호 규칙 짝 맞추기

CodeKata Week 2

1주차보다 문제가 좀 더 어려워진 것 같다.

 

문제 2

숫자로 이루어진 배열인 nums를 인자로 전달합니다.

숫자 중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

def more_than_half(nums):
  # 구현

input

nums = [3,2,3]
nums = [2,2,1,1,1,2,2]

output

3
2

 

나의 풀이

각 요소별 count 비교

def more_than_half(nums):
  set_list = set(nums)
  result, count = 0, 0

  for i in set_list:
    if count < nums.count(i):
      result = i
      count  = nums.count(i)

  return result

nums = [2,2,1,1,1,2,2]  
more_than_half(nums)

• set 함수 사용해서 중복을 제외한 숫자 리스트를 생성한다.

• 결과값을 반환할 변수 result 변수와 중복 개수를 가지는 count 변수를 선언한다.

• set_list를 순회하며 nums 배열에서 해당 요소의 개수를 구하고, 개수가 현재 count에 들어있는 수보다 크다면 result와 count의 값을 업데이트 한다.

 

정렬 후 가운데 요소 도출

# 과반수이기 때문에 리스트를 반으로 나눠서 가운데 있는 숫자를 반환해도 됨.
def more_than_half(nums):
  return sorted(nums, reverse=True)[len(nums)//2]

• 위와 같이 간단하게 작성할 수 도 있다.

 

문제 3

s는 여러 괄호들로 이루어진 String 인자입니다. s가 유효한 표현인지 아닌지 true 또는 false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.

한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다. 괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

def is_valid(string):
  # 구현

 

input

s = "(]"
s = "([)]"
s = "{[]}"

output

false
false
true

 

나의 풀이

replace()

def is_valid(string):  s = string  while len(string) > 0:    s = s.replace('()', '').replace('[]','').replace('{}','')    if len(s) == 0 or len(s) == len(string): break  return True if len(s) == 0 else False

아이디어

열린 괄호와 닫힌 괄호를 비교해서 문제를 풀려고 했을 때 ([)] 문자열을 어떻게 처리할 수 있을까 고민했다.

[{}] 이 문자열과 비교해서 생각했을 때, 짝이 맞는 괄호는 비교대상에서 제외시키면 확인해야 할 문자가 줄어들겠다고 생각했다.

그래서 replace() 함수를 떠올렸고, 코드로 작성했다.

• 괄호들을 빈문자열로 대체하는 과정을 반복해야 했기 때문에 while loop를 사용했다.

• while 루프 안에서 replace() 함수를 사용해서 짝지어진 괄호들( (), [], {} )을 빈 문자열('') 로 대체한다.

• 만약 s 변수의 길이가 더이상 대체할 문자열이 없는 빈 문자열이거나 replace() 함수를 쓰고도 처음 받은 문자열인 string과 동일하다면, 루프를 빠져나온다.

• s 문자열의 길이가 0이라면 True를, 0보다 크다면 False를 반환한다.

 

+ 재원님 풀이

Dictionary

def is_valid(string):    bracket = {"(": ")", "{": "}", "[": "]"}    for k,v in bracket.items():       if string.count(k) != string.count(v):        return False    res = []    for i in string:      if i in bracket:        res.append(i)      elif len(res) == 0 or bracket[res.pop()] != i:         return False      if len(res) == 0:      return True      s = "{(())[]}()"print(is_valid(s)) # True

• 열린 괄호는 Key, 닫힌 괄호는 Value로 한 Dictionary를 선언한다.

• Key와 Value의 개수가 맞지 않으면 짝이 맞지 않는 것이므로 곧바로 False를 반환한다.

• 열린 괄호와 닫힌 괄호의 개수가 맞다면,

  • string 을 순회하면서 열린 괄호인 경우에는 res 배열에 넣어주고, 닫힌 괄호라면 bracket 배열에 없기 때문에
    elif문 len(res) == 0 or bracket[res.pop()] != i 을 타게 된다.
  • res.pop() 으로 나온 열린 괄호를 bracket의 Key로 사용한다.
  • bracket[res.pop()]의 Value가 닫힌 괄호와 같은 값이라면 다음요소를 순회하고, 다른 값이라면 False를 반복한다.

• 위의 반복 과정을 거쳐 res 배열의 길이가 0 이 된다면 True를 반환하다.