Problem Solving/코딩테스트 후기

🌱 PS/알고리즘 초심자의 코딩테스트 복기…
취준과정에서 한번은 꼭 보게된다는 코딩테스트. 결과는 처참했다고 밖에 할 말이 없다. 절반은 풀어야한다던데, 절반에 못미치는 성적표에 큰 기대는 하지 않기로 했다.
다만 이것도 경험이니 기억에 의존해 문제를 복기해보려고 한다.

✏️ 예산에 맞는 물건 구매하기

두 가지 물품(첫 번째 물품 a, 두 번째 물품 b)을 구매할 수 있도록 예산(budget)을 배정받았다. 각 물품은 여러개 구매할 수 있고, 구매하지 않아도 괜찮다.
물품을 구매하는 경우의 수 중에서 예산에 딱 맞게 구매하는 방법의 가짓수를 구하는 solution을 완성하라.

(a, b, budget의 제한조건과 시간/메모리 조건이 있었는데, 입력 매개변수가 자연수라는 것만 기억나고 디테일한 조건은 까묵음..)

조건에 맞는 경우의 수를 구해야하고, 조건에 맞는 경우의 수를 구현해야하니 가장 먼저 든 생각은 당연히 완전탐색 이었다. 동시에 ‘100% 시간초과 날것 같은데..’ 라는 생각도 들었지만, 일단 냅다 코드를 짜기 시작했다.

잘은 기억나지 않지만 어찌어찌 이중반복문을 만들었는데.. 테스트 돌리니 역시나 시간초과로 실패했다고 뜨더라. 그래도 당황하지 말고 일단 제출이라도 해볼 걸. 더이상의 유의미한 사고를 이어나가지 못하고 시간만 쏟은 셈이었다.

def solution(a, b, budget) {
  count = 0;
  d = 0;

  if a == b and (budget % 2) == 0:
    d = budget // (4 * a)
    count += 1

  a = max(a, b)
  b = min(a, b)

  da = budget // a
  mod budget % a
  db = mod // b

  for i in range(da + 1):
    for j in range(db + 1):
      if mod % b == 0:
        count += 1
        break
  
  answer = count
  return answer; 
}

부끄럽지만 제출한 답안을 다시 보니, 당시 내가 무슨 생각이었는지 모르겠다. 중복되는 연산을 먼저 제외하고 싶었던 것 같은데, 이중반복 구조인 건 변하지 않았으니 문제 해결에는 전혀 도움안되고 코드수만 늘린 꼴 아닌가. 다시 봐도 별다른 아이디어가 떠오르지 않는 걸 보니 공부가 부족해서 그렇겠지😕

익숙하지 않은 환경에서 자바의 엄격한 문법이 발목을 잡을까봐 파이썬으로 테스트를 치렀는데 ㅎ.. 엄청난 오산이었다. 최종 제출한 답안 이전에 작성한 코드가 전혀 기억나지 않는 걸 보면, 어지간히 긴장하고 정신이 없었나보다. 그 때로 되돌아간다면 아래와 같이 좀더 익숙한 자바로 빠르게 답안 제출하고, 다른 문제에 더 시간을 쏟을 것 같다.

public int solution(int a, int b, int budget) {
  int answer = 0;
  int tot = 0;

   for (int i = 0; i * a <= budget; i++ ) {
    for (int j = 0; j * b <= budget; j++) {
      tot = a*i + b*j
      if (budget == tot) answer++
    }
   }
  return answer; 
}

✏️ 대표 선출하기

투표로 A, B 중 대표를 정하려고 한다. A, B 그리고 기권표 C 셋 중에 하나에 투표권을 행사할 수 있고, 투표결과(vote)는 “AABBCCABCAAAA”와 같은 문자열로 주어진다. 문자열의 길이는 전체 투표에 참여한 인원 수와 같고, 더 많은 득표를 한 쪽이 대표로 선출된다. 단 기권표가 과반수 이상일 때는 선출하지 않는다.
결과는 ‘A’, ‘B’ 로 출력하고, A와 B가 동점일 경우 공동대표를 의미하는 ‘AB’로 출력한다(BA 아님). 과반수 이상의 기권표로 대표를 선출하지 못한 경우, ‘C’로 출력한다.

