라이브 세션과 PR 리뷰를 보고 기억에 남았던 것들을 모아 정리해봤다.

UI와 1:1

// AS-IS
function RoomBookingPage() {
  return (
    <div style={{ padding: 20 }}>
      <div style={{ fontSize: 24, fontWeight: 'bold' }}>회의실 예약</div>
      <div className="calendar-wrapper">...</div>
      <div style={{ marginTop: 40 }}>
        {reservations.map(r => <div key={r.id}>...</div>)}
      </div>
    </div>
  );
}

// TO-BE
function RoomBookingPage() {
  return (
    <main>
      <TopNavigation title="회의실 예약" />
      <section>
        <h2>날짜 선택</h2>
        <DatePicker value={date} onChange={setDate} />
      </section>
      <ReservationStatusSection selectedDate={date} />
      <section>
        <MyReservationList items={myReservations} />
      </section>
      <Button onClick={handleOpenBooking}>예약하기</Button>
    </main>
  );
}

사람의 기억력과 인지 능력은 한계가 있기 때문에 HTML이 그림처럼 위에서 아래로 읽히는 것처럼, 컴포넌트들도 UI와 1:1 대응이 되게 해서 예측을 쉽게 해줄 수 있어야 한다.

세부 구현은 컴포넌트 안으로

내장이 쏟아져 나온 것 같다

다소 직설적이지만 적절한 표현이었던 것 같아서 기억에 남았서 적었다.

// 페이지에 계산 로직이 흘러넘침
const timeSlots = Array.from({ length: 24 }).map((_, i) => {
  const hour = Math.floor(i / 2) + 9;
  const min = i % 2 === 0 ? '00' : '30';
  return `${String(hour).padStart(2, '0')}:${min}`;
});

return <페이지 컴포넌트 />;

---

// 의도만 전달하고, 구현은 안으로
<TimeSelect value={start} onChange={setStart} minTime="09:00" maxTime="20:00" />

페이지 레벨에서 Array.from().map() 같은 계산 루프가 돌아가고 있다면, 굳이 페이지가 시간 배열 만드는 방법 -> 세부 구현까지 알아야 할 필요가 있나 생각해 볼 필요가 있다. TimeSelect에는 "09시부터 20시까지"라는 의도만 전달하면 충분하다.

Props 이름에 세부 구현은 좀

DateSelector에 setDate를 props로 내리면, 이 컴포넌트는 영원히 "상태를 변경하는 용도"로만 쓰일 수밖에 없다. 컴포넌트는 자신이 할 행위만 props로 요청해야 하고, 외부에서 어떻게 처리할지는 관여하면 안된다.

// AS-IS 외부 구현 방식에 종속됨
<DateSelector setDate={setDate} />

// TO-BE HTML 표준 인터페이스를 따름
<DateSelector value={date} onChange={setDate} />

value, onChange는 HTML input이 쓰는 방식이고, 우리가 이미 제일 익숙한 인터페이스이다. 2부에서 문동욱 님이 인터페이스는 구멍이라는 표현을 쓰셨는데, 규격이 안 맞는 구멍은 아무것도 연결하지 못한다는 게 적절한 비유였던 것 같다.

추가로 PR 리뷰에서도 비슷한게 있었는데, props 이름이 컴포넌트 이름과 그대로 겹치는 문제였다. <MyReservationList reservationList={data} />처럼 쓰면 "마이 레저베이션 리스트의 레저베이션 리스트"가 되는데, 문맥이 명확하다면 그냥 items정도면 OK다.

함수 이름의 배신

// ❌ 호출부에서는 알 수 없는 사이드 이펙트
const navigate = (url) => {
  if (hasMessage) setMessage("예약이 완료되었습니다.");
  router.push(url);
};

<Button onClick={() => navigate('/booking')}>예약하기</Button>

// ✅ 호출부에서 흐름이 그대로 보임
const handleBooking = () => {
  setMessage("예약이 완료되었습니다.");
  router.push('/booking');
};

<Button onClick={handleBooking}>예약하기</Button>

이름은 단순 이동인데 내부에서 외부의 메세지까지 조작한다. 함수 이름이 예측을 유도하는데 내부에서 전혀 다른 동작을 하면, 이해 하는 것에 추가적인 리소스가 필요하게 된다. 이런 코드가 쌓일수록 이해하는 것이 더 피로해지고, 버그를 추적하기가 점점 힘들어진다. 예측 가능한 코드와 이해하기 쉬운 코드는 결국 같은 말인 것 같다.

마무리

