[2/2] Kakao Internship 기출문제 풀이

👉 사용 언어 : PYTHON3

[1차] 뉴스 클러스터링

✅ Solution

import re

def solution(str1, str2):
    answer = 0
    multiSet1, multiSet2 = [], []
    regex = re.compile(r'[^a-zA-Z]+')
    for i in range(len(str1)-1):
        if not regex.search(str1[i:i+2]):
            multiSet1.append(str1[i:i+2].lower())
    for j in range(len(str2)-1):
        if not regex.search(str2[j:j+2]):
            multiSet2.append(str2[j:j+2].lower())
    if len(multiSet1 + multiSet2) == 0:
        return 65536
    else:
        for m in multiSet1:
            for n in multiSet2:
                if m == n:
                    multiSet2.remove(n)
                    answer += 1
                    break
        return int(answer / (len(multiSet1) + len(multiSet2)) * 65536)

 

👉 아이디어

• 빈 다중집합 배열 2개를 생성한다.
• re.compile을 사용하여 정규 표현식 (위 예에서는 (r'[^a-zA-Z]+')을 컴파일한다.
  • 리턴값을 객체 regex(컴파일된 패턴 객체)에 할당한다.
  • ^ : 문자열의 시작
  • a-zA-Z : 알파벳 소문자(a부터 z)와 대문자(A부터 Z)
  • [] : 대괄호 안에 있는 문자 중 하나와 매치되는 것
  • ^a-zA-Z : 대괄호 안에서 맨 앞에 ^를 사용하면 해당 문자 집합이 아닌 것과 매치된다. 즉, 알파벳이 아닌 문자와 매치된다.
  • [^a-zA-Z] : 알파벳이 아닌 문자와 매치된다.
  • + : 앞에 있는 패턴이 하나 이상 반복되는 것과 매치된다. 따라서 여러 알파벳이 아닌 문자가 하나 이상 반복되는 것과 매치된다.
  • r'[^a-zA-Z]+' : 알파벳이 아닌 문자가 하나 이상 반복되는 부분과 매치되는 정규표현식
• 각 문자열 집합에서 반복문을 돌리고 문자열 슬라이싱 을 사용하여 2개씩 잘라서 다중집합에 넣는다.
• 둘 다 공집합일 경우, 1 * 65536을 리턴한다.
• 아닐 경우 중첩 for문을 돌려 겹치는 원소가 있으면 하나의 다중집합에서 그 원소를 지운 후, 카운트 +1한다.
  • 1개의 다중집합에서 지우는 이유 : 마지막에 두 다중집합의 길이를 더해서 합집합의 개수를 구하기 위해
  • 카운트 변수(answer) : 교집합 개수

✅  자카드 유사도 J(A, B)

: 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값 (교집합 크기 / 합집합 크기)

: 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

: 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.

 

✅  자카드 유사도를 사용한 문자열 사이의 유사도를 계산

: 두 글자씩 끊어서 다중집합 만든 후, 두 집합의 합집합과 교집합을 사용하여 유사도를 계산한다.

: 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.

: 대문자와 소문자의 차이는 무시한다. (= 같은 취급한다.)

 

✅ 집합 연산

• 합집합: set.union()
• 교집합: set.intersection()
• 차집합: set.difference()
• 대칭차집합: symmetric_difference

👉 집합은 중복을 허용하지 않으므로 집합 연산이 아니라 반복문을 통해 직접 구현한다.

 

✅ 다른 사람 풀이 참고

import re
import math

def solution(str1, str2):
    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0 :
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)

 

👉 깨달은 것 / 알게된 것

• 다중집합 배열을 따로 정의하지 않고 전달받은 str1, str2배열에 재할당 할 수 있다.
• match()말고 findall() 를 사용하여 찾을 수도 있다.
• for문과 if문을 한 줄 에 작성함으로써 코드가 좀 더 깔끔하게 작성할 수 있다.
• 교집합과 합집합을 집합 연산 을 사용하여 구현하는 대신 2개의 다중집합 배열에서 해당 문자를 count하고 카운트 값의 min/max를 구하여 개수를 계산할 수 있다.

문제 힌트를 올바르게 사용하였따!

피로도

✅ Solution

from itertools import permutations

def solution(k, dungeons):
    answer = []
    index = [i for i in range(len(dungeons))]
    for i in list(permutations(index, len(dungeons))):
        current = k
        cnt = 0
        for j in i: 
            if dungeons[j][0] <= current:
                current -= dungeons[j][1]
                cnt += 1
        answer.append(cnt)
    return max(answer)

 

👉 아이디어

• dungeons 원소 : ["최소 필요 피로도", "소모 피로도"]
• dungeons 이중 배열에서 permutaions 메서드를 사용하여 순서를 고려하여 원소(= 내부 배열)를 재배열 하여 리스트를 만들고 반복문을 돌려 하나씩 뽑는다.
  • 최소 필요 피로도를 현재 남아있는 피로도와 비교하여 그보다 같거나 많은 경우에만 현재 남은 피로도를 업데이트하고 던전 수를 카운트한다.
• 모든 케이스(= 재배열한 이중 배열)에서 카운트(= 모험한 던전 수)가 최대 인 것을 반환한다.

 

✅ 다른 사람 풀이 참고

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

👉 깨달은 것 / 알게된 것

• 함수 밖에서 선언한 변수를 함수 내에서 사용하려면 global을 변수명 앞에 붙인다.
  • 함수 안에서 전역 변수를 선언하려면 global 변수명
  • 함수 밖에서 전역 변수를 선언하려면 (global) 변수명, 꼭 사용할 함수 내에서도 사용을 명시하기 위해 해당 변수명 앞에 global을 붙여준다.
• 순열을 사용하지 않고 DFS 알고리즘과 재귀 호출을 사용하여 풀이할 수 있다.
  • dfs 내에서 cnt 와 answer 를 비교 하여 업데이트 하는 코드를 통해 탐험할 수 있는 최대 던전 수를 구할 수 있다.
  • for문 내에서 현재 피로도 와 필요한 피로도 를 비교 하고 방문 여부 를 체크한 후, 방문 여부를 업데이트하고 dfs 메서드를 재귀 호출 한다.
  • DFS와 BFS 참고 : https://codingopera.tistory.com/67