hyeonnnnn

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/150367

🛎️  풀이 과정

두 가지의 과정이 필요하다.

1. 포화 이진 트리 만들기
2. 부모, 자식 관계 재귀적으로 확인하기

포화 이진트리를 만들기 위해서는 2^n - 1꼴의 자릿수를 가져야한다.
그리고 확인할 리스트(num)와 해당 리스트의 부모(parent)를 재귀적으로 확인한다.
해당 리스트의 가장 탑노드(child)는 파라미터로 보낸 부모(parent)의 자식이다.
따라서 왼쪽, 오른쪽의 child를 확인해서 parent와 비교한다.

두 가지의 과정이 필요하다는 것까지 확인했지만,
구현에 어려움을 느껴 블로그를 참고하였다.

💻  풀이

import math

def is_tree(num, parent):
  if num:
    mid = len(num) // 2
    # 자식이 있는지 없는지 확인
    child = num[mid] == "1"
  else:
    return 1

  if child and not parent:
    return 0
  else:
    return is_tree(num[:mid], child) and is_tree(num[mid+1:], child)

def check(num):
  if num == 1: return 1

  # 2진수 변환
  b_num = bin(num)[2:]

  # 2^n - 1꼴의 자릿수를 가져야함.
  digit = 2 ** (int(math.log(len(b_num), 2)) + 1) - 1
  b_num = "0" * (digit - len(b_num)) + b_num

  # 자식이 있는 부모가 0이 아닌지 확인
  if b_num[len(b_num) // 2] == "0":
    return 0
  else:
    return is_tree(b_num, 1)

def solution(numbers):
  answer = []
  for num in numbers:
    answer.append(check(num))
  return answer

print(solution([63, 111, 95, 1, 0]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/152995

🛎️  풀이 과정

근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬한다.
그리고 동료 평가 점수의 max값을 저장하기 위한 변수를 선언하고 가장 첫번 째 동료 평가 점수를 넣어준다. (여기서는 max_y)
이 max_y값은 현재 보다 근무 태도 점수가 높은 직전 동료들 중 가장 높은 동료 평가 점수를 가지고 있다.

여기서 동료 평가 점수를 오름차순으로 정렬하는 이유가 나타나는데,
오름차순으로 정렬했을 때 max_y값을 가지고 비교하게 되면
[2, 1], [2, 2] -> 둘 다 인센티브 후보
[2, 2], [2, 1] -> [2, 1]은 후보에서 탈락
으로 오류가 생긴다.

따라서 내림차순 / 오름차순으로 정렬하면
[[3, 2], [3, 2], [2, 1], [2, 2], [1, 4]]
다음과 같고, max_y의 초기값에는 2가 들어간다.

여기서 만약 현재 반복문의 위치가 [1, 4]라고 했을 때, 현재까지의 max_y는 2가 된다.
근무 태도 점수인 1은 작지만 max_y인 2보다 동료 평가 점수인 4가 크기 때문에 인센티브 후보가 된다.

완호의 등수를 구하기 위해 인센티브 후보일 시, 완호의 점수 합과 비교한다. (answer)

💻  풀이

def solution(scores):
  wanho = scores[0]
  wanho_sum = sum(scores[0])
  scores.sort(key=lambda x: (-x[0], x[1]))
  answer, max_y = 1, scores[0][1]

  for index, score in enumerate(scores):
    if score[1] < max_y:
      if score == wanho:
        return -1
      scores[index] = [-1, -1]
    else:
      max_y = score[1]
      if wanho_sum < sum(score):
        answer += 1

  return answer

print(solution([[2,2], [1,4], [3,2], [3,2], [2,1]]))

💻  풀이 (시간초과)

def solution(scores):
  # 완호의 점수 합
  wanho = scores[0][0] + scores[0][1]
  rank = 0
  for index, score in enumerate(scores):
    if index != 0 and score[0] + score[1] <= wanho:
      continue
    for s in scores:
      if score[0] < s[0] and score[1] < s[1]:
        if index == 0:
          return -1
        break
    else:
      rank += 1
  return rank

print(solution([[2,2], [1,4], [3,2], [3,2], [2,1]]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

🛎️  아이디어

- 기본 bfs + 끝까지 직진

1. 다음 위치가 범위 안에 있는지, 장애물이 있는 곳인지 확인

2-A. 다음 위치로 이동이 가능하다면 계속 이동 (continue)

2-B. 다음 위치로 이동이 불가능하다면 직전 위치 queue에 append, cost + 1 (break)

💻  풀이

from collections import deque

def bfs(board):
  row, col = len(board), len(board[0])

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  visited = [[False] * col for _ in range(row)]

  queue = deque()

  # 출발점 찾기
  for i in range(row):
    r_index = board[i].find("R")
    if r_index != -1:
      queue.append((i, r_index, 0))
      visited[i][r_index] = True
      break

  while queue:
    x, y, cost = queue.popleft()

    if board[x][y] == "G":
      return cost

    for i in range(4):
      nx, ny = x, y

      while True:
        nx += dx[i]
        ny += dy[i]

        # 계속 갈 수 있으면
        if 0 <= nx < row and 0 <= ny < col and board[nx][ny] != "D":
          continue
        # 갈 수 없으면 바로 직전 자리 append
        else:
          if not visited[nx - dx[i]][ny - dy[i]]:
            queue.append((nx - dx[i], ny - dy[i], cost + 1))
            visited[nx - dx[i]][ny - dy[i]] = True
            break
          else:
            break

  return -1

def solution(board):
  return bfs(board)

print(solution(["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/118667

🛎️  아이디어

- 1차 아이디어
  queue이기 때문에 둘다 list -> queue 형태로 만들어서 popleft() 사용

- 2차 아이디어
  queue1, queue2를 연결해서 하나의 리스트로 만든 후 그 안에서 규칙을 찾는다.
  -> 예외 내용으로 인해 정규식이 나오지 않음.

- 3차 아이디어
  블로그 참고해서 합이 큰 큐 -> 합이 작은 큐로 원소를 하나씩 이동시키는 아이디어를 얻음
  + while True로 시간초과 걸려서 찾아본 결과 300000로 제한 걸거나 중간에 count를 넣어서하는 방법이 있음.

💻  풀이

from collections import deque

def solution(queue1, queue2):
  q1, q2 = deque(queue1), deque(queue2)
  sum1, sum2 = sum(q1), sum(q2)

  for i in range(300000):
    if sum1 == sum2:
      return i
    elif sum1 > sum2:
      num = q1.popleft()
      q2.append(num)
      sum1 -= num
      sum2 += num
    else:
      num = q2.popleft()
      q1.append(num)
      sum2 -= num
      sum1 += num
  return -1

print(solution([3, 2, 7, 2], [4, 6, 5, 1]))

❓  문제

🛎️  아이디어

1. 출차 기록이 없는 차 번호를 찾는다.
    a. 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우가 없기 때문에 입출차 개수가 홀수라면 출차 기록이 한 개 부족한 것이다.
    b. 23:39로 출차 기록을 추가해준다.

2. 차량 번호 - 시간 - 내역 순으로 정렬을 한다.
    a. 내역 정렬을 하면 알파벳 순으로 IN - OUT이 정렬된다.

3. 차량 별 주차 누적 시간을 계산한다.
    a. 출차 시간인 경우 앞 인덱스의 시간(입차)의 차이를 구해서 더해준다.

4. 최종 요금을 구해준다.
    a. 올림을 사용한다고 했기 때문에 math를 임포트해서 ceil 함수를 사용한다.

💻  풀이

import math
from collections import Counter

def solution(fees, records):
  default_time, default_fee, unit_time, unit_fee = fees

  # 차 번호 별 입출차 갯수 계산
  car_numbers = dict(Counter(map(lambda x: x.split()[1], records)))

  # 출차 기록이 없는 번호는 23:59 추가
  for car in car_numbers.items():
    if car[1] % 2 != 0:
      records.append(f'23:59 {car[0]} OUT')

  # 차량 번호, 시간, 내역 순으로 정렬
  records.sort(key=lambda x: (x.split()[1], x.split()[0], x.split()[2]))
  # ['06:00 0000 IN', '06:34 0000 OUT', '18:59 0000 IN', '23:59 0000 OUT', '07:59 0148 IN', '19:09 0148 OUT', '05:34 5961 IN', '07:59 5961 OUT', '22:59 5961 IN', '23:00 5961 OUT']

  # 차량 별 누적 시간
  sum_time = {}
  for index, record in enumerate(records):
    time, car, history = record.split()

    # 출차 시간인 경우
    if history == "OUT":
      # 입차 시간
      in_time = records[index - 1].split()[0]
      sub_hour = int(time.split(':')[0]) - int(in_time.split(':')[0])
      sub_minute = int(time.split(':')[1]) - int(in_time.split(':')[1])

      # 실제 주차 시간
      sub_time = 60 * sub_hour + sub_minute

      if car in sum_time:
        sum_time[car] += sub_time
      else:
        sum_time[car] = sub_time

  answer = []
  for time in sum_time.values():
    # 최종 요금
    if time <= default_time:
      answer.append(default_fee)
    else:
      answer.append(default_fee + math.ceil((time - default_time) / unit_time)  * unit_fee)

  return answer

print(solution([180, 5000, 10, 600], ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"]))

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/160585

🛎️  아이디어

1. 3x3에서 3개가 연결될 수 있는 경우의 수는 8개이다.
    a. 8개 뿐이기 때문에 경우의 수를 직접 만들어준다.

2. 경우의 수를 돌면서 해당 인덱스의 데이터들이 같으면 winner list에 저장해준다.

3. board에서 O과 X의 개수를 저장한다.

4. 이 판이 정상적인지 확인한다.
    a. winner_list의 길이는 3 이상일 수 없다. (O 또는 X가 여러 개 완성된 경우)
    b. winner_list에서 중복 제거를 한 후 길이는 2일 수 없다. (O, X 모두 완성한 경우)
    c. winner_list의 길이가 1인 경우
        ㄱ. 승자가 O인 경우 -> O가 선공이기 때문에 O개수가 X개수보다 1이 많아야 한다.
        ㄴ. 승자가 X인 경우 -> " O의 개수와 X의 개수가 같아야한다.
    d. winner_list의 길이가 0인 경우, O의 개수는 X의 개수와 같거나 1개 커야한다.

💻  풀이

def solution(board):
  wins = [[[0,0], [0,1], [0,2]],
         [[1,0], [1,1], [1,2]],
         [[2,0], [2,1], [2,2]],
         [[0,0], [1,0], [2,0]],
         [[0,1], [1,1], [2,1]],
         [[0,2], [1,2], [2,2]],
         [[0,0], [1,1], [2,2]],
         [[2,0], [1,1], [0,2]]]

  # 승자 확인
  winner_list = []
  for win1, win2, win3 in wins:
    if board[win1[0]][win1[1]] == board[win2[0]][win2[1]] == board[win3[0]][win3[1]]:
      winner = board[win1[0]][win1[1]]
      if winner != '.':
        winner_list.append(winner)

  # O, X 각각의 개수
  o_num = sum(map(lambda x: x.count('O'), board))
  x_num = sum(map(lambda x: x.count('X'), board))

  # 3개가 연결된 개수가 2이상이거나 O, X 모두 완성된 경우
  if len(winner_list) > 2 or len(set(winner_list)) == 2:
    return 0
  # 승자가 O 또는 X인 경우
  elif len(winner_list) == 1:
    if winner_list[0] == 'O':
      return 1 if o_num == x_num + 1 else 0
    else:
      return 1 if o_num == x_num else 0
  # 승자가 없는 경우
  else:
    return 1 if o_num == x_num + 1 or o_num == x_num else 0

❓  문제

🛎️  아이디어

1. 캐시 교체 알고리즘인 LRU를 구현하기 위해 deque를 사용한다.

2. 도시 이름을 하나씩 가져온다.
    a. 만약 deque안에 있으면(hit) 제거 후 time += 1
    b. deque안에 없으면(miss) 가장 왼쪽 요소 제거 후 time += 1 (LRU가 가장 오래된 요소를 제거하기 때문)

3. 해당 도시를 큐에 넣어준다.

** cache가 0인 경우 예외 처리가 필요함. -> hit인 경우가 없기 때문에 city개수 * 5를 리턴한다.

💻  풀이

from collections import deque

def solution(cacheSize, cities):
  if cacheSize == 0:
    return len(cities) * 5

  time = 0
  cache = deque([0 for i in range(cacheSize)])

  for city in cities:
    city = city.lower()
    if city in cache:
      cache.remove(city)
      time += 1
    else:
      cache.popleft()
      time += 5
    cache.append(city)
  return time

❓  문제

파일명 정렬

🛎️  아이디어

1. sorted를 사용한다.
    a. lambda 식을 사용해서 key값을 두 개 넣어준다.
    b. 키 두 개는 각각 re를 사용해서 head, number 부분을 가져온다.
        ㄱ. 문자열에서 숫자 부분을 가져와서 해당 숫자 기준으로 자른다. -> 인덱스 0이 head가 된다.
        ㄴ. head 부분은 대소문자 구분을 하지 않기 위해 lower을 사용한다.

💻  풀이

import re

def solution(files):
  # head 기준으로 정렬 -> number 기준으로 정렬
  return sorted(files, key= lambda x: (x.split(re.findall('\d+', x)[0])[0].lower(), int(re.findall('\d+', x)[0])))

❓  문제

피로도

🛎️  아이디어

1. permutations를 사용해서 던전의 수만큼의 range 순열을 만든다.

2. 각각의 순열에서 통과한 던전의 수를 보관할 answer 배열을 만든다.

3. permutations로 생성한 순열들을 돌면서 피로도 계산을 한다.

4. answer 배열에서의 가장 큰 값을 return 한다.

💻  풀이

from itertools import permutations

def solution(k, dungeons):
  permutaion = list(permutations(range(len(dungeons)), len(dungeons)))
  answer = []

  for pmt in permutaion:
    # 통과한 던전 수
    pass_num = 0

    # 초기 피로도
    fatigue = k

    for p in pmt:
      if fatigue >= dungeons[p][0]:
        fatigue -= dungeons[p][1]
        pass_num += 1

    answer.append(pass_num)

  return max(answer)

❓  문제

땅따먹기

🛎️  아이디어

1. 2번째 행부터 돌면서 윗 줄의 최댓값을 더해준다. 단 본인 열은 제외한다.

2. 마지막행에서는 이전 행까지의 최댓값들을 더한 값이 있음. 따라서 마지막행에서의 max값을 리턴한다.

💻  풀이

def solution(land):
  row = len(land)
  column = len(land[0])

  for r in range(1, row):
    for c in range(column):
      land[r][c] += max(land[r - 1][:c] + land[r - 1][c + 1:])

  return max(land[row - 1])

print(solution([[1,2,3,5],[5,6,7,8],[4,3,2,1]]))