모의고사를 풀 때에는 거대한 코드에 당황하여 목적 없이 마구 잡이로 리팩토링을 했던 것 같다. 라이브 세션을 듣고 복습 겸 추가적인 리팩토링을 할 때에는 중요한 원칙을 세우고 차근차근 진행해보니 이전 코드 보다는 훨씬 나아진 것 같았다. 또한 동료 개발자 두분과 코드 리뷰 및 온라인 밋업으로 리뷰와 궁금증을 해결하는 시간을 가졌었는데 이 시간도 굉장히 재밌고 유익했다. 이른 시간 안에 3회차가 시작되어 다시 해볼 수 있다면 좋겠다.

이 모의고사는 Toss의 프론트엔드 개발자 채용에서 실제로 사용했던 과제를 풀어보는 서비스인데, 단순히 문제만 푸는 것이 아니라 다른 사람들의 코드를 보고 토론할 수 있으며, 라이브 해설 강의까지 제공된다니 참여하지 않을 이유가 없었다.

과제 제출

요구사항을 훑어보던 중, 가장 강조된 문구가 눈에 들어왔다.

서비스의 유지보수나 장기적인 확장성을 고려한 설계, 추상화 관점에 집중해서 기능을 구현해주세요.

이 문장을 보자마자 생각이 많아지기 시작했는데, 결과적으로 이것이 패착이었다.

• 컴포넌트와 함수의 네이밍은 어떻게 명확하게 할까?
• 컴포넌트 분리는 어느 수준까지 해야 할까?
• 상태를 부모 컴포넌트에서 관리해서 내려줄까, 아니면 전역 상태 도구를 도입할까?
• 폴더 구조를 어떻게 하지? 응집성을 위해 pages 내부에서 분리를 할까? 아니면 FSD 이론을 어느 정도 적용해서 관심사를 분리할까?
• 라이브러리는 어떻게 사용을 해야 할까?
• README 작성까지... 시간이 될까?

지금 다시 생각해도 고민거리가 많은데, 과제를 풀 당시에는 훨씬 더 복잡한 생각들이 머릿속을 채웠던 것 같다. 차라리 침착하게 요구사항을 먼저 분석하고, 기본적인 구현을 마친 뒤에 설계를 다듬었으면 훨씬 나았을 것이라는 아쉬움이 든다.

라이브 세션

라이브 해설에는 평소 블로그 글을 인상 깊게 읽었던 재엽님과, 원티드 프리온보딩을 재밌게 강의해주셨던 종택님이 나오셔서 혼자 반가운 마음이 들었다.

세션은 실시간 코딩, PR 및 Discussion 리뷰, Q&A로 구성되었는데, 보는 내내 고개를 끄덕이고 감탄하느라 바빴다. 새삼 공부 더 해야겠다는 자극을 강하게 받은 유익한 시간이었다.

배운 점

라이브를 통해 배운점들을 정리해봤다.

• useState는 '구현'

const [view, setView] = useState();

단순히 view를 관리하는 상태처럼 보이지만, 이는 전역 상태, 브라우저 스토리지, URL 등 다양한 방식으로 구현될 수 있다. 이것 또한 추상화의 영역이다. (useState만이 아니라 다른 부분에서도 ‘구현’이라는 말을 많이 하셨다. 이건 그냥 예시..)

• 인터페이스는 표준을 따르자 컴포넌트 인터페이스 설계 시 불필요한 창의력보다는 일반적인 인터페이스를 따르는 것이 좋다. (Input은 Input답게!)

• Props Drilling Props Drilling을 해결하기 위해 무조건 전역 상태를 도입하는 것은 좋지 않다. Drilling은 주로 역할 분리가 제대로 되지 않았거나, 하나의 컴포넌트가 너무 많은 책임을 질 때 발생한다. 구조적인 역할 분리를 통해 해결하는 것이 우선이다.

• 이상적인 형태를 먼저 떠올리자 코드를 작성하기 전, 요구사항 문서를 보고 이상적인 구조를 먼저 상상하는 습관을 들이자.

• UI와 코드는 1:1 매핑 UI를 지나치게 쪼개려 하지 말고, 시각적인 UI 구조와 코드의 형태가 매핑되도록 작성하면 유지보수하기 좋다.

• 추상화와 재사용성 책임 단위로 올바르게 추상화를 하면 재사용성은 자연스럽게 따라온다.

마치며

비록 요구사항 충족에 급급해 생각만큼 구현을 다 마치지는 못했지만, 모의고사라는 프로세스를 경험해 본 것 자체가 좋았다. 다른 분들의 코드를 보며 배운 점도 많았고, 깃허브 디스커션에서의 수준 높은 토론들을 보며 생각의 폭을 넓힐 수 있었다.

사람은 생각하는 동물이다. 앞으로도 구현에만 매몰되지 말고, 끊임없이 생각하고 고민하는 개발자가 되어야겠다.

📄풀이

누적합

처음 문제를 보고 해석했을 때, 떠올린 풀이인데 정확성은 맞출 것 같았지만 효율성은 통과하지 못할 것 같았습니다. 그래도 일단 정확성이라도 맞추자라는 생각으로 푼 풀이입니다.

