Jinho Tech

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

첫 번째 풀이는 파이썬의 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

그냥 조건문(노가다), 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

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

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)