코딩 테스트 풀이 - 2022 카카오 블라인드 1차 (1~4번 문제)

2021/09/11(일) 14:00~19:00 진행되었던 카카오 블라인드 1차 코딩테스트 문제 풀이 게시물입니다.

코드나 문제를 상세히 올려도 되는지 모르겠어서 간략히만 해설 합니다.

제가 아직 실력이 부족하여 4번까지만 TC ALL AC를 맞아서 우선은 4번까지 해설합니다.
혹시나 문제가 되면 글 바로 내리겠습니다.

 

2022 KAKAO BLIND RECRUITMENT

 

1번 문제

---

핵심 키워드 : 구현, 딕셔너리

 

문제 내용

• 유저들끼리 서로 신고함. 한번에 1명의 유저를 신고가능 (A B = A가 B를 신고함)
• k번 이상 신고받으면 방출되면서 유저신고한 모든 사람들한테 신고처리 메일을 보냄
  
  

풀이

총 3개의 딕셔너리 만든다.

1. reported_cnt_list[유저명] : 신고된 횟수
2. report_me_user_list[유저명] : [날신고한 유저1, 날신고한 유저2, ...]
3. mail_list[유저명] : 신고처리 메일 받은 횟수

신고 리스트 반복.

• ex) A가 B를 신고을 경우
• reported_cnt_list[B] +1 : B의 신고받은 횟수 1 증가
• report_me_user_list[B].append(A) : B를 신고한 사람 목록에 A추가
  
  

신고된 횟수가 k이상인것들 뽑아서 그 유저의 메일통보 횟수 증가

mail_list[유저명] +1

 

 

 

2번 문제

---

핵심 키워드 : 진법 변환, 소수

 

문제 내용

• 양의 정수 n 을 k진법으로 변환 후 조건에 맞는 소수 개수 리턴

 

풀이

먼저 진법 변환 함수, 소수 판별 함수를 준비한다.