const calculate = (board, r1, c1, r2, c2, degree) => {
    for (let i=r1; i<=r2; i++) {
        for (let j=c1; j<=c2; j++) {
            board[i][j] += degree;
        }
    }
}

const solution = (board, skill) => {
    skill.forEach(v=>{
        const [type, r1, c1, r2, c2, degree] = v;
        calculate(board, r1, c1, r2, c2, type===1 ? -degree : degree);
    });

    return board.map(v=>v.filter(v2=>v2>0).length).reduce((acc,cur)=>acc+cur);
}

정확성은 전부 맞췄지만 효율성은 전부 나가리였습니다. 해결 방법이 너무 떠오르지 않아서 카카오 기술 블로그에서 해설을 봐버렸습니다. 카카오 해설

누적합의 개념은 알고 있었지만 2차원 배열을 활용해 누적합하는 것은 정말 신기했습니다. 그리고 더욱 더 공부를 해야된다는 것을 느꼈습니다...

(0,0)부터 (2,2)까지 n만큼의 변화를 줘야한다면

                                              아래, 오른쪽으로 누적합한 결과
[0, 0 ,0, 0]    =>          [n, 0, 0, -n]       =>         [n, n, n, 0]
[0, 0 ,0, 0]             [0, 0, 0, 0]                 [n, n, n, 0]
[0, 0 ,0, 0]             [0, 0, 0, 0]                [n, n, n, 0]
[0, 0 ,0, 0]             [-n, 0, 0, n]                [0, 0, 0, 0]

이런 식으로 (r1, c1) += n, (r2+1, c1) += -n, (r1, c2+1) += -n, (r2+1, c2+1) += n 을 하고 아래와 오른쪽 방향으로 각각 누적합을 해주면 됩니다.

누적합한 결과를 기존의 board와 합쳐주게 되면 최종적으로 공격과 회복이 완료된 board가 나오게 되고 0 이하로 내려간 칸의 갯수를 세주어서 반환한다면 정답이 나오게 됩니다.

👨‍💻코드

const prefixSum = (pSum, skill) => {
    skill.forEach(v=>{
        const [type, r1, c1, r2, c2, degree] = v;
        const d = type === 1 ? -degree : degree;
        pSum[r1][c1] += d;
        pSum[r2+1][c1] += -d;
        pSum[r1][c2+1] += -d;
        pSum[r2+1][c2+1] += d; 
    });
    for (let r = 0; r < pSum.length; r++) { // 아래로 누적합
        for (let c = 1; c < pSum[0].length; c++) {
            pSum[r][c] += pSum[r][c - 1];
        }
    }
    for (let r = 1; r < pSum.length; r++) { // 오른쪽으로 누적합
        for (let c = 0; c < pSum[0].length; c++) {
            pSum[r][c] += pSum[r - 1][c];
        }
    }
}

const solution = (board, skill) => {
    const pSum = Array.from({length: board.length+1}, ()=>Array(board[0].length+1).fill(0));
    prefixSum(pSum, skill);

    for (let r = 0; r < board.length; r++) {
        for (let c = 0; c < board[0].length; c++) {
            board[r][c] += pSum[r][c];
        }
    }

    return board.map(v=>v.filter(v2=>v2>0).length).reduce((acc,cur)=>acc+cur);
}

📄풀이

완전탐색

• 문자열의 길이가 1이 넘고, 문자열의 끝자리가 A라면 A를 제거하고 재귀한 것이 True라면 return True
• 문자열의 길이가 1이 넘고, 문자열의 첫자리가 B라면 B를 제거하고 뒤집은 다음 재귀한 것이 True라면 return True
• T와 S가 같아졌다면 return True

조건에 만족하지 않게 된다면 return False

재귀한 결과가 True라면 1을 출력하고 False라면 0을 출력합니다.

👨‍💻코드

def dfs(T):
  if T==S:
    return True 
  if len(T) > 1 and T[-1]=='A' and dfs(T[:-1]):
    return True
  if len(T) > 1 and T[0]=='B' and dfs(T[1:][::-1]):
    return True

  return False

S = input()
T = input()
if dfs(T):
  print(1)
else:
  print(0)

📄풀이

구현

findMax 함수

• 밑 주사위에서 윗면의 숫자의 인덱스를 찾습니다.
• 찾은 인덱스로 윗 주사위의 밑면이 되어야 하는 숫자를 찾습니다.
• 찾은 숫자와 밑면, 윗면의 숫자들을 제외한 숫자들의 최댓값을 반환합니다.

첫번째 주사위의 모든 면으로 경우의 수를 구해서 최댓값을 구해서 출력합니다.

👨‍💻코드

n = int(input())
dices = [list(map(int, input().split())) for _ in range(n)]

