블로그 이사했습니당~ 위 주소로 오세요!!

📛 문제에 있는 오류!!

• 테스트 27번에 E#이 존재한다!
• 양 옆에 `가 붙지 않은 None을 반환 해야한다.

  🎅 문제 풀이 아이디어

  

🎄 전체 코드

def control(m):
    return m.replace('C#','c').replace('D#','d').replace('F#','f').replace('G#','g').replace('A#','a')

def solution(m, musicinfos):
    answer = []
    m = control(m)
    for i in musicinfos:
        start, end, name, s = i.split(",")
        n = abs((int(start[:2])*60 + int(start[3:])) - (int(end[:2])*60 + int(end[3:])))
        s = control(s)
        music = ''
        for j in range(n):
            music += s[j%len(s)]
        if music.find(m) != -1:
            answer.append((name, n))
    if not answer:
        return "(None)"
    answer.sort(reverse=True, key = lambda x: x[1])
    return answer[0][0]

👀 문제 풀이 아이디어

👀 전체 코드

from collections import deque
from itertools import combinations

def solution(relation):
    n = len(relation)
    m = len(relation[0])
    answer = 0

    # 가능한 모든 조합 구하기
    com = []
    for i in range(1,m+1):
        com.extend(list(combinations(range(m), i)))

    # 유일성 만족하는 키 찾기
    keys = deque()
    for i in com:
        temp = ['' for _ in range(n)]
        for idx1, j in enumerate(i):
            for idx2,k in enumerate(relation):
                temp[idx2] += k[j]
        if len(set(temp)) == n:
            keys.append(i)

    # 최소성 만족하는 키 찾기 
    while keys:
        temp = keys.popleft()
        answer += 1
        new = deque()
        for i in keys:
            if len(set(i)-set(temp)) != len(i)-len(temp):
                new.append(i)
        keys = new
    return answer

✨구현해야 하는 기능

구현해야 하는 기능을 아래와 같이 3개로 나누고 하나씩 구현하니까 코드가 더 간단하고 구현하기도 더 수월했다.

(1) 4개씩 붙어 원소 찾기

def check(m,n,board):
    isChange= False
    temp = [[0]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            if board[i][j]== board[i-1][j] == board[i][j-1] ==board[i-1][j-1] != '0':
                isChange = True
                temp[i][j] = temp[i-1][j] = temp[i][j-1] = temp[i-1][j-1] =1
    return temp, isChange

isChange는 (3)에서 변화가 없으면 반복을 중단하기 위한 boolean값이다.

(2) (1)에서 찾은 값을 바탕으로 board 변경

def reboard(m ,n, board, temp):
    newboard = [['0']*n for _ in range(m)]
    cnt = 0
    for j in range(n):
        i = k = m-1
        while i >= 0:
            if temp[i][j] == 1:
                cnt += 1
                i -= 1
            else:
                newboard[k][j] = board[i][j]
                k -= 1
                i -= 1
    return newboard, cnt

cnt는 변경한 값이 몇 개인지 계산해서 answer에 더하기 위한 변수이다.

(3) (1)~(2)반복

변화가 없을 때 까지 (4개씩 붙어있는 같은 값이 없을 때 까지) (1)~(2)를 반복한다.

🎄 전체 코드

def check(m,n,board):
    isChange= False
    temp = [[0]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            if board[i][j]== board[i-1][j] == board[i][j-1] ==board[i-1][j-1] != '0':
                isChange = True
                temp[i][j] = temp[i-1][j] = temp[i][j-1] = temp[i-1][j-1] =1
    return temp, isChange

def reboard(m ,n, board, temp):
    newboard = [['0']*n for _ in range(m)]
    cnt = 0
    for j in range(n):
        i = k = m-1
        while i >= 0:
            if temp[i][j] == 1:
                cnt += 1
                i -= 1
            else:
                newboard[k][j] = board[i][j]
                k -= 1
                i -= 1
    return newboard, cnt

def solution(m, n, board):
    board = list(map(list, board))
    answer = 0
    isChange = True
    while isChange:
        temp, isChange = check(m ,n, board)            
        board, cnt = reboard(m ,n, board, temp)
        answer += cnt
    return answer

👀 문제 풀이 아이디어

👀 전체 코드

def solution(N):
    answer = 0
    while N > 0:
        answer += N % 2
        N //= 2
    return answer

def solution(N):
    return bin(N).count('1')

👀 문제 풀이 아이디어

• 비교 기준이 될 변수가 하나의 int값이 아니고 list로 확장해서 생각하자
• dp구조를 잊지 말자

  👀 전체 코드

  def solution(land):
    last = land[0]
    for i in land[1:]:
        temp = [0,0,0,0]
        for idx, item in enumerate(i):
            temp[idx] = item + max(last[:idx] + last[idx+1:])
        last = temp
    return max(last)

👀 문제 풀이 아이디어

👀 전체 코드

✅ indexing이 좀 헷갈리는 문제였다. 헷갈릴 땐 찍어보면서 하기!

# [0의 개수, 1의 개수]를 원소로 갖는 이차원 배열을 만드는 재귀함수
def check(s):
    n = len(s)
    if n == 1:
        return s[0][0]
    temp= [[] for _ in range(n//2)]
    for i in range(1,n,2):
        for j in range(1,n,2):
            zero = s[i][j][0] + s[i][j-1][0] + s[i-1][j][0] + s[i-1][j-1][0]
            one = s[i][j][1] + s[i][j-1][1] + s[i-1][j][1] + s[i-1][j-1][1]
            # 압축
            if one == 0: zero = 1
            if zero == 0: one = 1
            temp[i//2].append([zero, one])
    return check(temp)


def solution(arr):
    n = len(arr)
    first = [[] for _ in range(n//2)]

    # 초기 이차원 배열 만들기 
    for i in range(1,n,2):
        for j in range(1,n,2):
            temp = [arr[i][j], arr[i][j-1], arr[i-1][j], arr[i-1][j-1]]
            one = temp.count(1)
            zero = temp.count(0)
            if one == 0: zero = 1
            if zero == 0: one = 1
            first[i//2].append([zero, one])

    return check(first)

💥 어떤 문제에 어떻게 동적 프로그래밍을 이용해야 할지 막막하다면 관련 포스팅을 꼭 참고하기!

👀 왜 동적 프로그래밍(dp) 문제인가?

그 이유는 아래와 같이 크게 두 가지 이다.

1. 점점 값을 쌓아가면서 풀어야함
2. dp를 이용하지 않는다면 3중 반복문을 써야함

👀 dp를 이용한 풀이

• 2중 포문을 이용해서 원소 하나하나에 방문한다.
• ** 현재의 위치에서 가능한 최대 크기의 정사각형의 한 변의 길이**를 dp에 저장한다.
• 아래와 같은 과정을 하나씩 해보면 알겠지만 ** '현재의 위치에서 가능한 최대 크기의 정사각형의 한 변의 길이'**는 현재 위치가 [i][j]라면 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 이렇게 세 값을 비교했을 때 가장 작은 값에 1을 더한 값이다! (단, 현재 위치의 board값이 1일 때!)

👀 코드

def solution(board):
    n = len(board)
    m = len(board[0])

    # dp 준비
    dp = [[0]*m for _ in range(n)]
    dp[0] = board[0]
    for i in range(1,n):
        dp[i][0] = board[i][0]

    # 2중 포문으로 연산
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

    # 최대 넓이 구하기
    answer = 0
    for i in range(n):
        temp = max(dp[i])
        answer = max(answer, temp)

    return answer**2

# 위 코드 처럼 dp 배열을 따로 만들지 않고 board의 값을 직접 변경해가면서 값을 구해도 된다!

def solution(board):
    n = len(board)
    m = len(board[0])

    # 2중 포문으로 연산
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], dp[i][j-1]) + 1

    # 최대 넓이 구하기
    answer = 0
    for i in range(n):
        temp = max(board[i])
        answer = max(answer, temp)

    return answer**2

블로그 이사했습니다~ 위 링크로 들어오세요!

👀 타겟넘버가 왜 BFS/DFS 문제인가?

👀 deque를 이용한 BFS 풀이

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

# stack을 이용한 dfs여도 마찬가지! 
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

👀 재귀함수를 이용한 DFS 풀이

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

💡 위 코드에서 nonlocal을 처음 보신다면 관련포스팅을 참고!

useMemo(함수, [deps 배열]);
useCallback(함수, [deps 배열]);

👀 useMemo

• useMemo는 함수의 return값을 재사용하기 위한 hooks이다.

• useMemo(함수, [여기있는 값이 바뀌면 다시실행])  : 첫번째 인자로 담은 함수를 실행하고 리턴 값을 기억해둔다. deps배열에 담긴 값이 바뀌기 전까지만 기억한다.

  // 랜더링 될 때마다 아래를 실행하지만, lottoNumbers 값을 매번 바꾸고 싶지는 않다.
  const lottoNumbers = useMemo(() => getWinNumbers(), []);
  const [winNumbers, setWinNumbers] = useState(lottoNumbers);

  👀 useCallback

• useCallback은 특정 함수를 새로 만들지 않고 재사용할 때 사용한다.

• useCallback(함수, [여기있는 값이 바뀌면 다시실행])

• 함수를 자체를 기억하고 있어서 리랜더링될 때, 함수가 다시 선언되지 않는다.

• 자식 컴포넌트에 props값으로 함수를 넘길 때 그 함수는 useCallback 을 씌워주는 것이 좋다. → 쓸데없이 자식 컴포넌트가 리랜더링 되는 것을 방지한다.

• useCallBack은 반드시 첫번째 인자인 함수 내에서 변화하는 state값을 두 번째 인자(deps 배열)의 원소로 추가해 줘야한다.

  const onClickRedo = useCallback(() => {
    setWinNumbers(getWinNumbers());
    timeouts.current = [];
  }, [winNumbers]);

블로그 이사했습니다~ 위 링크로 들어오세요!

↗ 오름차순 정렬

int[] arr = {6,3,2,1,5};
String[] arr2 = {"h", "e", "a", "c"};
Arrays.sort(arr);
Arrays.sort(arr2);

↘ 내림차순 정렬

String String 타입일 때는 비교적 쉽게 내림차순 정렬이 가능하다.

Arrays.sort(arr2, Collections.reverseOrder());

int int 타입일 때는 위와 같은 방법으로 정렬할 수 없고, Integer타입 배열로 변경해 주어야 한다.

Integer[] arr3 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(arr3, Collections.reverseOrder());

정렬을 시작하는 위치와, 끝 위치를 지정하고 싶을 때

Arrays.sort(arr, 1, 3);
Arrays.sort(arr, 1, 3, Collections.reverseOrder());

ref는 DOM에 직접 접근해야할 때 사용된다. 이런 직접 접근이 필요한 경우는 아래와 같다.

• input / textare 등에 커서 조정
• DOM 의 크기를 가져와야 할 때
• DOM 에서 스크롤 위치를 가져오거나 설정을 해야 할 때
• 외부 라이브러리 (플레이어, 차트, 캐로절 등)을 사용 할 때

🧍🏻‍♂️ html input 태그에서 커서 조정

• html에서 커서 조정하는 방법은 아래와 같다. script단에서 원하는 곳에 .focus()메소드를 사용해주면 포커스가 해당 input 입력창으로 이동된다.

<script>
  var goFocus = function() { $('#input').focus(); }
</script>
...
<input type="text" id="input"/>

🚶🏻‍♂️ class Component에서 커서 조정

class LetsReact extends React.Component {
  // ref를 위한 변수 선언 
  inputRef; 
  ...
  // 커서 이동을 원할 때,
  this.inputRef.focus();

render() {
  return (
    ...
    <input ref = {(c) => {this.inputRef = c;}}/>
    ...
  );
}
}

🏃🏻‍♂️ Hooks에서 커서 조정

const LetsReact = () => {
  // ref를 위한 변수 선언 
  const inputRef = React.useRef(null);

  //  커서 이동을 원할 때,
  inputRef.current.focus();

  return (
    ... 
    <input ref = {inputRef}/>
    ...
  );

}

🎾 문제 아이디어 정리

🏈 풀이 코드

import heapq
n = int(input())
array = []
for _ in range(n):
    deadline, cupNoodle = map(int, input().split())
    array.append((deadline, cupNoodle))

array.sort()

queue = []

for i in array:
    heapq.heappush(queue, i[1])
    if i[0] < len(queue):
        heapq.heappop(queue)

print(sum(queue))

🏀 문제 아이디어 정리

⚡ 시간초과를 위해 position배열을 활용하면, 무거워서 박스를 못옮겼을 때, position을 +1해줘서 다음에는 그 박스 다음 박스부터 시행하게 한다. 때문에 박스와 크레인을 내림차순으로 정렬해줘야 한다.

🎾 풀이 코드

n = int(input())
crane = list(map(int, input().split()))
m = int(input())
box = list(map(int, input().split()))

# ⚡ 내림차순 정렬
crane.sort(reverse = True)
box.sort(reverse = True)

time = 0 # 시간
checked = [0 for _ in range(m)] # 박스를 옮겼는지 여부
count = 0 # 옮긴 박스의 개수 

positions = [0] * n

if max(box) > max(crane):
    print(-1)
else:
    while count < len(box):
        for i in range(n): # 크레인에 대하여
            while positions[i] < len(box):
            # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
                if not checked[positions[i]] and crane[i] >= box[positions[i]]:
                    checked[positions[i]] = True
                    positions[i] += 1
                    count += 1
                    break
                positions[i] += 1
        time += 1
    print(time)