# 진법 변환 (10진수 → n진수)
def to_radix(n, b):
    if n < b:
        return str(n)
    s = to_radix(n//b, b)
    return s + str(n%b)

# 소수 판별 (True/False)
def prime_check(n):
    if n == 1 :
        return False
    for div in range(2,int(math.sqrt(n))+1):
        if n%div == 0:
            return False
    return True

 

이중 for문을 돌면서 문자열[i~j]이 조건에 만족하는지 확인

 

조건 

• 문자열[i~j]가 0을 포함하지 않고 소수인지 확인.
  → 0P, P0, 0P0 형태 중 1개인지 확인
• 문자열이 0을 포함하지 않고 소수인지 확인 (P형태)
  
  

(잡담)

진법 변환 방법이 생각이 안 나서 찾아봤던 문제였다.
웃긴건 처음에 찾아왔던 진법 변환 함수가 제대로 작동 안되는 경우가 있는 함수여서 다시 찾느라 5~10분 정도를 허비해버렸다.

 

3번 문제

---

핵심 키워드 : 문자열, 딕셔너리

 

문제 내용

• 주차장의 요금표와 차량의 IN(입차), OUT(출차) 기록이 주어졌을 때, 차량별로 주차 요금 계산
• 요금표 : 기본시간(분), 기본요금(원), 단위시간(분), 단위요금(원)

 

풀이

총 3개의 딕셔너리를 만든다.

1. car_inout_time_dict[차번호] = (입차시간, 출차시간)
2. car_cost_dict[차번호] = 요금
3. car_park_time_dict[차번호] = 주차누적시간

 

자동차 IN,OUT 기록을 보고 car_inout_time_dict[차번호] 업데이트

→ OUT(출차)시 car_park_time_dict[차번호] 업데이트

 

자동차 OUT 기록이 없는 대상 확인해서 23:59으로 넣어주기

→ car_inout_time_dict[차번호]의 IN시간보다 OUT 시간이 더 빠른경우

 

주차비용 마지막에 일괄 계산

 

(잡담)

차량 IN/OUT 시간을 처음부터 모두 minute(정수)로 변환해서 기록했으면 훨씬 빨리 풀었을것 같다.
그리고 주차요금 계산할 때 문제 예시를 조금만 더 자세히 읽어봤으면 괜히 헛짓거리 안 했을 것이란 생각이 든다.

 

4번 문제

---

핵심 키워드 : 브루트포스, BFS, 그리디

 

문제 내용

• 10점~0점까지 과녁에 어피치가 화살 n발 쏘고난 이후의 상황이다. 이제 라이언이 n발 쏜다.
• 어피치가 k점에 2발 맞혔다면 라이언은 k점에 3발이상은 맞혀야 점수 얻는다.
• (예시)
  [0,0,0,0,0,0,0,0,0,0] 이라는 배열이 순서대로 10점,9점...0점 과녁을 맞힌 화살 수라 하였을때
  어피치가 [1,1,1,0,0,0,0,0,0,0] 이라면
  라이언은 [3,0,0,0,0,0,0,0,0,0,] or [2,1,0,0,0,0,0,0,0,0] or [1,1,1,0,0,0,0,0,0,0] ... [0,0,0,0,0,0,0,0,0,3] 의 조합 가능.
  
  

풀이

BFS로 라이언이 화살을 쏠 수 있는 모든 조합을 구한다.

어피치가 맞힌 화살수에 +1한 리스트를 set로 만들어서 [2,2,2,1,1,1,1,1,1,1] → {2,1} 이렇게 변환.

그리고 queue에 (tuple(점수합,list(맞힌횟수))) 이렇게 넣어서 BFS 돌렸다.

즉, {1,2}로 만들 수 있는 조합의 합이 n인 것들을 구한 것이다.

결과 → (3, [1,1,1]), (3, [1,2]), (3, [2,1])

 

라이언이 무조건 높은 점수를 취득해야하므로 해당 조합들을 그리디하게 10점 부터 차례로 가져가도록 했다.

1,1,1, 의 경우 10점(1발), 9점(1발), 8점(1발)을 가져감

1,2의 경우 10점(1발), 9점(2발) 가져감

이렇게 해서 라이언과 어피치 점수를 비교하여 점수가 가장 차이가 많이 나는 경우,

또 그러한 경우가 많다면 라이언이 최저점수를 최대한 많이 맞힌 경우를 update했다.

 

라이언의 화살이 남는 경우가 존재한다. 남는 화살은 모두 0점 과녁에 추가해줘야 한다.

 

(잡담)

문제 읽고나서 그리디인가? DP인가? 조합인가? 딱 3가지가 떠올랐다.
그리디/DP는 풀이법이 생각이 안나서 먼저 조합을 시도해보았고, 조합 다해보니 이제 그리디로 할 수 있겠구나 싶었다.
만약 C++로 풀었다면 비트마스킹 같은걸 썼을 것 같기도 하다.

 

문제 자체는 간단 명료한데 풀다보면 처리할 부분이 생각보다 꽤나 많다.
- 라이언과 어피치 점수차이가 동일하면 라이언이 최저점수를 최대한 많이 맞힌 경우를 update
- 라이언 화살이 남는 경우 → 0점 과녁에 추가

- 모든 경우에 어피치와 동점이거나 어피치가 점수가 더 높은경우 → [-1] 리턴

 

 

5번 문제 (실패)

---

핵심 키워드 : 그래프 탐색, DP

 

문제 내용

• 이진트리 모양 초원에 늑대와 양 존재
• 루트에서 출발하여 양을 수집한다. 노드 방문마다 늑대/양이 나를 따라옴
• 현재 수집한 양의 수 <= 현재 수집한 늑대 수 되는 순간 모든 양 죽임당함
• 최대한 많은 양을 남기고 루트로 돌아와야 함.
  
  

(잡담)

부모/자식을 양방향 그래프로 재해석해서
부모→자식 : 양(+1비용), 늑대(-1비용), 자식→부모 : 양/늑대(0비용) 이런 생각도 해봤고,

단순히 BFS를 여러번 돌려볼까도 생각해봤고,
우선순위 큐로 양이 많은순서, 늑대가 적은 순서 꺼내오면서 매순간 노드정보 update도 생각해봤다.

 

어떻게든 현재보다 더 최적의 경우가 나왔을때 다른 노드들에 이 정보를 전파해주면 쉽게 풀릴 것 같았는데 평소에 그래프/트리 문제를 많이 소홀히한 탓인지... 집중력이 떨어진 탓인지 풀릴듯 말듯 하다가 못풀었다.

 

 

후기

---

문제 난이도가 이전 까지의 코테보다 많이 낮아진 느낌이었다.

실력이 아직 많이 부족해서 5시간 동안 4번 문제까지 푸는 것을 목표로 했는데 3시간만에 1~4문제를 풀어버려서 적어도 5번 문제를 꼭 풀어야 2차 갈 수 있겠구나 싶었다. 결국 5번은 TC 4개 Fail를 해결못하고 실패...ㅠㅠ

앞으로 그래프/트리/어려운DP 쪽을 보충해서 코테 정복하는 날까지 열심히 해야겠다.