def findMax(dice, num):
  for idx in range(6): # 밑 주사위의 윗면의 숫자의 인덱스 찾기
    if dice[idx] == num:
      break
  # 윗 주사위의 밑면이 되어야 하는 숫자를 찾아서 넘겨주기 ( 1=6, 2=4, 3=5 )
  if idx == 0:
    return [dice[5], max(dice[1], dice[2], dice[3],dice[4])]
  elif idx == 1:
    return [dice[3], max(dice[0], dice[2], dice[4],dice[5])]
  elif idx == 2:
    return [dice[4], max(dice[0], dice[1], dice[3],dice[5])]
  elif idx == 3:
    return [dice[1], max(dice[0], dice[2], dice[4],dice[5])]
  elif idx == 4:
    return [dice[2], max(dice[0], dice[1], dice[3],dice[5])]
  elif idx == 5:
    return [dice[0], max(dice[1], dice[2], dice[3],dice[4])]

answer = 0
for i in range(6):
  # 첫번째 주사위의 모든 면을 해보기
  next_val, total = findMax(dices[0], dices[0][i])
  for j in range(1, n):
    temp1, temp2 = findMax(dices[j], next_val)
    next_val = temp1
    total += temp2
  answer = max(answer, total) # 최댓값 구하기

print(answer)

📄풀이

다이나믹 프로그래밍

계산하기 편하게 하기 위해 배열의 첫째 줄과 각 줄의 첫번째 숫자로 0을 추가합니다.

배열을 순회하면서

현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 위쪽
현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 왼쪽
현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 좌상단 대각선

중에서 가장 큰 값을 현재 자리의 숫자로 업데이트 합니다.

업데이트한 배열의 마지막 줄에서 가장 큰 숫자를 찾아서 출력합니다.

👨‍💻코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
maze = [[0]*(M+1) for _ in range(N+1)]
for n in range(N):
  for m in range(M):
    maze[n+1][m+1] = arr[n][m]

for i in range(1, N+1):
  for j in range(1, M+1):
    maze[i][j] = max(maze[i-1][j]+maze[i][j], maze[i][j-1]+maze[i][j], maze[i-1][j-1]+maze[i][j])

print(max(maze[-1]))

📄풀이

누적합

인덱스를 맞추기 위해 빈 배열에 0을 넣어놓고, 입력 받은 숫자들의 누적합을 구해서 배열에 넣습니다.

주어진 i부터 j까지의 구간의 합은 누적합[j] - 누적합[i-1]입니다.

ex) 5, 4, 3, 2, 1 -> [0, 5, 9, 12, 14, 15] 3부터 5까지일 경우

• 5까지의 누적합=15, 2(3-1)까지의 누적합=9 -> 15-9 = 6
• 3 + 2 + 1 = 6

👨‍💻코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))
nums = [0]
for n in range(N):
  nums.append(nums[-1]+arr[n])

for _ in range(M):
  i, j = map(int, input().split())
  print(nums[j]-nums[i-1])

📄풀이

정렬

입력 받은 전화번호 배열을 정렬합니다. 정렬하면 현재 전화번호와 다음 전화번호를 비교 하기만 하면 됩니다.

두 전화번호를 비교하는 check 함수를 생성해서 앞의 전화번호가 뒤의 전화번호에 속한다면 False, 전부 통과한다면 True를 반환합니다.

check 함수가 True라면 YES, False라면 NO를 출력합니다.

👨‍💻코드

import sys

def check():
  for i in range(n-1):
    if phoneNumbers[i] in phoneNumbers[i+1][:len(phoneNumbers[i+1])-1]:
      return False
  return True

t = int(sys.stdin.readline())
for _ in range(t):
  n = int(sys.stdin.readline())
  phoneNumbers = [sys.stdin.readline().rstrip() for _ in range(n)]
  phoneNumbers.sort()

  if check():
    print('YES')
  else:
    print('NO')

📄풀이

그래프 탐색 -> BFS

이 문제는 상하좌우를 움직여서 그래프를 탐색하는 일반적인 BFS 문제에서 한 가지 테크닉이 추가된 문제입니다. 주어진 그래프의 끝을 벗어나면 무시하는 것이 아니라 처음이나 끝으로 되돌아가게 풀어야 합니다.

nx = (nx + N) % N
ny = (ny + M) % M

예를 들어, 가로 길이가 6, 세로 길이가 5로 주어진 그래프에서 좌표 (0, 0)에서 왼쪽으로 간다면 (-1, 0)이 될 것입니다. 일반적인 문제라면 제한을 벗어났으므로 무시하고 다른 방향을 탐색하겠지만 여기선 가로 길이만큼 더해준 후 다시 가로 길이로 나눈 나머지로 바꿔줍니다. (-1 + 6) % 6 = 5 -> (5, 0) (끝의 좌표)

