바로가기

문제 풀이

풀이 1

import sys
sys.setrecursionlimit(10000)

answer = 0

def dfs(sum, cIndex, nRow, land):
    global answer

    if nRow == len(land):
        answer = max(answer, sum)
        return

    for i in range(4):
        if i == cIndex: continue
        dfs(sum + land[nRow][i], i, nRow + 1, land)

def solution(land):
    for i in range(4):
        dfs(land[0][i], i, 1, land)

    return answer

처음에는 dfs 재귀함수 방식으로 풀면 되지 않을까 생각했다. 테스트 케이스는 통과하였지만, 이렇게 풀면 범위가 100,000이기 때문에 시간 초과가 생길 수 밖에 없었다. 그래서 다른 방식으로 풀이를 바꾸었다.

풀이 2

def solution(land):
    for i in range(1, len(land)):
        for j in range(4):
            max_value = 0
            for k in range(4):
                if j == k: continue
                max_value = max(max_value, land[i-1][k])
            land[i][j] += max_value
    return max(land[len(land) - 1])

두번째 풀이는 누적합 방식으로 풀었다. 땅을 돌면서 현재 인덱스 값을 이전 땅의 자기 자신과 같은 인덱스 값을 제외하고 나머지 세 값을 비교하고 누적하여 더해주는 방식으로 구현하였다. 이렇게 구현하면 O(N)으로 풀 수 있었다.

_(빅오표기법에서는 상수를 제외하기 때문에 N)_

새롭게 배운 점

1. 제한 사항을 보며 재귀나 bfs방식을 쓸 수 있는지 확인할 것.

바로가기

문제 풀이

