시간에 쫓기고, 뭔가 꼭 정답을 생각해 내야된다는게 좋은게 아닌걸아는데.. 나는 매번 정답을 못 맞추는 내가 바보같다는 자괴감이 들더라 ㅠㅠ

-DAY4-

<문제>
nums는 숫자로 이루어진 배열입니다.
가장 자주 등장한 숫자를 k 개수만큼 return해주세요.

예를 들면
nums = [1,1,1,2,2,3],k = 2
->return [1,2]
nums = [1],k = 1
->return [1]

접근방법

처음에 나는 각 수를 count해서 가장 높은 순서인 애들을 k만큼 불러올까라고 생각을했다.

def top_k(nums, k):
  dic = {}
  for i in nums:
    if i not in dic:
      dic[i] = 1
    else:
      dic[i] += 1

여기서 막혀버림... 가장 높은 순서를 뽑아내는걸 찾다가 most_common과 Counter함수가 있다는걸 민철님한테 듣고 사용했다.

from collections import Counter

def top_k(nums, k):
  a = Counter(nums)
  b = a.most_common(k)
  
  c = []
  for i in range(k):
    c.append(b[i][0])
  return c

몇가지 새로운 개념이 나와서 한번 정리해 보겠다

<collections 모듈 - Counter>

컨테이너에 동일한 값의 자료가 몇개인지 파악하는데 사용된다.
<입력값>
1.리스트의 요소개수를 collections.Counter()를 이용하면 Dictionary형태로 반환한다.

import collections
lst = ['aa', 'cc', 'dd', 'aa', 'bb', 'ee']
print(collections.Counter(lst))
#결과
Counter({'aa': 2, 'cc': 1, 'dd': 1, 'bb': 1, 'ee': 1})

2.딕셔너리의 경우 동일하게 딕셔너리 그대로 반환되며 value의 값이 많은 것 부터 출력해준다.

3."값=개수"형태도 입력이 가능하다. 예를들어, collections.Counter(a=2, b=3, c=2)는
['a', 'a', 'b', 'b', 'b', 'c', 'c']와 같다.
결과는{'b': 3, 'c': 2, 'a': 2}로 나온다.

4.문자열(String)은 {문자:개수}의 딕셔너리 형태로 반환된다.

<most_common메서드>

보통의 경우, 주어진 단어에서 가장 많이 등장하는 알파벳과 그 알파벳의 개수를 구하는 함수는 다음과 같이 작성한다.

from collections import Counter

def find_max(word):
    counter = Counter(word)
    max_count = -1
    for letter in counter:
        if counter[letter] > max_count:
            max_count = counter[letter]
            max_letter = letter
    return max_letter, max_count

알파벳의 개수가 많은 순서대로 정렬해 리턴해주는 함수도 존재하는데 Counter안에 포함이 되어있다(개이득👍)

from collections import Counter

Counter('hello world').most_common()

#결과값
#[('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

most_common()의 ()괄호에 숫자를 넣으면 그 숫자만큼의 데이터만 뽑아 낼 수도 있다!

Solution

def top_k(nums, k):
    count = {}
    for n in nums:
        count[n] = count.get(n, 0) + 1
    bucket = [[] for _ in range(len(nums)+1)]
    for n, freq in count.items():
        bucket[freq].append(n)
    ret = []
    for n_list in bucket[::-1]:
        if n_list:
            ret.extend(n_list)
            if len(ret) == k:
                return ret

-DAY5-

<문제>
인자인 height는 숫자로 이루어진 배열입니다.
그래프로 생각한다면 y축의 값이고, 높이 값을 갖고 있습니다.
아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.

저 그래프에 물을 담는다고 생각하고,
물을 담을 수 있는 가장 넓은 면적의 값을 반환해주세요.
(가정 : 배열의 길이는 2이상입니다.)

접근방법

문제를 본 순간의 나 : ?????????
동기님 고맙습니다..
진짜.. 문제이해를 못해서 접근을 못하는 한주였다 ㅠㅠ 나는 바보..ㅠㅠㅠ

def get_max_area(height):
  answer=[]
  for i in range(len(height)):
      for j in range(i+1,len(height)):
          square=(j-i)*min(height[i],height[j])
          answer.append(square)
  return max(answer)

먼저 빈리스트를 만들고 높이를 구하기위해 for loop를 사용했다. 면적을 경우의 수별로 다 만든뒤 list에 넣는 방식으로 접근했다
이번에는 수월하게 처리했는데!! 모범답안을 보고 새로운 걸 생각해 볼 수 있게 되었다.

Solution

def get_max_area(height):
	l = 0
	r = len(height) -1
	area = 0
	while l < r: 
		area = max(area, min(height[l],height[r]) * (r - l))
		if height[l] < height[r]: 
			l += 1
		else:
		    r -= 1
	return area

함께 답안을 본 동기분들과 이야기하며 깨달은 점이 있다.
단순히 정답을 부르는게 아니라 좀더 컴퓨터적 입장에서 볼경우
for loops를 두번 사용하는게 시간이 오래걸리는 구문이 된다는 점이다. 알고리즘이란게 이런거구나~ 라는 생각이 들던 시간이였다.

다음주도 화이팅!!🔥🔥🔥🔥