계속 탐색하다가 상, 하, 좌, 우 방향에 갈 곳이 없다면 탐색을 종료하게 됩니다. 탐색이 종료되면 구역 하나를 탐색한 것이므로 정답을 +1 합니다.

👨‍💻코드

from collections import deque

def bfs(a, b):
  q = deque()
  q.append([a, b])
  visited[a][b] = 1

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + move[i][0]
      ny = y + move[i][1]
      nx = (nx + N) % N
      ny = (ny + M) % M
      if not visited[nx][ny] and planet[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append([nx, ny])

N, M = map(int, input().split())
planet = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
move = [[0,1],[0,-1],[1,0],[-1, 0]]
answer = 0

for i in range(N):
  for j in range(M):
    if planet[i][j] == 0 and not visited[i][j]:
      bfs(i, j)
      answer += 1

print(answer)

📄풀이

그래프 탐색 -> BFS, DP

마지막 25번 테스트케이스가 너무 안풀려서 프로그래머스 질문하기 탭에서 도움을 받아서 작성했습니다. https://school.programmers.co.kr/questions/40589

방향에 따라서 비용이 달라지기 때문에 2차원 DP 배열을 사용하여 계산할 경우 특정 좌표까지 최소비용이라도 다음좌표에서도 방향이 여러 가지기 때문에 항상 최소비용을 보장할 수 없기 때문입니다.

👨‍💻코드

function solution(board) {
  const N = board.length;
  const visited = Array(N)
    .fill()
    .map(() =>
      Array(N)
        .fill()
        .map(() => Array(4).fill(Infinity))
    ); // 3차원 dp
  const DIRECTIONS = [
    [1, 0],
    [-1, 0],
    [0, -1],
    [0, 1],
  ]; // 우,좌,상,하

  const isValid = (x, y) => x >= 0 && x < N && y >= 0 && y < N && board[x][y] !== 1; 
  // 유효한지 체크
  const q = [
    [0, 0, 0, 0],
    [0, 0, 0, 3],
  ]; // 오른쪽, 아래쪽 출발
  while (q.length) {
    const [x, y, cost, dir] = q.shift();
    for (let i = 0; i < DIRECTIONS.length; i++) {
      const nx = x + DIRECTIONS[i][0];
      const ny = y + DIRECTIONS[i][1];

      if (isValid(nx, ny)) {
        let new_cost = cost + 100; // 직선도로는 100원
        if (dir !== i) new_cost += 500;
        // dir과 i가 같지 않다는 것은 방향이 달라졌다는 뜻이므로 500원 추가 (곡선도로 600원)
        if (new_cost < visited[nx][ny][i]) {
          visited[nx][ny][i] = new_cost;
          q.push([nx, ny, new_cost, i]);
        }
      }
    }
  }

  return Math.min(...visited[N - 1][N - 1]);
}

📄풀이

백트래킹

문제를 해석했을 때 그래프가 만들어지는 것 같아서 그래프 탐색 방법을 활용하여 풀어보았습니다. 그 중 백트래킹 알고리즘을 활용하면 좋을 것 같았습니다.

1. 주어진 항공권 수 만큼 방문 확인 배열을 만들고, 종료 변수를 항공권 갯수 +1로 선언합니다.

2. backTracking 함수

   • 현재 여행 경로의 길이와 종료 변수가 같아지면 정답 배열에 여행 경로를 넣고 종료합니다.
   • 주어진 여행 경로를 순회하여 사용한 적이 없는 항공권이라면 항공권의 출발지와 도착지를 분리합니다. 현재 여행 경로의 마지막 지점과 항공권의 출발지가 같다면 방문 확인을 해주고 backTracking 함수에 도착지를 넣고 호출합니다.

3. 정답 배열을 오름차순으로 정렬한 뒤 첫 번째 배열을 반환합니다.

👨‍💻코드

const solution = (tickets) => {
  const answer = [];
  const visited = Array(tickets.length).fill(0);
  const finished = tickets.length + 1;

  const backTracking = (travelPath) => {
    if (travelPath.length === finished) {
      answer.push(travelPath);
      return;
    }
    tickets.forEach((ticket, i) => {
      if (!visited[i]) {
        const [start, end] = ticket;
        if (travelPath.at(-1) === start) {
          visited[i] = 1;
          backTracking([...travelPath, end]);
          visited[i] = 0;
        }
      }
    });
  };
  backTracking(["ICN"]);

  return answer.sort()[0];
};

📄풀이

재귀

나쁜 수열이 있는지 확인하는 check함수, check함수를 활용해 조건에 맞춰 수를 늘려가는 재귀 함수로 나눕니다.
check함수

• [1,2,3,1,2,3]인 예시가 있다면 3-2 -> 3,1-2,3 -> 1,2,3-1,2,3 순으로 확인합니다. 1,2,3-1,2,3이 존재하여 나쁜 수열이므로 이 수열은 정답이 되지 않습니다.
• False가 반환되지 않으면 좋은 수열이므로 True를 반환합니다.

requr함수

• 1,2,3을 수열에 각각 추가해보고 check함수를 통과한다면 수열에 숫자를 넣고 재귀합니다.
• 수열의 길이가 주어진 N과 같다면 수열을 출력하고 종료합니다.

👨‍💻코드

def check(nums):
  for i in range(1, len(nums)+1):
    if nums[-(i*2):-i] == nums[-i:]:
      return False
  return True

def requr(idx, nums):
  if idx == N:
    print(nums)
    exit()

  for i in '123':
    if check(nums+i):
      requr(idx+1, nums+i)

N = int(input())
requr(1, '1')

📄풀이

백트래킹

모든 후보를 다 찾아보려면 너무 비효율적이므로 조건을 걸어서 가지치기를 하는 백트래킹 알고리즘을 활용하여 풀어야 할 것 같았다.

1. 암호는 오름차순으로 정렬이 되어 있다고 하니 입력 받은 알파벳들을 정렬해줍니다.

2. 알파벳 배열을 탐색해야 하는데, 처음부터 끝까지 재귀하면 암호가 조건을 만족하지만 오름차순이 아닌 것들도 포함이 되기 때문에 이미 본 것은 포함하지 않게 인덱스(idx)를 인자로 받아서 재귀할 때 마다 1씩 늘려줍니다.

3. 주어진 암호의 길이와 현재 암호의 길이가 같아지면 자음과 모음의 갯수를 세어서 조건을 만족할 경우 출력한 다음 함수를 종료합니다.

👨‍💻코드

def dfs(length, idx):
  if length == L:
    c_cnt, v_cnt = 0, 0
    for r in result:
      if r in 'aeiou': v_cnt += 1
      else: c_cnt += 1

    if v_cnt >= 1 and c_cnt >= 2:
      print(''.join(result))

    return

  for i in range(idx, C):
    if not visited[i]:
      visited[i] = 1
      result.append(alphabet[i])
      dfs(length+1, i+1)
      visited[i] = 0
      result.pop()

L, C = map(int, input().split())
alphabet = input().split()
alphabet.sort()
visited = [0]*C
result = []

dfs(0, 0)

📄풀이

그래프 탐색

문제를 보고 해석했는데 그래프 탐색 문제인 것을 깨달았습니다. 그런데 정확히 요구하는게 뭔지 너무 헷갈렸습니다. 그래서 검색을 통해 문제 해석을 찾아봤는데 그냥 조건이 딱히 까다롭지 않은 그래프 탐색 문제였습니다.

1. defaultdict를 활용해서 p, q, r을 입력 받을 때 인접 그래프를 만들어줍니다.
2. k, v를 입력 받아서 bfs함수에 인자로 넣은 후 결과를 출력합니다.

bfs 함수

def bfs(K, num):
  visited = [0]*(len(video.keys())+1)
  cnt = 0
  q = deque()
  q.append(num)
  visited[num] = 1

  while q:
    n = q.popleft()
    for v in video[n]:
      if not visited[v[0]] and v[1] >= K:
        visited[v[0]] = 1
        cnt += 1
        q.append(v[0])

  return cnt

먼저 deque와 방문 확인할 배열, 반환할 카운트 변수를 선언해줍니다. deque에 입력받은 동영상 번호를 넣고 방문 체크를 해줍니다.

deque에서 popleft한 번호를 그래프에서 탐색합니다. 방문한 적이 없고 k가 K보다 같거나 크다면 방문 체크, 카운트 +1, deque에 동영상 번호를 추가합니다.

탐색이 종료되면 카운트를 반환합니다.

👨‍💻코드

from collections import defaultdict, deque

def bfs(K, num):
  visited = [0]*(len(video.keys())+1)
  cnt = 0
  q = deque()
  q.append(num)
  visited[num] = 1

  while q:
    n = q.popleft()
    for v in video[n]:
      if not visited[v[0]] and v[1] >= K:
        visited[v[0]] = 1
        cnt += 1
        q.append(v[0])

  return cnt

N, Q = map(int, input().split())
video = defaultdict(list)
for _ in range(N-1):
  p, q, r = map(int, input().split())
  video[p].append([q, r])
  video[q].append([p, r])

for _ in range(Q):
  k, v = map(int, input().split())
  print(bfs(k, v))

📄풀이

이분 탐색

최소 금액과 최대 금액을 반으로 나누어서 상한액으로 설정합니다.

모든 예산을 순회하여 각 예산이 상한액보다 작거나 같으면 예산을 더해주고, 크다면 상한액을 더해줍니다.

전부 더한 값이 총 예산액보다 크다면 최대 금액을 상한액에서 1을 빼준 값으로 변경하고, 작거나 같다면 최소 금액을 상한액에서 1을 더해준 값으로 변경합니다.

이 과정을 계속 반복하다가 최소 금액이 최대 금액보다 커지면 반복을 종료하고 최대 금액을 출력합니다.

👨‍💻코드

N = int(input())
budgets = list(map(int, input().split()))
M = int(input())
start, end = 0, max(budgets) # 최소 금액, 최대 금액

while start <= end:
  mid = (start+end) // 2 # 상한액
  total = 0
  for budget in budgets:
    if budget <= mid: # 요구 예산액이 상한액보다 작거나 같으면
      total += budget # 예산액 더하기
    else:
      total += mid # 크다면 상한액 더하기

  if total > M: # 전부 더한 값이 총 예산액보다 크다면 최대 금액을 상한액 -1으로 변경
    end = mid - 1
  else: # 작거나 같다면 최소 금액을 상한액 +1로 변경
    start = mid + 1

print(end)

📄풀이

그리디

0 이하의 정수를 음수, 1인 수, 나머지 양수로 나눕니다.

양수들은 큰 수 부터 올 수 있게 내림차순, 음수들은 작은 수부터 올 수 있게 오름차순으로 정렬합니다.(음수들은 작은 두 개의 수 끼리 곱해야 커지므로)

각 배열의 길이가 짝수이면 2개 씩 짝지어서 곱한 뒤 정답에 저장합니다. 각 홀수이면 마지막 수를 제거한 뒤 정답에 저장하고 나머지를 짝지어서 곱한 뒤 저장합니다. 길이가 홀수일 경우 배열의 마지막 수는 최댓값에 가장 영향을 작게 주는 수이기 때문입니다.

마지막으로 따로 모은 1들을 전부 더한 뒤에 정답을 출력합니다.

👨‍💻코드

n = int(input())
positive = [] # 양수
negative = [] # 음수
one = [] # 1만 모으기
answer = 0 # 정답
for _ in range(n):
  temp = int(input())
  if temp == 1:
    one.append(temp)
  elif temp <= 0:
    negative.append(temp)
  else:
    positive.append(temp)
positive.sort(reverse=True) # 큰 수 부터 올 수 있게 내림차순
negative.sort() # 작은 수 부터 올 수 있게 오름차순

# 배열의 길이가 짝수이면 2개 씩 짝지어서 곱한 뒤 정답에 저장
# 홀수이면 마지막 수를 제거한 뒤 정답에 저장하고 나머지를 짝지어서 곱한 뒤 저장
if len(positive)%2==0:
  for i in range(0, len(positive), 2):
    answer += positive[i]*positive[i+1]
else:
  answer += positive.pop()
  for i in range(0, len(positive), 2):
    answer += positive[i]*positive[i+1]

if len(negative)%2==0:
  for i in range(0, len(negative), 2):
    answer += negative[i]*negative[i+1]
else:
  answer += negative.pop()
  for i in range(0, len(negative), 2):
    answer += negative[i]*negative[i+1]

# 모은 1들을 전부 더하기 -> 1은 곱하는 것 보다 더하는 게 더 큼
answer += sum(one)

print(answer)

📄풀이

슬라이딩 윈도우

이 문제의 핵심은 입력 받은 문자열 중에서 a의 갯수를 구한 다음, 그 만큼의 구간을 만들어 한 칸씩 이동하며 b의 개수를 세는 것 입니다.

구한 b의 갯수와 정답을 min으로 계속 비교하여 최종적으로 가장 적은 b의 갯수를 출력하게됩니다.

또 한 가지 중요한 점은 문자열이 원형으로 이어져 있다는 점인데, 이 조건 때문에 left를 문자열의 끝까지 탐색하고 넘치는 부분은 슬라이싱하여 붙힌 다음 구했습니다.

👨‍💻코드

s = list(input())
a_cnt = s.count('a')
answer = 999999999999999
left = 0

while left < len(s):
  right = left + a_cnt
  if right > len(s):
    temp = s[left:len(s)] + s[:right-len(s)]
  else:
    temp = s[left:right]
  answer = min(answer, temp.count('b'))
  left += 1

print(answer)

📄풀이

투 포인터 or Map 활용

처음엔 투 포인터 알고리즘을 활용하여 풀다가 생각보다 잘 안풀려서 구글링을 해보았습니다.
관련 글들 중에서 Map에 관련된 굉장한 풀이법들이 있어서 풀고 많이 배웠습니다.

1. 최대 구간을 저장합니다.

2. 보석 갯수를 Set을 활용하여 구해줍니다.

3. gems 배열을 순회하는데 Map에 보석 이름이 이미 있다면 삭제한 뒤 인덱스를 갱신하여 저장합니다. 계속 저장하다가 Map의 사이즈와 보석 갯수가 같아지면 Map의 처음 value+1과 현재 인덱스 +1을 하여 구간을 만들어줍니다. 현재 구간의 차이가 처음 저장한 최대 구간의 길이의 차이보다 작다면 배열을 갱신합니다.

4. 정답 구간을 반환합니다.

👨‍💻코드

function solution(gems) {
    let answer = [1, gems.length];
    const gemsCnt = new Set(gems).size;
    const gemsMap = new Map();

    gems.forEach((gem, idx)=>{
        gemsMap.delete(gem);
        gemsMap.set(gem, idx);
        if (gemsMap.size === gemsCnt) {
            const temp = [gemsMap.values().next().value+1, idx+1];
            const tempLen = temp[1] - temp[0];
            const answerLen = answer[1] - answer[0];
            if (answerLen > tempLen) answer = temp;
        }
    });

    return answer;
}

📄풀이

완전 탐색

start가 각 기지국의 전파 전달 범위 내에 있다면 start를 전파 전달 범위의 끝 지점으로 변경합니다. 그리고 확인한 기지국을 shift로 없애줍니다.

전파 전달 범위 밖이라면 start를 전파 도달 거리 w * 2 만큼 더해주고, 정답을 +1 합니다.

조건 확인이 끝났다면 start를 +1 합니다.

👨‍💻코드

function solution(n, stations, w) {
  let answer = 0;
  let start = 0;
  stations = stations.map((v) => v - 1);

  while (start < n) {
    if (start >= stations[0] - w && start <= stations[0] + w) {
      start = stations[0] + w;
      stations.shift();
    } else {
      start += w * 2;
      answer++;
    }
    start++;
  }

  return answer;
}

📄풀이

순열

const Permutation = (arr, num) => {
  const result = [];
  if (num === 1) return arr.map((v) => [v]);

  arr.forEach((select, i, origin) => {
    const remainder = [...origin.slice(0, i), ...origin.slice(i + 1)];
    const permutation = Permutation(remainder, num - 1);
    const combine = permutation.map((v) => [select, ...v]);
    result.push(...combine);
  });

  return result;
};

순열 배열을 만들어주는 함수입니다.

const check = (uid, bid) => {
  uid = uid.sort((a, b) => a.length - b.length);
  bid = bid.sort((a, b) => a.length - b.length);

  for (let i = 0; i < uid.length; i++) {
    if (uid[i].length !== bid[i].length) return false;

    for (let j = 0; j < uid[i].length; j++) {
      if (bid[i][j] === "*") continue;
      if (uid[i][j] !== bid[i][j]) return false;
    }
  }
  return true;
};

인자로 받은 유저아이디배열과 불량사용자아이디배열을 아이디의 길이 기준으로 정렬해준 후, 비교합니다. 두 아이디의 길이가 같지 않다면 false 반환, 두 아이디의 각 자리의 알파벳이 같지 않다면 false를 반환해주고, 조건을 전부 만족한다면 true를 반환합니다.

const permutation = Permutation(user_id, banned_id.length);
const checkArr = permutation.filter((v) => check(v, banned_id));
const set = new Set();
checkArr.forEach((v) => set.add(v.sort().join("")));

순열을 사용하여 불량사용자아이디 갯수만큼 유저아이디 경우의 수를 모두 만들어 줍니다.

check 함수를 통해 조건을 만족하는 아이디들을 가진 배열을 만듭니다.

아이디들을 정렬한 뒤 join하여 문자열로 만들어준 후, set을 활용하여 중복을 제거합니다.

set의 size을 반환하면 정답이 나옵니다.

👨‍💻코드

const Permutation = (arr, num) => {
  // 시간복잡도 O(n!)
  const result = [];
  if (num === 1) return arr.map((v) => [v]);

  arr.forEach((select, i, origin) => {
    const remainder = [...origin.slice(0, i), ...origin.slice(i + 1)];
    const permutation = Permutation(remainder, num - 1);
    const combine = permutation.map((v) => [select, ...v]);
    result.push(...combine);
  });

  return result;
};

const check = (uid, bid) => {
  // 시간복잡도 O(n^2)
  uid = uid.sort((a, b) => a.length - b.length);
  bid = bid.sort((a, b) => a.length - b.length);

  for (let i = 0; i < uid.length; i++) {
    if (uid[i].length !== bid[i].length) return false;

    for (let j = 0; j < uid[i].length; j++) {
      if (bid[i][j] === "*") continue;
      if (uid[i][j] !== bid[i][j]) return false;
    }
  }
  return true;
};

function solution(user_id, banned_id) {
  // 시간복잡도 O(n!)
  const permutation = Permutation(user_id, banned_id.length);
  const checkArr = permutation.filter((v) => check(v, banned_id));
  const set = new Set();
  checkArr.forEach((v) => set.add(v.sort().join("")));

  return set.size;
}