Optimal Partition of String - LeetCode

<내 풀이>

class Solution:
    def partitionString(self, s: str) -> int:
        new = []
        count = 1
        for i in s:
            if i not in new: 
                new.append(i)
            else: 
                count+=1
                new= [i]
        
        return count

쉬운 그리디 문제지만 count를 정확히 하는 것이 조금 헷갈렸다. 

일단 맨 처음에 count는 0이 아니라 1에서 시작한다. 

계속해서 겹치는 문자가 안 나와서 그대로 끝나더라도 substring이 0이 아니라 1개는 되는 것이다. 

그리고 new 배열에 문자를 차례대로 쌓아가다가,

겹치는 문자가 나올 때마다 일단 새로운 substring을 만들어야 하니까 

count에 1을 더한다. 

새로운 substring은 처음에는 new를 빈 배열로 초기화하는 걸로 만들었는데, 

그게 아니라 new에 방금 전에 겹친 문자열 딱 하나 들어가도록 초기화하고 다음 문자로 넘어가야 한다. 

끗

Reduce Array Size to The Half - LeetCode

<내 풀이>

from collections import Counter
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        res = 0
        counter = Counter(arr)
        counter = counter.most_common()

        for i in range(len(counter)):
            res += counter[i][1]
            if res >= (len(arr)//2):
                break

        return i+1

힙 문제라고 적혀 있었지만 그냥 딕셔너리 이용해서 빈도 순 정렬 해서 푸는 것도 시간복잡도상 큰 차이를 보이지 않는다. 

힙으로 하면 더 복잡해질 것도 같다. 

<Counter 함수>

num_list = [1, 2, 3, 4, 4, 4]
My_num_dict  = Counter(num_list)
라고 하면 

결과: Counter({4: 3, 1: 1, 2: 1, 3: 1})


My_num_dict = dict(Counter(num_list))
라고 하면

결과: {4: 3, 1: 1, 2: 1, 3: 1}
이렇게 깔끔한 딕셔너리만 나오게 된다.

딕셔너리를 등장 횟수 순, 즉 키/값 중 값(value) 순으로 정렬하고 싶을 때,

두 가지 방법을 쓸 수 있다. 


1. sorted 안에서 lambda 함수로 정렬의 기준을 정해주기

람다 함수 사용 방법을 자꾸 까먹는데 value 값이 아니라 key 값을 기준으로 정렬해야 할 때도 있어서 꼭 익숙해져야 한다. 

sorted_list = sorted(counter.items(), key=lambda x: -x[1])

sorted_list = sorted(counter.items(), reverse = True, key = lambda x: x[1])

내림차순으로 정렬하고 싶은 거니까, 
원래 오름차순으로 정렬되는 sorted() 함수에 reverse=True 옵션을 먹이거나, 

람다 함수에서 매개변수에 - 붙인 값을 주면 된다. 그러면 절댓값이 높은 음수가 앞으로 가게 되니까 결국 내림차순 정렬 하는 것과 같은 효과를 준다고 한다.

나는 그냥 reverse = True 쓰는 게 더 편한 것 같다.



2. 파이썬에 내장되어 있는 Counter.most_common() 기능을 사용하기

counter 딕셔너리가 자동으로 빈도가 많은 것부터 적은 것 순으로 정렬된다. 

counter = counter.most_common()

이런 식으로 쓰면 자동 정렬됨.

Seat Reservation Manager - LeetCode

• 1 <= n <= 10의 5제곱
• 1부터 10만까지.
• 1초의 시간 제한이 있다고 하고 1초에 실행할 수 있는 연산 횟수가 약 1억번이라고 할 때,  데이터의 개수(n)이 100,000이면 최대 시간복잡도가 O(nlogn)이 되도록 해야 한다.
• 힙 정렬, 퀵 정렬, 합병 정렬을 사용할 수 있다.

<내 풀이>

import heapq
class SeatManager:
    def __init__(self, n: int):
        self.h = []
        for i in range(1, n+1):
            self.h.append(i)
        self.res = []
        self.res.append('null')

    def reserve(self) -> int:
        a= heapq.heappop(self.h)
        self.res.append(a)
        return a
        
    def unreserve(self, seatNumber: int) -> None:
        b = heapq.heappush(self.h, seatNumber)
        self.res.append('null')

        


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

• heapq 모듈의 heapq.heappop, heapq.heappush를 이용했다.

• 세 개의 함수에서 모두 h, res 배열을 사용해야 함. 공통으로 클래스 인스턴스를 참조하기 위해서 self를 사용했다.
• self.h, self.h를 __init__ 함수에서 정의하고, 클래스 내의 메서드들에서 인스턴스 변수에 접근하거나 다른 메서드를 호출할 때 사용한다. 

Removing Stars From a String - LeetCode

class Solution:
    def removeStars(self, s: str) -> str:
        s = list(s)
        q= []
        for i in s:
            if i =='*':
                q.pop()
            else: q.append(i)
        res=''
        for j in q:
            res+=(j)
        return res

더 간단하게 하는 방법이 있을까??

<남의 풀이에서 배운 점: 리턴 간단하게 하는 법!>

return "".join(q)

''.join(리스트이름) 

Flatten Nested List Iterator - LeetCode

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.q = []
        self.flatten(nestedList)

    def flatten(self, nl):
        for i in nl:
            if i.isInteger():
                self.q.append(i.getInteger())
            else: self.flatten(i.getList())   #재귀함수
            
    def next(self) -> int: 
        return self.q.pop(0)

    def hasNext(self) -> bool:
        if self.q:
            return True
        else: 
            return False


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

리액트에서는 사용하는 데이터를 부모로부터 자식에게, 즉 위에서 아래로 props를 통해서 전달한다. 

context 기능을 사용하면 트리 단계마다 명시적으로 props를 넘겨주지 않아도, 많은 컴포넌트가 Global하게 데이터를 공유할 수 있다. 특히 컴포넌트가 다양한 레벨에서 쓰일 때 context로 데이터를 전달하면 좋다. 대신 context를 사용하면 컴포넌트를 재사용하기 어려워진다.

예를 들면 어떤 데이터를 전역데이터로 만들어야 할까?

현재 로그인 한 유저, 테마, 선호하는 언어 등이 있다. 

지금 만드는 페이지에서는 메뉴 정도 그렇다.

<리액트 공식 문서의 예시 코드>

// 버튼 컴포넌트의 'dark' 테마 props를 명시적으로 넘겨주는 코드

class App extends React.Component {
  render() {
    return <Toolbar theme="dark" />;
  }
}

function Toolbar(props) {
  //Toolbar 컴포넌트가 테마 props를 받아서 ThemeButton에 전달하는 과정.
  //모든 버튼에 대해서 이렇게 해야한다면 매우 곤혹스러울 것이다.
  return (
    <div>
      <ThemeButton theme={props.theme} />
    </div>
  );
}

class ThemeButton extends React.compoenet {
  render() {
    return <Button theme={this.props.theme} />;
  }
}

↓ ↓ ↓ ↓ ↓ ↓ ↓

// context를 활용해서 'light' 테마 context를 만드는 코드. 이 테마를 어떤 컴포넌트에든 쉽게 적용할 수 있게 된다.

const ThemeContext = React.createContext("light");

class App extends React.Component {
  render() {
    return (
      <ThemeContext.Provider value="dark">
        <Toolbar />
      </ThemeContext.Provider>
    );
  }
}

function Toolbar() {
  return (
    <div>
      <ThemedButton />
    </div>
  );
}

class ThemedButton extends React.Component {
  static contextType = ThemeContext;
  render() {
    return <Button theme={this.context} />;
  }
}
//현재 선택된 테마 값을 읽기 위해서 가장 가까이 있는 provider의 값을 사용한다. (여기서는 dark)

컨텍스트 객체를 API로 만드는 방법

React.createContext

const StoreContext = React.createContext(defaultValue);

--> defaultValue는 트리 안에서 적절한 provider를 찾지 못한 경우에만 쓰인다. 

<MyContext.Provider value = {/* 어떤 값 */}>

--> Context오브젝트에 포함된 Provider라는 컴포넌트이다. 

Provider는 context 내용이 바뀌는 것을 이 컨텍스트를 구독하는 컴포넌트틀에게 전달해준다. 
Value로 받은 "어떤 값" 이 바뀌는 부분이다. 

Provider 하위에서 이 컨텍스트를 구독하는 모든 컴포넌트는 value prop이 바뀔 때마다 다시 렌더링된다. 

Top K Frequent Elements - LeetCode

<내 풀이>

from collections import Counter

class Solution:
    def topKFrequent(self, nums:List[int], k:int) -> List[int]:
        numDict = dict(Counter(nums))
        countlist = sorted(numDict.items(), reverse = True, key = lambda x: x[1])
        res=[]
        for i in range(k):
            res.append(countlist[i][0])
        return res

정렬, 딕셔너리로 풀기. 

key = lambda x: x[1] 이거는 왜 이렇게 안 익숙해질까.. 헣

#자전거 도로 연결하는 거 숫자만 바꿀 거임

class Graph():
    def __init__(self, size):
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g):
    print(' ', end=' ')
    for v in range(g.SIZE) : 
        print("%9s" %nameAry[v], end=' ')
    print()
    for row in range(g.SIZE):
        print("%9s" %nameAry[row], end=' ')
        for col in range(g.SIZE):
            print("%8s" %g.graph[row][col], end= ' ')
        print()
    print()

