Jinho Tech

오늘은 프로그래머스에서 진행되는 코테 모의고사 2차 문제를 풀어봤다. 난이도가 조금 쉬운 것 같다.

1차도 풀긴 했는데 시험 종료하면 문제랑 코드를 못 본다는 사실을 몰랐어서 그냥 종료해버렸다ㅜ 

https://career.programmers.co.kr/competitions/2627

1번

설명할 필요도 없을 듯 하다. python의 combinations를 쓰면 조합을 바로 구할 수 있다.

from itertools import combinations

def solution(number):
    return len([s for s in combinations(number, 3) if sum(s) == 0])

2번

처음에 그냥 리스트를 쪼개고 set 함수를 사용해서 풀었는데 시간 초과가 나왔다

EX) len(set(topping[:i]) == len(set(topping[i:])

딕셔너리를 사용해서 해결했다. 역시 빠르다 우리 사전!

from collections import Counter, defaultdict

def solution(topping):
    front, back = defaultdict(int), dict(Counter(topping))
    ans = 0
    
    for t in topping:
        front[t] += 1
        back[t] -= 1
        if back[t] == 0:
            del back[t]
        if len(front) == len(back):
            ans += 1

    return ans

3번

문제의 글만 보면 군인들이 목적지로 향하는 상황이지만

우리가 문제를 풀 때는 목적지가 군인들을 찾아간다고 생각하는 것이 풀기 쉽다.

목적지 기준으로 bfs 알고리즘을 사용해서 다른 모든 위치까지의 거리를 구하면 사실상 끝이다.

from collections import deque

def solution(n, roads, sources, destination):
    graph = [[] for _ in range(n+1)]
    ans = []
    
    for s, e in roads:
        graph[s].append(e)
        graph[e].append(s)

    check = [-1 for _ in range(n+1)]
    check[destination] = 0
    q = deque([destination])
    while q:
        i = q.popleft()
        for node in graph[i]:
            if check[node] == -1:
                check[node] = check[i]+1
                q.append(node)

    for s in sources:
        ans.append(check[s])

    return ans

거리와 탐색 관련된 문제이기 때문에 BFS를 사용해서 풀었다.

BFS 풀이 

마지막에 check_li.count(max(check_li))로 한 번에 제일 먼 노드의 개수를 구할 수 있다.

from collections import deque

def solution(N, edge):
    graph = [[] for _ in range(N+1)]
    q = deque([1])
    check_li = [-1]*(N+1)
    check_li[1] = 0
    
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check_li[n] == -1:
                q.append(n)
                check_li[n] = check_li[node] + 1
    
    return check_li.count(max(check_li))

간단한 DFS, BFS 문제이다. DFS, BFS를 안 사용하고도 풀어봤다.

DFS 풀이

def dfs(n, numbers, target, i):
    if i == len(numbers):
        return 1 if n == target else 0
    return dfs(n + numbers[i], numbers, target, i+1) + dfs(n - numbers[i], numbers, target, i+1)

def solution(numbers, target):
    return dfs(0, numbers, target, 0)

생각해보니 굳이 dfs 함수를 만들 필요도 없었다.

아래와 같은 방식으로 numbers 리스트의 앞에 값을 빼가면서, target이 0이 되는지 확인하는 방법도 있다.

def solution(numbers, target):
    if not numbers:
        return 1 if target == 0 else 0
    return solution(numbers[1:], target + numbers[0]) + solution(numbers[1:], target - numbers[0])

BFS 풀이

from collections import deque

def solution(numbers, target):
    q = deque([(0, 0)])
    ans = 0

    while q:
        n, i = q.popleft()
        if i == len(numbers):
            if n == target:
                ans += 1
        else:
            q.append([n + numbers[i], i+1])                
            q.append([n - numbers[i], i+1])                
        
    return ans

풀이 DFS, BFS 사용 X

def solution(numbers, target):
    res_li = [0]
    for n in numbers:
        li = []
        for res in res_li:
            li.append(res + n)
            li.append(res - n)
        res_li = li
    
    return res_li.count(target)

맨 앞 스킬부터 순서대로 나오는지 확인해야 되기 때문에, 큐를 사용해서 풀었다.

첫 번째 풀이는 파이썬의 for-else문을 몰라서 check 변수를 사용한 것이다.

두 번째 풀이는 for-else문을 사용했다.

풀이 for-else X

1. 스킬 순서를 담는 큐를 만들어준다.

2. 스킬 순서에 포함되는 스킬이 나왔는데 선행 스킬이 아니면 불가능한 스킬트리이므로 check = 0을 해준다.

3. 반대로 선행 스킬이 맞다면 스킬 순서 큐를 popleft 해준다.

4. ans += check(1: 올바른 스킬트리, 0: 불가능한 스킬트리) 

def solution(skill, skill_trees):
    ans = 0
    for skill_tree in skill_trees:
        q = list(skill)
        check = 1
        for s in skill_tree:
            if s in q and s != q.pop(0):
                check = 0
                break
        ans += check
        
    return ans

풀이 for-else O

for 문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행됐을 경우 else문이 실행된다.

check 변수가 필요 없어지기에 코드 한 줄이 줄었다.

from collections import deque

def solution(skill, skill_trees):
    ans = 0
    for skill_tree in skill_trees:
        q = deque(skill)
        for s in skill_tree:
            if s in q and s != q.popleft():
                break
        else:
            ans += 1
        
    return ans

간단한 큐 문제이다. 큐를 안 쓴 풀이도 있다.

이 문제 같이 앞에 값부터 없애가면서 체크해야 되는 문제는 큐를 사용해보도록 하자. 

풀이 Q 사용 O

1. 각 progress 별 필요한 요일을 큐에 저장해준다 -> [ceil((100-progresses[i])/speeds[i]) for i in range(len(speeds))]

2. popleft 한 값이 최대값일 경우 ans에  append 1, 아닐 경우 ans 마지막 요소에 1 더함

from math import ceil
from collections import deque

def solution(progresses, speeds):
    ans = []
    q = deque([ceil((100-progresses[i])/speeds[i]) for i in range(len(speeds))])
    max_t = 0
    while q:
        t = q.popleft()
        if t > max_t:
            max_t = t
            ans.append(1)
        else:
            ans[-1] += 1

    return ans

풀이 Q 사용 X

from math import ceil

def solution(progresses, speeds):
    ans = []
    li = [ceil((100-progresses[i])/speeds[i]) for i in range(len(speeds))]
    for i in range(len(li)):        
        if ans == [] or max(li[:i]) < li[i]:
            ans.append(1)
        else:
            ans[-1] += 1

    return ans

단순한 구현 문제이다. dart 딕셔너리를 써서 조건문을 많이 줄일 수 있었다.

풀이

def solution(dartResult):
    dart = {'S': 1, 'D': 2, 'T': 3}
    n = ''
    score = []

    for c in dartResult:
        if c.isnumeric():
            n += c
        elif c in dart:
            score.append(int(n) ** dart[c])
            n = ''
        elif c == '*':
            score[-2:] = [s*2 for s in score[-2:]]
        elif c == '#':
            score[-1] = -score[-1]       

    return sum(score)

비트연산자를 쓸 수 있느냐를 물어보는 문제이다. 처음에는 그냥 bin을 써서 풀었는데,

확실히 비트연산자 쓰는 게 훨씬 편한 것 같다. 

풀이 1

def binary(num, n):
    b = bin(num)[2:]
    return (n - len(b))*'0' + b

def str_sum(n, s1, s2):
    s = ''
    for i in range(n):
        s += '#' if s1[i] == '1' or s2[i] == '1' else ' '
    return s

def solution(n, arr1, arr2):
    ans = [0]*n
    for i in range(n):
        ans[i] = str_sum(n, binary(arr1[i], n), binary(arr2[i], n))
    return ans

풀이 2 

비트연산자와 replace를 사용하니 훨씬 쉽게 풀린다

def solution(n, arr1, arr2):
    ans = []
    for i in range(n):
        b = bin(arr1[i] | arr2[i])[2:]
        ans.append((n - len(b))*' ' + b.replace('1', '#').replace('0', ' '))
        
    return ans

그냥 조건문(노가다), DFS, BFS 등의 방식으로 풀 수 있는 문제이다.

나는 BFS 알고리즘을 사용해서 풀었다.

place에 map함수를 쓴 이유는 place가 문자열로 이루어진 리스트이기 때문이다.

예를 들어 place[0]이 문자열이라 place[0][0] = 'X'이 안된다. 그래서 쓰기 쉽게 map함수를 써서 리스트로 바꿔줬다.

풀이

1. place 탐색 -> place의 현재 위치가 'P'라면 'X'로 바꾸고 BFS 탐색 시작

2. BFS 탐색)

   상하좌우로 탐색하는데 맨 처음 탐색 시작 위치(i, j)와 다음 위치(Y, X)의 맨헤튼 거리가 2 이하일 경우에만 진행한다.

   다음 위치가 'O' 라면 현재 위치를 'X'로 바꾸고 계속 탐색 진행

   다음 위치가 'P'라면 거리 두기 위반이므로 바로 0 리턴

3. 한 명이라도 위반하면 0을 리턴해야 되므로 BFS 탐색이 끝날 때마다 check &= bfs(i, j) 같은 방식으로 check를 업데이트

4. 작은 반복문 끝날 때마다 ans에 check를 추가  

import sys
sys.setrecursionlimit(10000)

def solution(places):    
    def bfs(i, j):
        q = [(i, j)]
        while q:
            y, x = q.pop(0)
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                Y, X = y+dy, x+dx
                if 0 <= Y < 5 and 0 <= X < 5 and abs(Y-i) + abs(X-j) <= 2:
                    if place[Y][X] == 'O':
                        place[Y][X] = 'X'
                        q.append((Y, X))
                    elif place[Y][X] == 'P':
                        return 0
        return 1
    
    ans = []
    for place in places:
        place = list(map(list, place))
        check = 1
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    place[i][j] = 'X'
                    check &= bfs(i, j)
        ans.append(check)                       
                    
    return ans

문제에 맞는 자료구조를 생성하고 활용해야 하는 문제이다.

이 문제의 경우에는 Counter를 사용해서 쉽게 풀 수 있다.

주의해야 할 점이 스테이지에 도달한 사람이 없을 때인데 이를 따로 처리해주지 않으면 런타임 에러가 난다.

이거 때문에 조금 푸는데 시간이 걸렸다. 

풀이

1. 각 스테이지별 도달한 유저의 수를 담은 딕셔너리를 생성(Counter)

2. 각 스테이지별 실패율 계산

3. 실패율을 기준으로 내림차순 정렬한 리스트의 인덱스를 반환

from collections import Counter

def solution(N, stages):
    ans = []
    n = len(stages)
    counter = Counter(stages)
    for i in range(1, N+1):
        if n:
            ans.append(counter[i] / n)
            n -= counter[i]
        else:
            ans.append(0)
                
    return [i+1 for i in sorted(range(N), key=lambda x : ans[x], reverse=True)]

문제 상황에 맞는 적절한 자료구조를 생성하고 활용해야 되는 문제다. 

Collections의 Counter를 사용하면 상당히 쉽게 풀 수 있다. 처음에 안 쓰고 풀어서 그런지 쉽지 않았다. 

조합을 직접 구하기는 번거롭기에 itertools의 combinations 함수를 사용했다.

풀이 1 (Counter 사용 X)

*cource의 개수 만큼 반복([2, 3]의 경우 -> 2개짜리 조합, 3개짜리 조합 찾기)

1. 모든 order에서 가능한 n(cource 값)개 짜리 조합을 comb_li에 저장

2. comb_li에서 {주문된 개수: [메뉴1, ...], ... }의 형태의 딕셔너리 d를 생성

3. d에서 주문된 개수가 제일 많은 메뉴들을 ans에 추가

from collections import defaultdict
from itertools import combinations

def solution(orders, course):   
    ans = []
    for n in course:
        d = defaultdict(list)
        comb_li = []
        max_cnt = 0        
        for order in orders:
            if len(order) >= n:
                comb_li.extend(list(combinations(sorted(order), n)))
        
        for comb in set(comb_li):            
            cnt = comb_li.count(comb)
            d[cnt].append(''.join(comb))
            if cnt > max_cnt:
                max_cnt = cnt                
        
        if max_cnt > 1:
            ans.extend(d[max_cnt])

    return sorted(ans)

풀이 2 (Counter 사용 O)

Counter를 사용했기에 d 딕셔러니가 필요가 없다. d 딕셔너리를 생성하는데 필요했던 자잘한 코드들을 지우니 훨씬

코드가 간결해졌다.

from collections import Counter
from itertools import combinations

def solution(orders, course):   
    ans = []
    for n in course:
        comb_li = []
        for order in orders:
            comb_li.extend(list(combinations(sorted(order), n)))

        counter = Counter(comb_li)
        if counter and max(counter.values()) > 1:
            ans.extend([''.join(k) for k in counter if counter[k] == max(counter.values())])

    return sorted(ans)

문제 상황에 맞는 적절한 자료구조를 생성하고 활용해야 되는 문제다.

요즘 카카오 초반 문제 특징인 것 같은데, 이 문제의 경우에는 2개의 Dictionary를 사용했다.

python의 defaultdict를 거의 처음 사용해봤는데 꽤 좋은 것 같다.

dict의 메서드인 setdefault도 사용해봤지만 defaultdict 쪽이 조금 더 편한 것 같다.

풀이

1. 유저별 신고한 id를 저장하는 report_user_dict, 유저별 신고당한 횟수를 저장하는 report_cnt_dict를 생성한다.

2. 위의 두 사전을 사용해 유저가 신고한 id가 k번 이상인지 확인하고 카운트해준다. 

from collections import defaultdict

def solution(id_list, report, k):
    report_user_dict = defaultdict(set)
    report_cnt_dict = defaultdict(int)
    ans = []
    
    for arg in set(report):
        id, reported_id = arg.split()
        report_user_dict[id].add(reported_id)
        report_cnt_dict[reported_id] += 1
        
    for id in id_list:
        cnt = 0
        for reported_id in report_user_dict[id]:
            if report_cnt_dict[reported_id] >= k:
                cnt += 1 
        ans.append(cnt)
    
    return ans

간단한 구현 문제이다. 문제에서 정해준 순서대로 입력 문자열을 처리해주면 된다.

첫 번째 풀이  

리스트 사용

def solution(new_id):
    # 1
    new_id = new_id.lower()
    
    # 2
    li = [c for c in new_id if c.isalnum() or c in "-_."]
    
    # 3
    i = 0
    while i < len(li)-1:
        if li[i] == li[i+1] == '.':
            li.pop(i)
        else:
            i += 1
    
    # 4
    if li and li[0] == '.':
        li.pop(0)
    if li and li[-1] == '.':
        li.pop()
    
    # 5
    if li == []:
        li.append('a')
    
    # 6
    if len(li) >= 16:
        li = li[:15]
        if li[-1] == '.':
            li.pop()
    
    # 7
    if len(li) <= 2:
        while len(li) < 3:
            li.append(li[-1])
    answer = ''.join(li)
    
    return answer

두 번째 풀이

리스트를 생성할 필요가 있을까 싶어서 문자열로도 풀어봤다.

def solution(new_id):
    ans = ""

    # 1
    new_id = new_id.lower()
    
    # 2
    for c in new_id: 
        if c.isalnum() or c in "-_.":
            ans += c
    
    # 3
    while ".." in ans:
        ans = ans.replace("..", '.')
    
    # 4
    if ans and ans[0] == '.':
        ans = ans[1:]
    if ans and ans[-1] == '.':
        ans = ans[:-1]
    
    # 5
    if ans == '':
        ans = 'a'
    
    # 6
    if len(ans) >= 16:
        ans = ans[:15]
        if ans[-1] == '.':
            ans = ans[:-1]
    
    # 7
    while len(ans) < 3:
        ans += ans[-1]
        
    return ans

문제 상황에 맞는 적절한 자료구조를 생성하고 활용해야 되는 문제다.

카카오 코딩테스트 초반 문제들 특징인 것 같다. 

나름 잘 풀었다고 생각했으나 훨씬 좋은 풀이가 있었기에 두 번째 풀이를 추가했다.

풀이 1

record를 따라 유저의 id와 이름을 기록한 딕셔너리인 user_dic, 유저 id와 출력돼야 하는 메시지들이 담긴

리스트인 msg_li를 만들어줬다. 아래와 같은 느낌이다.

msg_li에서 메시지 부분을 유저 id에 매칭 되는 이름으로 수정한 결과를 담은 리스트를 반환해주면 끝이다.

-> [msg.replace(user_id, user_dic[user_id]) for user_id, msg in msg_li]

def solution(records):
    user_dic = {}
    msg_li = []

    for record in records:
        li = record.split()
        if li[0] == "Enter":
            command, user_id, user_name = li
            user_dic[user_id] = user_name
            msg_li.append([user_id, f"{user_id}님이 들어왔습니다."])
        elif li[0] == "Leave":
            command, user_id = li
            msg_li.append([user_id, f"{user_id}님이 나갔습니다."])
        else:
            command, user_id, user_name = li
            user_dic[user_id] = user_name
    
    ans = [msg.replace(user_id, user_dic[user_id]) for user_id, msg in msg_li]
    
    return ans

풀이 2

지금 첫 번째 반복문을 보면 Enter와 Change의 경우일 때 중복인 코드가 있는데,

이유는 내가 굳이 필요 없는 자료구조인 msg_li를 생성하고 msg_li를 통해 ans를 완성하려고 했기 때문이다.

msg_li를 생성하지 않고, 그냥 user_dic을 첫 반복문에서 완성하고 두 번째 반복문에서 바로 ans를 완성하면 된다.

위의 방식으로 짠 결과 코드가 훨씬 간단해졌다. printer는 두 번째 반복문에 조건문을 넣기 싫어서 만들었다.

def solution(records):
    user_dic = {}
    printer = {"Enter": "님이 들어왔습니다.", "Leave": "님이 나갔습니다."}
    ans = []
    
    for record in records:
        li = record.split()
        if li[0] in ["Enter", "Change"]:
            user_dic[li[1]] = li[2]

    for record in records:
        li = record.split()
        if li[0] != "Change":
            ans.append(user_dic[li[1]] + printer[li[0]])
            
    return ans

단순한 구현 문제이다. 

풀이

1. 0의 개수, 일치하는 숫자의 개수를 센다.

2. 0의 개수 + 일치하는 숫자 -> 순위가 제일 높은 경우, 일치하는 숫자 -> 순위가 제일 낮은 경우

이므로 이에 맞게 순위를 반환해준다.

def solution(lottos, win_nums):
    zero_cnt = lottos.count(0)
    matching_num_cnt = sum([n in win_nums for n in lottos])
    rank = [6, 6, 5, 4, 3, 2, 1]
    
    return rank[zero_cnt+matching_num_cnt], rank[matching_num_cnt]

스택을 사용하면 쉽게 풀 수 있는 간단한 구현 문제이다.

뭔가를 차곡차곡 쌓고 마지막에 쌓은 것부터 처리해야 되는 식의 문제 -> 스택을 생각하자

풀이

1. 인형을 뽑을 때마다 인형을 스택에 추가

2. 스택의 길이가 2 이상일 때 맨 뒤에 있는 인형 2개가 같으면 제거해야 하므로 stack pop 2번 후 ans += 2를 해준다. 

def solution(board, moves):
    ans = 0
    stack = []
    for m in moves:
        for i in range(len(board)):       
            if board[i][m-1]:
                stack.append(board[i][m-1])
                board[i][m-1] = 0

                if len(stack) > 1:
                    if stack[-1] == stack[-2]:
                        stack.pop(); stack.pop()
                        ans += 2
                break
                
    return ans