def solution(n):
    num = 1
    type = 1
    idx = 0
    arr = [[] for _ in range(n)]
    answer = []

    while n >= 0:
      if type % 3 == 1:
        for _ in range(0, n):
            arr[idx].insert(type // 3, num)
            num += 1
            idx += 1
        idx -= 1
      elif type % 3 == 2:
        for i in range(1, n + 1):
            arr[idx].insert(type // 3 + i, num)
            num += 1
        idx -= 1
      elif type % 3 == 0:
        for _ in range(0, n):
            arr[idx].insert(len(arr[idx]) - type // 3 + 1, num)
            num += 1
            idx -= 1
        idx += 2
      n -= 1
      type += 1

    for i in arr:
       for j in i:
          answer.append(j)

    return answer

문제를 보고 특정한 알고리즘을 이용해 문제를 풀어야 하겠다기 보다는 단순 구현으로 문제를 풀 수 있을 것이라고 생각하였다. 그 이유는 반복되는 규칙이 많이 보였기 때문이다.

1. 먼저 숫자는 왼쪽 / 아래 / 오른쪽 순으로 채워진다.
2. 숫자가 채워지는 만큼은 N -> N - 1 -> N - 2 순으로 채워진다.

N이 4일 때, 1234로 왼쪽이 채워지고, 567로 아래, 89로 오른쪽, 10으로 왼쪽이 채워지는 형태이다.

그래서 while문으로 반복하면서 N이 0이 될때 벗어나도록 하였고, 왼쪽, 아래, 왼쪽에 대한 분기를 타서 번호를 삽입하도록 진행하였다.

새롭게 배운 점

X

바로가기

문제 풀이

PY

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
graph = [[] for _ in range(1001)]
isVisited = [False] * 1001
answer = 0

for i in range(M):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

def dfs(node):
  isVisited[node] = True

  for i in graph[node]:
    if not isVisited[i]:
      dfs(i)
  return

for i in range(1, N + 1):
  if not isVisited[i]:
    dfs(i)
    answer += 1

print(answer)

풀이

DFS의 기본이 되는 문제이다.

재귀 함수를 이용해서 문제를 풀었고, 방문이 되어있지 않을 때 정답을 1씩 더해주었다.

새롭게 배운 점

1. 파이썬에서는 재귀를 할 때 안정적인 계산을 위해 1000번의 제한을 두고 있다. 처음에는 이러한 환경으로 백준에서 런타임 에러가 발생했는데 sys.setrecursionlimit(10000)을 통해 재귀 횟수를 늘려주어 문제를 해결했다.

바로가기

문제 풀이

PY

from collections import deque
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
numbers = list(map(int, input().split()))
window = deque()

for (i, num) in enumerate(numbers):
  while window and window[-1][1] > num:
    window.pop()
  window.append((i, num))
  if window[0][0] < i - L + 1: window.popleft()
  print(window[0][1], end=' ')

풀이

범위가 엄청 크면서 배열 안의 부분을 이동하면서 체크해야할 때는 슬라이딩 윈도우를 사용하는 것이 적합하다.

12 3 1 5 2 3 6 2 3 7 3 5 2 6

이렇게 입력을 받았을 때,

[1]
[1, 5]
[1, 5, 2]
[5, 2, 3]

이런 식으로 범위를 정한 다음에 최솟값을 구해야한다. 다만, 배열의 길이와 슬라이딩 배열의 최대 크기가 5000000이기 때문에 순회하면서 또 최솟값을 구하고 하기에는 무리가 있다.

슬라이딩 윈도우를 사용하면 최솟값을 구하는 반복을 최소화할 수 있다. 해당 부분에서 처음으로 deque를 사용했다. 일반적인 리스트의 pop(0)과 deque의 popleft은 성능차이가 있기 때문이다.

먼저 입력 받은 숫자들을 순회하면서 덱의 끝 숫자와 넣을 숫자를 비교해주고, 덱의 끝 숫자가 더 크면 pop을 한다.

그런 다음에 덱에 숫자를 넣어준다. 이때 인덱스와 함께 튜플의 형태로 넣어주는데 슬라이딩 윈도우의 범위를 가져야하기 때문에 덱의 맨 앞 원소의 인덱스를 검사해주고 범위를 벗어나면 popleft 해주어야 하기 때문이다.

이러한 과정을 거치면서 계속 덱의 맨 앞 원소의 값을 출력해주면 최솟값을 쉽게 찾을 수 있다.

새롭게 배운 점

1. 덱을 임포트 할 때 from collections import deque
2. window = deque()
3. popleft, appendleft는 모두 시간 복잡도가 O(1)이다.

팀원들과 스터디를 진행하면서 어떤 프로젝트를 진행할 지 고민하였고, 구현 보다는 설계 측면에서 어떻게 api를 연동하고 최적화를 진행할 지에 대한 고민을 하였다.

그래서 구글링을 하던 중 개발자 한 분이 웹툰 정보를 모아서 뿌려주는 api를 개발하셨고, 포스팅 해둔 글을 발견하였고, 이 api를 활용해보자고 결정하였다.

https://hyeokjaelee.github.io/korea-webtoon-api-update/

_(감사합니다 개발자님...)_

다들 다양하게 api를 활용해서 구현을 진행하였는데, 나는 리액트 쿼리를 활용해서 페이지네이션을 하는데스크롤이 아래쯤으로 내려오면 데이터를 로드해서 무한 스크롤 비슷하게 만들어보면 어떨까 생각하였다.

그래서 tanstack-qeury의 useInfiniteQuery와 IntersectionObserver를 통한 무한스크롤 기능에 중점을 두고 스터디를 임하였다.

본론

API 연동

  // webtoonApi.ts
...

  export const fetchWebtoons = async ({
    keyword,
    provider,
    isFree,
    updateDays,
    isUpdated,
    page,
  }: webtoonQueryType) => {
    const params = Object.fromEntries(
      Object.entries({ keyword, provider, isFree, updateDays, isUpdated }).filter(
        ([, value]) => value !== "" && value !== "ALL" && value !== false
      )
    );

    const { data } = await axiosInstance.get("/webtoons", {
      params: {
        ...params,
        page: page,
      },
    });
    return {
      data: data.webtoons, // 웹툰 리스트 반환
      isLastPage: data.isLastPage, // 마지막 페이지 여부 반환
    };
};

API를 보면 쿼리스트링을 통해 데이터를 필터링한 후 가져올 수 있다. 이미 페이지네이션 기능도 제공을 하기 때문에 저렇게 page를 넣어주었다.

Object를 필터링하는 이유는 사용자가 값을 입력하지 않았다면 쿼리스트링에 포함하지 않기 위해서이다.

예를 들어서, provider는 KAKAO, KAKAO_PAGE, NAVER 이렇게 인데 사용자가 아무런 입력을 하지 않았다면 ALL로 설정을 해두었다. 하지만 파라미터 값이 들어갈 때 ALL이 들어가면 API에서 제공하는 값이 아니기 때문에 오류가 날 수 있다. 그래서 API를 요청하기 전에 한 번 필터링을 거치는 것이다.

_(ALL이라는 값은 클라이언트에서 사용하는 값이라 서버 쪽에서는 어떤 값인지 알 수 없다는 뜻)_

  // useWebtoonQuery.ts
...

  export const useWebtoonsQuery = (filters: webtoonQueryType) => {
    const { keyword, provider, isFree, updateDays, isUpdated } = useSearchStore();

    return useInfiniteQuery({
      queryKey: ["webtoons", keyword, provider, isFree, updateDays, isUpdated],
      queryFn: ({ pageParam = 1 }) =>
        fetchWebtoons({ ...filters, page: pageParam }),
      getNextPageParam: (lastPage, allPages) => {
        // 마지막 페이지인지 확인 후 증가
        return lastPage.isLastPage ? undefined : allPages.length + 1;
      },
      initialPageParam: 1,
    });
};

쿼리 부분에서는 기본적인 useQuery를 사용하지 않고, useInfiniteQuery를 사용하였다.

useQuery와 useInfiniteQuery의 차이점

useQuery는 요청을 한 번 보내는 쿼리이고 useInfiniteQuery는 요청을 보낸 다음에 추가 요청을 보낼 수 있는 쿼리이다.

getNextPageParam 메서드를 통해 추가 요청을 보내고 데이터를 쌓아나갈 수 있다. 또 특이한 점은 useInfiniteQuery는 queryFn에 pageParam을 받아야한다. 그리고 옵션으로 initialPageParam 통해 초기 페이지 값을 정해줄 수 있다.

  |  | `useQuery` | `useInfiniteQuery` |

|---|---|---| | 데이터 요청 방식 | 한 번만 가져옴 | 추가 데이터를 계속 요청 가능 | | 사용 예시 | 유저 정보, 특정 게시물 상세 | 무한 스크롤, 더 보기 버튼 | | 다음 페이지 로딩 | ❌ (지원 안 함) | ✅ (fetchNextPage 사용) | | 데이터 저장 방식 | 한 번만 저장 | 여러 페이지 데이터를 누적 |

IntersectionObserver를 통한 데이터 로드

다음 페이지를 가져오도록 쿼리를 사용했으니 트리거를 달아줘야한다.

스크롤이 끝 지점이 다다랐을 때, fetchNextPage를 호출해서 다음 페이지를 불러오는 작업을 진행한다.

  ...

  const WebtoonList = () => {

    ...

    // 스크롤 감지 로직
    useEffect(() => {
      if (!observerRef.current) return;

      const observer = new IntersectionObserver(
        (entries) => {
          if (entries[0].isIntersecting) {
            fetchNextPage();
          }
        },
        { threshold: 0.8 } // 80% 지점에서 감지
      );

      observer.observe(observerRef.current);
      return () => observer.disconnect();
    }, [fetchNextPage, isLoading]);

    if (isLoading) return <p>로딩 중...</p>;
    if (!webtoons || webtoons.pages.length === 0)
      return <p>검색 결과가 없습니다.</p>;

    return (
      <>
        <div className="flex flex-wrap justify-center gap-x-3 gap-y-3">
          {webtoons.pages.map((page) =>
            page.data.map((webtoon: webtoonType) => (
              <WebtoonItem key={webtoon.id} webtoon={webtoon} />
            ))
          )}

          {/* 스크롤 감지 요소 */}
          <div className="h-[10px]" ref={observerRef} />
        </div>
        {/* 로딩 상태 표시 */}
        {isFetchingNextPage && (
          <p className="text-center text-gray-500">로딩 중...</p>
        )}
      </>
    );
};

export default WebtoonList;

IntersectionObserver는 요소가 화면에 보이는지 감지하는 웹 API로, 뷰포트에 감지가 되면 특정한 콜백 함수를 호출하는 기능을 가지고 있다. 그래서 스크롤 이벤트를 하지 않아도 특정 구간에서 함수를 호출할 수 있다. (성능 우위)

IntersectionObserver는 두 가지 매개 변수를 받는데 콜백 함수와 옵션 값을 받는다. 먼저 콜백함수는 인자로 감지한 요소들의 배열과 옵저버를 받을 수 있다.

entries → 감지한 요소들의 배열 entry.isIntersecting → 뷰포트에 보이면 true observer.observe(target) → 감지할 요소 지정 observer.unobserve(target) → 감지 중지 (필요 없으면 해제 가능)

위와 같이 특정한 조건에서 감지를 중지할 수도 있고, 감지가 되었는지 판단할 수도 있다.

const options = {
  root: null, // 뷰포트 기준 (null이면 화면 자체가 기준)
  rootMargin: "0px", // 감지 범위 확장/축소 가능 (ex. "100px 0px" → 위로 100px 더 감지)
  threshold: 0.5, // 50% 이상 보이면 감지
};

두번째 매개변수인 옵션은 객체의 형태로 넣어주어야하고 위와 같은 옵션이 있다. threshold를 자주 사용한다.

결론

이러한 기술들을 이용하여 무한 스크롤 기능을 구현한 프로젝트는 아래와 같이 동작을 하게 됐다!

_(디자인은 신경쓰지 말아주세요.. 기능만 고려를 해봤습니다..!)_

바로가기

문제 풀이

PY

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()

cnt = 0
for idx, number in enumerate(numbers):
  start_idx, end_idx = 0, n - 1

  while start_idx < end_idx:
    sum = numbers[start_idx] + numbers[end_idx]

    if sum == number:
      if start_idx == idx: start_idx += 1
      elif end_idx == idx: end_idx -= 1
      else:
        cnt += 1
        break
    elif sum < number:
      start_idx += 1
    else:
      end_idx -= 1

print(cnt)

풀이

투 포인터 알고리즘을 이용하여 문제를 풀었다.

배열을 입력받은 후에 정렬을 한 뒤, 인덱스를 시작 지점과 끝 지점에 두고 해당 인덱스에서의 숫자 합을 비교한다. 하지만 이때 타겟 인덱스가 두 인덱스와 같으면 안되기 때문에 거기에 대한 분기를 타주었다.

새롭게 배운 점

1. 투포인터 알고리즘을 사용하여 문제를 푼다고 했을 때는 시작 인덱스와 끝 인덱스를 시작으로 인덱스를 바꿔가면서 수를 비교해야하기 때문에 배열이 정렬되어있어야한다.

바로가기

문제 풀이

PY

import sys
input = sys.stdin.readline

answer = 0
m, n = map(int, input().split())
numbers = list(map(int, input().split()))
spatial_sum = [0] * m
modified_sum = [0] * n

spatial_sum[0] = numbers[0]
for i in range(1, len(numbers)):
  spatial_sum[i] = numbers[i] + spatial_sum[i - 1]

for sum in spatial_sum:
  if sum % n == 0: answer += 1
  modified_sum[sum % n] += 1

for sum in modified_sum:
  answer += sum * (sum - 1) // 2

print(answer)

풀이

5 3 1 2 3 1 2

위와 같이 입력을 받는다고 하면 먼저 구간합을 구해보자.

1 3 6 7 9

이렇게 될 것이다. 이러면 일단 순서대로 더했을 때의 나머지를 구할 수 있다. 나머지를 구해보면

1 0 0 1 0 -> arr

이렇게 나온다. 그러면 일단 0인 애들은 나누어 떨어지기 때문에 카운트를 세준다.

그 다음부터는 새롭게 알게 된 사실인데 나머지 값이 같은 애들끼리 두 개를 조합할 수 있는 경우의 수를 구한다.

나머지를 구한 배열을 arr이라고 하면, arr[0]과 arr[3]은 1로 원소가 같고, arr[1], arr[2], arr[4]는 0으로 원소가 같다.

arr[0]의 구간합은 1이고 arr[3]의 구간합은 7이다. 7 - 1은 6으로 나누어 떨어진다.

arr[1], arr[2], arr[4]도 같은 방식이다. arr[2]의 구간합은 6이고 arr[4]의 구간합은 9이다. 9 - 6은 3으로 나누어 떨어진다.

이런 방식으로 나머지가 같은 애들끼리 두 개를 조합하면 갯수를 확인할 수 있다. (두 개인 이유는 시작점과 끝점으로 두 개인 것)

이렇게 해서 모든 경우의 수를 계산하면 3 + 3 + 1 = 7 이렇게 나온다.

새롭게 배운 점

1. 프로그래머스랑 백준이랑 정답 체크 방식이 달라서 입력 출력하는데 신경 쓸 필요가 있다. 원래는 input() 만을 사용해서 풀었었는데 그럴 경우 너무 느려졌는데 다음과 같은 이유가 있었다.

   input() 은 매개변수로 prompt message를 받음 입력받은 값의 개행 문자를 삭제시키고 반환함.

   그래서 아래처럼 전처리 과정이 필요하다.

   import sys
   input = sys.stdin.readline
   
   m, n = map(int, input().split())
   numbers = list(map(int, input().split()))

2. 경우의 수를 구하는 공식은

만약에 원소가 세 개 있고 거기서 두 개로 조합을 하면 n = 3, k = 2가 되는 것이다. 그렇게 되면 3 * 2 / 2 = 3이 나온다.

백준 문제는 자바스크립트로 작성하기 너무 귀찮아서 파이썬으로만..

바로가기

문제 풀이

JS

function solution(players, m, k) {
    let answer = 0;
    let server = [];

    for(const player of players){
        server.forEach((val, idx) => server[idx]--);
        server = server.filter(val => val > 0);

        const available_players = server.length * m + m - 1;
        if(player > available_players) {
            let temp = available_players;
            while(temp < player){
                server.push(k);
                temp += m;
                answer++;
            }
        }
    }
    return answer;
}

PY

def solution(players, m, k):
    answer = 0
    server = []

    for player in players:
        server = [val - 1 for val in server]
        server = [val for val in server if val > 0]

        available_players = len(server) * m + m - 1
        if player > available_players:
            temp = available_players
            while temp < player:
                temp += m
                server.append(k)
                answer += 1
    return answer

풀이

Level2의 문제 치고는 쉬운 편이다.

시간을 돌면서 플레이어와 수용 가능한 플레이어의 수를 비교한 다음, 서버를 추가해야할 경우라면 while 문을 통해 서버를 추가해주고 카운팅을 한다.

이후 for문을 돌면서 서버의 시간을 1씩 줄여주고 0이 되면 배열에서 없애준다.

새롭게 배운 점

1. 파이썬에서 리스트 컴프리헨션에 익숙해져야할 필요가 있다.

    server = [val - 1 for val in server]
    server = [val for val in server if val > 0]

   위 방법을 통해서 서버에 새로운 배열을 만들어 줄 수 있다.

바로가기

문제 풀이

JS

function solution(name) {
    let answer = 0;
    const dict = {};

    // char 인덱스 정의
    const alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
    alphabet.map((idx, val) => dict[idx] = val);

    // 알파벳을 앞으로 돌지 뒤로 돌지 판별
    for(const word of name) 
        answer += Math.min(dict[word], Math.abs(26 - dict[word]));

    // 경우의 수 1. 그냥 순회 2. 오른쪽으로 갔다가 뒤로 가기 3. 왼쪽으로 갔다가 오른쪽으로 가기
    let move = name.length - 1; // 1번
    let j = 0;
    for(let i = 0; i < name.length; ++i) {
        j = i + 1; // 현재 인덱스 다음부터 A가 아닌 인덱스
        while(j < name.length && dict[name[j]] === dict['A']) j++;
        move = Math.min(move, Math.min(i + i + (name.length - j), (name.length - j) + (name.length - j) + i))
    }

    return answer + move;
}

PY

def solution(name):
    answer = 0

    move = len(name) - 1
    y = 0
    for idx, word in enumerate(name):
        answer += min(ord(word) - ord('A'), abs(ord('Z') - ord(word) + 1))
        y = idx + 1
        while y < len(name) and name[y] == 'A': y += 1
        move = min(move, min(idx + idx + len(name) - y, len(name) - y + len(name) - y + idx))

    return answer + move

풀이

탐욕법은 너무 어렵다.. 먼저 탐욕법은 여러 가지 경우의 수를 생각해서 최소의 경우를 구하는 방법이다. 탐욕법을 풀면서 팁은 여러 가지 경우의 수를 판단한 다음 최솟값 구하는 메서드를 사용하는 것이다.

먼저, 두 개의 과정을 거쳐야한다.

1. 알파벳을 앞으로 카운트할지 뒤로 카운트할지
2. 문자를 오른쪽으로 갈지 왼쪽으로 갈지

첫 번째 과정은 쉽다. 문자가 26개가 있으니 앞으로 카운트한 것과 뒤로 카운트한 것의 최솟값을 구하는 것

두 번째 과정이 정말 어려웠다. 두 번째 과정은 세 개의 경우의 수가 있다.

1. 가장 쉬운 그냥 순서대로 체크
2. 오른쪽으로 갔다가 왼쪽으로 가는 경우
3. 왼쪽으로 갔다가 오른쪽으로 가는 경우

모든 문자를 순회하면서 세 가지의 경우의 수를 체크해주어야한다. 일단 현재 인덱스와 현재 인덱스 다음으로 오는 A가 아닌 문자를 체크한다. 그 다음 현재 인덱스에서 위 세 가지의 경우의 수를 구하고 비교를 한다.

그 다음 두 개의 과정에서 얻은 수를 더하면 결과값이 나온다.

새롭게 배운 점

1. 자바스크립트에서 아스키코드 값을 얻으려면 charCodeAt, 파이썬에서는 ord 메서드를 사용한다.

바로가기

문제 풀이

JS

function solution(video_len, pos, op_start, op_end, commands) {
  const convertTime = (str) => {
    const [mm, ss] = str.split(":");
    return Number(mm) * 60 + Number(ss);
  };

  const v_len = convertTime(video_len);
  const o_start = convertTime(op_start);
  const o_end = convertTime(op_end);

  let c_pos = convertTime(pos);

  for (const command of commands) {
    if (c_pos < 0) c_pos = 0;
    if (c_pos > v_len) c_pos = v_len;
    if (c_pos >= o_start && c_pos <= o_end) c_pos = o_end;

    switch (command) {
      case "next":
        c_pos += 10;
        break;
      case "prev":
        c_pos -= 10;
        break;
    }
  }

  if (c_pos < 0) c_pos = 0;
  if (c_pos > v_len) c_pos = v_len;
  if (c_pos >= o_start && c_pos <= o_end) c_pos = o_end;

  const mm = Math.floor((c_pos / 60).toString());
  const ss = (c_pos % 60).toString();

  return String(mm).padStart(2, "0") + ":" + String(ss).padStart(2, "0");
}

PY

def convertTime(str):
    [mm, ss] = map(int, str.split(":"))
    return mm * 60 + ss

def solution(video_len, pos, op_start, op_end, commands):
    c_pos = convertTime(pos)
    v_len = convertTime(video_len)
    o_s = convertTime(op_start)
    o_e = convertTime(op_end)

    for command in commands:
        if c_pos >= o_s and c_pos <= o_e: c_pos = o_e
        if command == "next": c_pos = min(v_len, c_pos + 10)
        elif command == "prev": c_pos = max(0, c_pos - 10)

    if c_pos >= o_s and c_pos <= o_e: c_pos = o_e

    return str(c_pos // 60).zfill(2) + ":" + str(c_pos % 60).zfill(2)

풀이

이 문제도 단순 구현 문제인데 마지막에 0을 채우는 방법이 떠오르지 않아 애를 먹은 문제였다.

자바스크립트를 이용해서 먼저 문제를 풀었는데 코드를 조금 더 간결하게 만들 수 있을 것 같았다. 그래서 파이썬으로는 좀 더 코드를 간결화하는데 집중해서 문제를 풀었다. 저렇게 범위를 넘어가는 경우가 있을 때는 조건문을 통해 처리하기보다는 저렇게 최대, 최소로 비교하는 방법이 훨씬 깔끔한 것 같다.

새롭게 배운 점

1. 자바스크립트에서 왼쪽에 문자를 채울 때는 String().padStart(길이, "넣을 문자")
2. 파이썬에서 왼쪽에 문자를 채울 때는 str().zfill(2) 하면 자동으로 0을 채워준다.

바로가기

문제 풀이

JS

function solution(bandage, health, attacks) {
    let answer = health;
    const turn = attacks[attacks.length - 1][0];

    let cnt = 0;
    for(let i = 0; i < turn; ++i) {
        if (i + 1 === attacks[0][0]) {
            answer -= attacks[0][1];
            cnt = 0;
            attacks.shift();
        } else{
            cnt++;
            answer += bandage[1];

            if(cnt === bandage[0]) {
                answer += bandage[2];
                cnt = 0;
            }

            if(answer >= health) answer = health;
        }

        if(answer <= 0) return -1;
    }
    return answer;
}

PY

def solution(bandage, health, attacks):
    answer = health
    turn = attacks[len(attacks) - 1][0]

    cnt = 0
    for i in range(1, turn + 1):
        if i == attacks[0][0]:
            answer -= attacks[0][1]
            cnt = 0
            del attacks[0]
        else:
            cnt += 1
            answer += bandage[1]
            if cnt == bandage[0]:
                answer += bandage[2]
                cnt = 0
            if answer > health: answer = health

        if answer <= 0: return -1

    return answer

풀이

단순 구현 문제이다. 최대한 반복하는 횟수를 줄여보고 싶었는데 나의 머리로는 잘 생각이 안나서 공격이 끝나는 횟수만큼 한 턴씩 움직이게끔 구현하였다..

처리만 잘해주면 공격하는 횟수만큼만 돌면 될 것 같은데..

새롭게 배운 점

1. 파이썬에서 앞 원소를 삭제할 때 del 키워드를 사용한다.

바로가기

문제 풀이

JS

function solution(k, dungeons) {
    let answer = Number.MIN_SAFE_INTEGER;
    const visited = new Array(dungeons.length).fill(false);

    const dfs = (health, dungeons, cnt) => {
        answer = Math.max(answer, cnt);

        for(let i = 0; i < dungeons.length; ++i) {
            if (health < dungeons[i][0] || health - dungeons[i][1] < 0 || visited[i]) continue;
            visited[i] = true;
            dfs(health - dungeons[i][1], dungeons, cnt + 1);
            visited[i] = false;
        }
    }

    dfs(k, dungeons, 0);
    return answer;
}

PY

import sys

def solution(k, dungeons):
    answer = -sys.maxsize
    visited = [False for _ in range(len(dungeons))]

    def dfs(health, dungeons, cnt):
        nonlocal answer
        answer = max(answer, cnt)

        for idx, dungeon in enumerate(dungeons):
            if(visited[idx] or health < dungeons[idx][0] or health - dungeons[idx][1] < 0):
                continue
            visited[idx] = True
            dfs(health - dungeons[idx][1], dungeons, cnt + 1)
            visited[idx] = False

    dfs(k, dungeons, 0)
    return answer

풀이

DFS의 정석인 문제

모든 경우의 수를 탐색해야하고 범위가 크지 않을 때 DFS 고려해봐야한다. 재귀함수를 통해 문제를 해결했는데 방문 체크를 하는 것과 동시에 조건에 맞으면 재귀한다.

새롭게 배운 점

1. 파이썬에서 함수 내부에서 전역 변수를 수정하려고 하면 nonlocal 키워드가 필요하다.

바로가기

문제 풀이

JS

function solution(schedules, timelogs, startday) {
  let answer = 0;

  timelogs.map((timelog, idx) => {
    let flag = true,
      day = startday - 1;

    for (const table of timelog) {
      day++;
      if (day === 6 || day === 7) continue;

      const tHour = Math.floor(Number(table) / 100),
        tMinute = Number(table) % 100;
      const sHour = Math.floor(Number(schedules[idx]) / 100),
        sMinute = Number(schedules[idx] % 100);
      const diff = (tHour - sHour) * 60 + (tMinute - sMinute);
      if (diff > 10) flag = false;

      if (day > 7) day = 1;
    }
    if (flag) answer++;
  });
  return answer;
}

PY

def solution(schedules, timelogs, startday):
    answer = 0

    def convertTime(time):
        h = time // 100
        m = time % 100
        return h * 60 + m

    for idx, timelog in enumerate(timelogs):
        s = startday - 1
        flag = True
        for table in timelog:
            s += 1
            if s in [6, 7]:
                continue
            elif s > 7:
                s = 1

            if convertTime(table) - convertTime(schedules[idx]) > 10:
                flag = False

        if flag:
            answer += 1
    return answer

풀이

구현 문제였는데 실수한 부분이 나눗셈을 할 때 소수부를 신경쓰지 않았던 점이다. 이 부분 때문에 시간이 지체됐다. 조금 더 계산할 때 신경써주어야할 것 같다.

새롭게 배운 점

1. 파이썬에서 나눗셈을 할 때 / 이면 소수부까지 // 이면 정수부에 대한 몫만 구하는 것

2. enumerate를 통해 value, idx를 한 번에 받아올 수 있다.

3. 파이썬에서는 in 배열을 통해서 쉽게 포함되어있는지 확인할 수 있다.

바로가기

문제 풀이

JS

function solution(today, terms, privacies) {
  var answer = [];

  privacies.map((privacy, index) => {
    const [date, type] = privacy.split(" ");
    const [year, month, day] = date.split(".");
    const [tYear, tMonth, tDay] = today.split(".");

    const duration =
      Number(tYear - year) * 12 * 28 +
      Number(tMonth - month) * 28 +
      Number(tDay - day);

    terms.map((term) => {
      const [targetType, targetMonth] = term.split(" ");

      if (targetType === type && duration >= targetMonth * 28) {
        answer.push(index + 1);
      }
    });
  });
  return answer;
}

PY

def solution(today, terms, privacies):
    tYear, tMonth, tDay = map(int, today.split("."))
    answer = []
    for i in range(len(privacies)):
        target, type = privacies[i].split(" ")
        year, month, day = map(int, target.split("."))

        term = (tYear - year) * 12 * 28 + (tMonth - month) * 28 + (tDay - day)
        for j in range(len(terms)):
            tarType, tarTerm = terms[j].split(" ")
            if tarType == type:
                if term >= int(tarTerm) * 28:
                    answer.append(i + 1)
    return answer

풀이

회사 지원을 하면서 JS를 지원하지 않는 기업이 생각보다 많았다. 조금 다양한 풀을 지원하기 위해서 코테용 언어를 하나 배우는게 나을 것 같다고 생각해서 가장 접근이 쉬운 파이썬을 이용해 복습 겸 한번 더 푸는 방식으로 공부하자고 결정하였다.

파이썬으로 새롭게 풀면서 느꼈던 점은 구조분해할당이 JS와 비슷한 방식이어서 편했고, c++이나 java보다는 빠르게 익힐 수 있을 것 같다는 생각을 하였다.

먼저 privacies를 돌면서 split한 다음 타입에 맞춰서 기간을 체크해주면 됐다. 가볍게 풀 수 있는 구현 문제 같았다.

새롭게 배운 점

1. 파이썬에서 split을 할 때 타입을 명시하지 않으면 문자열로 만들어지고, 이때 숫자 계산이 어렵기 때문에 map(type, 문자열) 메서드를 통해 타입 자체로 split하는 방법

2. terms을 for문을 통해 계속 반복하면서 체크하기보다는 JS의 map이나 파이썬의 dict을 통해 저장해놓고 바로 접근하면 이중 포문을 안써도 된다.

   terms_dict = dict(t.split() for t in terms)

바로가기

문제 풀이

function solution(triangle) {    
    for(let i = 1; i < triangle.length; ++i) {
        for(let j = 0; j < triangle[i].length; ++j) {
            if(j === 0) triangle[i][j] += triangle[i - 1][0];
            else if(j === triangle[i].length - 1) triangle[i][j] += triangle[i - 1][j - 1];
            else triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j])
        }
    }

    return Math.max(...triangle[triangle.length - 1]);
}

풀이

레벨 3 문제치고는 쉬웠다.

위에서 아래로 내려가면서 더해주는 원리인데, 가장자리(처음, 마지막)에 있는 원소들은 두 가지 숫자를 고를 수 없이 바로 위에 있는 애들을 더해주어야 하고, 중간에 있는 원소들은 위에 두 수 중에 최댓값을 더해주면 된다.

가장 위에 있는 원소는 더해질 필요가 없으니 두번째 라인부터 반복분을 진행하면서 위에있는 원소를 더해주는 작업을 한다. 이때 앞서 말한 규칙대로 더해준다.

마지막으로 리턴할 때 가장 밑에 있는 배열의 최댓값을 구해서 리턴해주면된다.

결과

새롭게 배운 점

1. Math.max 메서드는 배열을 받지 않기 때문에 스프레드 연산자로 배열을 풀어줘야함.
2. 파이썬은 배열에 -1 인덱스를 넣어서 마지막 원소에 접근이 가능한데 JS는 안되네..

바로가기

문제 풀이

function solution(n, wires) {
    let answer = Number.MAX_SAFE_INTEGER;

    // 그래프 생성
    const graph = [];
    for(let i = 0; i < n + 1; ++i) graph.push(new Array());
    for(const [a, b] of wires) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const bfs = (rootNum, exceptNum) => {
        const visit = new Array(n + 1).fill(false);
        const queue = [rootNum];
        let cnt = 0;
        visit[rootNum] = true;

        while(queue.length > 0) {
            const root = queue.pop();
            for(const num of graph[root]){
                if(visit[num] || num === exceptNum) continue;
                visit[num] = true;
                queue.unshift(num);
            }

            cnt++;
        }

        return cnt;
    }

    for(const [a, b] of wires){
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    }

    return answer;
}

import sys

def solution(n, wires):
    answer = sys.maxsize
    graph = [[] for _ in range(n + 1)]

    for (a, b) in wires:
        graph[a].append(b)
        graph[b].append(a)

    def bfs(startNode, exceptNode):
        cnt = 0
        visit = [False for _ in range(n + 1)]
        queue = [startNode]
        visit[startNode] = True

        while queue:
            currentNode = queue.pop()

            for node in graph[currentNode]:
                if visit[node] or node == exceptNode:
                    continue
                visit[node] = True
                queue.insert(0, node)

            cnt += 1

        return cnt

    for (a, b) in wires:
        answer = min(answer, abs(bfs(a, b) - bfs(b, a)))

    return answer

풀이

어떻게 접근해야할 지 감이 잡히지 않았다. 그나마 다행인 것은 문제를 보고 bfs로 접근해야겠다는 느낌을 받았다.

그래프에서 전력망을 끊으면 해당 간선을 기준으로 두 개의 그래프로 쪼개지게된다. 그러면 그 두 그래프를 bfs로 탐색하면서 몇 개로 구성되어 있는지 검사하면 되겠다고 생각했다.

그래서 먼저 wires를 조금 더 분석하기 쉽게 구조를 수정하였다. 그 다음에 bfs 함수를 만들어서 큐를 이용해 풀었다. 방문한 노드이거나 끊어진 노드면 처리하지 않도록 했다.

마지막으로 모든 간선을 돌면서 두 개의 그래프 갯수의 차이를 계산하였다.

결과

새롭게 배운 점

JS에서 최댓값은 이렇게 쓸 것

Number.MAX_SAFE_INTEGER

바로가기

문제 풀이

function solution(numbers) {
    let answer = 0;
    const nums = numbers.split("");
    const check = new Array(10000000).fill(0);
    const length = new Array(numbers.length).fill(false);

    check[0] = true;
    check[1] = true;
    const dfs = (number, str) => {
        let num;
        if(number !== "") num = Number(str);

        if(!check[num]) {
            let flag = true;
            for(let i = 2; i * i <= num; ++i) {
                if (num % i === 0) flag = false;
            }

            if(flag) answer++;
            check[num] = true;
        }
        for(let j = 0; j < number.length; ++j) {
            if(length[j] === false) {
                length[j] = true;
                dfs(number, str + number[j]);
                length[j] = false;
            }
        }
    }

    dfs(nums, "");
    return answer;
}

새롭게 배운 점

너무 어려웠던 소수찾기 문제

모든 경우의 수를 다 찾아봐야하기 때문에 dfs로 탐색하였다.

중복해서 숫자를 검색할 필요는 없기 때문에 check 배열로 이미 찾은 수를 확인해주었고, 배열의 길이만큼 반복문을 돌려주면서 원소 한 개 넣고 검사하고 한개 더 넣고 검사하는 방식으로 모든 경우의 수를 탐색해주었다.

바로가기

문제 풀이

function solution(maps) {
    const m = maps.length;
    const n = maps[0].length;
    const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];

    const bfs = () => {
        const queue = [];
        queue.push([0, 0, 1]);
        maps[0][0] = 0;

        while(queue.length > 0) {
            const [row, col, distance] = queue.shift();

            if(row === m - 1 && col === n - 1) {
                return distance;
            }

            for(let i = 0; i < dir.length; ++i) {
                const [x, y] = dir[i];
                const newRow = row + x;
                const newCol = col + y;

                if(newRow < 0 || newCol < 0 || newRow >= m || newCol >= n || maps[newRow][newCol] === 0) continue;

                queue.push([newRow, newCol, distance + 1]);
                maps[newRow][newCol] = 0;
            }
        }

        return -1;
    }

    return bfs();
}

새롭게 배운 점

너비 우선 탐색의 전형적인 문제인 길찾기를 풀어보았다. JS로 BFS 문제를 푸는게 처음이라 조금 헤맸지만 그래도 길찾기 문제는 정해진 양식이 있는 것 같다.

1. 방향 만들기
2. 시작점 넣고 while문으로 큐가 비어있을 때까지 돌리기
3. while문 넣자마자 원소 빼고 목표 설정하기
4. 방향 만큼 반복문으로 돌리면서 큐에 방향 넣어주기
5. 방향 넣어주면 다녀온 처리하기

이렇게 외워두자!

바로가기

문제 풀이

let answer = 0;

function dfs(numbers, target, sum, cnt) {
    if(numbers.length === cnt) {
        if(sum === target) answer++;
        return;
    }else {
        dfs(numbers, target, sum + numbers[cnt], cnt + 1);
        dfs(numbers, target, sum - numbers[cnt], cnt + 1);
    }
}

function solution(numbers, target) {
    dfs(numbers, target, 0, 0);
    return answer;
}

새롭게 배운 점

오랜만에 코딩테스트를 봐야하는 일이 생겨서 다시 DFS/BFS를 공부중이다.. 핵심은 재귀함수로 할 수 있는 경우의 수를 다 검사하는 법이다.

더하는 수와 빼는 수가 있기 때문에 깊이 우선 탐색을 통해 0부터 시작해서 수를 더하는 방법과 빼는 방법의 경우의 수를 하나하나 들어가면서 배열의 길이와 함수의 카운트 수가 같아 졌을 때 타겟 넘버가 일치하면 답을 하나 올려주는 형식으로 구현하였다.

바로가기

문제 풀이

function solution(n, w, num) {
    const arr = [];

    for(let i = 0; i < w; ++i){
        arr.push(new Array());
    }

    let j = 0, cnt = 0;
    for(let i = 0; i < n; ++i) {
        if(j === w) {
            j = 0;
            cnt++;
        }

        switch(cnt % 2){
            case 0:
                arr[j].push(i + 1);
                break;
            case 1:
                arr[Math.abs(j-w+1)].push(i + 1);
                break;
        }

        j++;
    }

    let answer = 0;
    arr.map(items => {
        items.map((item, idx) => {
            if(item === num){
                answer = items.length - idx;
                return;
            } 
        })
    })

    return answer;
}

새롭게 배운 점

처음에는 배열을 초기화할 때

const arr = new Array(w).fill([]);

이런 식으로 작성을 했는데 for문을 한번 돌리는데도 불구하고 모든 배열에 숫자가 다 들어가는 현상이 발생했다. 그래서 찾아보니까 모든 빈 배열 요소가 같은 값을 참조해서 생기는 현상이라고 했다. 그래서 새로운 배열 객체를 가질 수 있도록

const arr = [];

for(let i = 0; i < w; ++i){
  arr.push(new Array());
}

이렇게 변경하였다.