def findVertex(g, findVtx):
    stack = []
    visitedAry = []

    current = 0
    stack.append(current)
    visitedAry.append(current)

    while (len(stack) != 0):
        next = None
        for vertex in range(gSize) :
            if g.graph[current][vertex] != 0 :
                if vertex in visitedAry :
                    pass
                else: 
                    next = vertex
                    break

        if next != None:
                current = next
                stack.append(current)
                visitedAry.append(current)
        else:
            current = stack.pop()
        
    if findVtx in visitedAry : 
        return True
    else: 
        return False





gSize=6
G1 = Graph(gSize)
nameAry = ['서울', '뉴욕', '북경', '방콕', '런던', '파리']
서울, 뉴욕, 북경, 방콕, 런던, 파리 = 0, 1, 2, 3, 4, 5

G1.graph[서울][뉴욕] = 80; G1.graph[서울][북경] = 10
G1.graph[뉴욕][서울] = 80; G1.graph[뉴욕][북경] = 40; G1.graph[뉴욕][방콕] = 70
G1.graph[북경][서울] = 10; G1.graph[북경][뉴욕] = 40; G1.graph[북경][방콕] = 50
G1.graph[방콕][뉴욕] = 70; G1.graph[방콕][북경] = 50; G1.graph[방콕][런던] = 30; G1.graph[방콕][파리] = 20
G1.graph[런던][방콕] = 30; G1.graph[런던][파리] = 60
G1.graph[파리][방콕] = 20; G1.graph[파리][런던] = 60

print("## 해저 케이블을 위한 전체 연결도 ##")
printGraph(G1)

edgeAry = []
for i in range(gSize):
    for k in range(gSize):
         if G1.graph[i][k] != 0 :
            edgeAry.append([G1.graph[i][k], i, k])

from operator import itemgetter
edgeAry = sorted(edgeAry, key = itemgetter(0), reverse= False)

newAry = []
for i in range(0, len(edgeAry), 2) :
    newAry.append(edgeAry[i])

index = 0
while (len(newAry) > gSize-1):
    start = newAry[index][1]
    end = newAry[index][2]
    saveCost = newAry[index][0]

    G1.graph[start][end] = 0
    G1.graph[end][start] = 0

    startYN = findVertex(G1, start)
    endYN = findVertex(G1, end)

    if startYN and endYN:
        del(newAry[index])
    else: 
        G1.graph[start][end]= saveCost
        G1.graph[end][start]= saveCost
        index += 1

print('## 가장 효율적인 해저 케이블 연결도 ##')
printGraph(G1)