(더이상의 디테일은 기억나지 않음 이슈..)

조건에 맞는 입출력 솔루션을 구한하는 문제. 2번 문제였던 걸로 기억하는데.. 문제번호랑 난이도는 관계가 없나보다. 정확성을 보는 문제였나본데, if문을 써서 구현했다.

그런데 여기에도 사소한 실수가 있었다. 중간에 런타임에러(NameError)를 잡는 과정에서 불필요한 조건(b == 0)을 추가했는데 이걸 지운다는 걸 까먹고 그냥 제출해버린 것🥲 결과에 영향을 미치는 조건은 아니지만, 깔끔하지 못한 코드를 답으로 제출하게 되어 아쉬움이 남는다.

def solution(vote) {
  int answer = "";
  a = vote.count("A")
  b = vote.count("B")
  c = vote.count("C")

  if c >= (len(vote)/2):
    answer = "C"
  else: 
    if a == b:
      answer = "AB"
    elif max(a, b) == a or b == 0: 
      answer = "A"
    else:
      answer = "B"

  return answer; 
}

✏️ 타겟 합 구하기

0~9까지 정수를 가진 배열 numbers가 입력으로 주어질 때, numbers에 있는 자연수에 부호(+, -)를 붙인 전체 합이 0이 되는 경우의 수를 구하는 솔루션을 구현하라

예를 들어 numbers = [1, 1, 1, 1] 가 주어질 때, 가능한 경우는 [+1, +1, -1, -1], [+1, -1, +1, -1], [+1, -1, -1, +1]… 등이 있다.

이 문제도 조건이 더 있었던 것 같은데…

비슷한 문제를 백트래킹/재귀함수로 풀었던 기억이 있어서 시도해봤는데, 공부가 부족한 탓인지 이 문제도 시간초과 문제로 완벽한 답을 도출하지는 못했다.

내 아이디어는 다음과 같다.
현재 index와 부분합(sum, 초기값 0)을 매개변수로 전달해서 현재까지의 부분합(sum)이 0인 경우에만 1을 반환해 해당 경우의 수를 카운트한다. 그리고 다음 숫자를 탐색할때, 현재 index에 해당하는 숫자를 sum에 더하고(+numbers[idx]) 빼는(-numbers[idx]) 두 가지 경우를 모두 탐색하도록 한다.(재귀호출)

결과적으로는 70점짜리 솔루션이었는데, 아무래도 재귀로 풀기에는 numbers의 개수가 많았던 것 같다. 문제 조건에 배열의 개수가 있었던 것 같기도 하고.. 다른 어떤 방법으로 구현할 수 있는걸까🤔

def solution(numbers): {
  
  def fn(idx, sum):
    if idx == len(numbers):
      return 1 if sum == 0 else 0

    return fn(idx+1, sum+numbers[idx]) + fn(idx+1, sum-numbers[idx])

  answer = fn(0, 0)    

  return answer; 
}

🖍 연속되는 자연수

자연수 1부터 차례대로 수를 나열한 문자열 A( = 123456789101112131415…)와 어떤 자연수 n이 주어질 때, A의 n번 째에 위치한 수를 알아내기 위한 솔루션을 구현하라
예를 들어 5번 째에 위치한 수는 5, 15번째에 위치한 수는 2이다.

수능 공부할 때나 보던 문제 같은데… 풀지 못 한 두 문제 중에 상대적으로 문제가 짧고 간단해서 기억하고 있는 문제.숫자가 반복되니까 점화식을 이용해 풀 수 있을 것 같았는데, 아직 풀지는 못했다🫥.
나중에라도 코테실력이 좀 쌓이면 풀 수 있을지도 모르니 일단 기록용으로 남겨두어야지.