꾸준히 개발하기

https://school.programmers.co.kr/learn/courses/30/lessons/42890

접근

유일성을 만족하기 위해 set 자료형을 사용했다. 키의 최대 길이가 8개로, 가능한 키 조합을 모두 구해 각 경우별로 set 자료형으로 변환해도 길이가 변하지 않는 것을 체크했다.

2차원 배열은 set연산을 적용하기가 골치 아파 중간에 한번 tuple 자료형으로 변환해주었다. 

유일성을 만족하는 모든 경우의 수를 ck_list 배열에 저장한 뒤, ck_list 배열을 돌면서 최소성을 만족하는지 체크했다.

최소성을 만족하는지 체크하기 위해 실제로 최소성을 만족하는 후보키 배열 ck를 만들었다. 모든 후보키에 대해 합집합을 수행해 키가 최소성을 만족하는 경우를 체크했다. (단순히 합집합 한번만 했더니 [(0), (1,2)]과 [1,2,3] 경우를 계산하는 과정에서 0, (1,2,3) 이 조건을 만족하는 것으로 되서 cnt 변수를 통해 모든 후보키에 대해서 고려하도록 수정했다.)

한시간정도 걸린 문제였다. 은근 어려워..! 

코드

from itertools import combinations

def solution(relation):
    answer = 0
    
    column_list = [i for i in range(len(relation[0]))]

    # 모든 후보키가 될 수 있는 경우의 수(컬럼 인덱스 배열)
    cases = []
    for i in range(1, len(column_list)+1):
        cases.append(list(combinations(column_list, i)))
        
    ck_list = [] 
    for case_list in cases:
        for case in case_list:
            all_senario = []
            for row in range(len(relation)):
                arr = [relation[row][c] for c in case]
                all_senario.append(tuple(arr))
            # print(all_senario)
            
            if len(all_senario) == len(list(set(all_senario))):
                ck_list.append(case)
        
    # print(ck_list)
    
    ck = []
    for key in ck_list:
        if len(ck) == 0:
            ck.append(key)
            continue
        cnt = 0
        for k in ck:
            if set(key) != set(k) | set(key):
                cnt += 1
        
        if cnt == len(ck):
            ck.append(key)
            
    answer = len(ck)        
    return answer

효율성은 없네 경우의 수를 모두 고려해야되서 그런가?

https://school.programmers.co.kr/learn/courses/30/lessons/42584

풀이

자기 뒤에서 자기보다 작은 가격이 등장한 최초의 순간만 찾으면 되는 간단한 문제라고 생각했는데......... .... 계속 시간초과가 나서 2시간정도 삽질하다가 해설을 봤다. deque 자료구조를 쓰거나 stack을 사용하면 되는 문제라고 한다. 

아래는 효율성 0점의 눈물나는 코드다.

# 단순 리스트 순회
def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in prices[i + 1 :]:
            if j < prices[i]:
                cnt += 1
                break
            else:
                cnt += 1
        answer.append(cnt)
    return answer

와 충격적... 알고리즘 오카방에 물어봤더니 알려줬다

for j in prices[i + 1 :]:

위 부분에서 매번 리스트를 새롭게 만들어주는 과정에서 시간초과가 난 것이다... 와 ... 그러고 보니 리스트 슬라이싱은 추출하여 새로운 리스트를 만들어주는 것이었다.... 그래서 이 부분 수정하면 효율성을 통과하기는 한다 대박사건

def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in range(i + 1, len(prices)):
            cnt += 1
            if prices[j] < prices[i]:
                break
        answer.append(cnt)
    return answer

deque 사용

list로 순회하는 방법에서 deque를 쓰는 방식으로 바꿨더니 바로 통과가 됬다. 분명 알고리즘은 똑같은데 이게 자료구조...?

# deque 사용
from collections import deque
def solution_deque(prices):
    queue = deque(prices)
    answer = []
    while queue:
        price = queue.popleft()
        cnt = 0
        for j in queue:
            cnt += 1
            if j < price:
                break
        answer.append(cnt)
    return answer

코드 실행 시간이 절반으로 줄었다... 더 효율적인 코드가 무엇일지 계속 고민하는 개발자가 되자

https://school.programmers.co.kr/learn/courses/30/lessons/42839

풀이

모든 경우의 수를 permutations를 사용하여 순열로 뽑아내었다. list로 나온 요소를 모두 join 메서드를 사용하여 이어붙인 뒤 숫자로 변환하였다. 문제에서 011과 11은 같은 숫자라고 명시했기 때문에 중복을 제거한 뒤 모든 경우를 소수 판별했다. 0과 1은 소수가 아니므로 예외처리를 해주고 그 외의 경우에는 1, 자기자신을 제외한 수로 모두 나눠보며 체크했다.

프로그래머스 내에서는 통과되었는데 분명 시간초과가 날 여지가 있다고 생각하여 소수판별 알고리즘을 한번 더 정리해보려 한다. 블로그에 이미 올려둔 내용이긴 하지만... 또 까먹었기 때문에 한번 더 정리

# 2022-07-22
# 프로그래머스 Lv2 - 소수 찾기
# https://school.programmers.co.kr/learn/courses/30/lessons/42839
# 소요시간 : 15:10 ~ 15:25 (15m)

from itertools import permutations

# 소수판별 알고리즘
def checkPrimeNum(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False
    return True


def solution(numbers):
    answer = 0
    num_arr = []
    for num in numbers:
        num_arr.append(num)

    every_case = []
    for i in range(1, len(num_arr) + 1):
        case = list(permutations(num_arr, i))
        for arr in case:
            every_case.append(int("".join(arr)))

    every_case = list(set(every_case))

    for case in every_case:
        if checkPrimeNum(case):
            answer += 1

    return answer

소수 판별 알고리즘

단일 숫자 판별 시

약수의 성질을 살펴보면 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 

16의 약수는 1, 2, 4, 8, 16 인데 2x8 = 16, 8x2=16이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인해주면 된다. 

# 소수 판별 (개선된 알고리즘)
import math

def isPrimeNumber(num):
    # 2부터 num의 제곱근까지의 모든 수를 확인하기
    # 제곱근을 구하는 방법은 math.sqrt() 사용. 반환형은 float
    # 음수의 제곱근을 구하게 되면 error 발생하니 유의
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

대량의 숫자 판별 시 (에라토스테네스의 체)

이 문제에서는 각각의 경우가 소수인지 판단해야 되서 아니지만, 만약 특정 범위까지의 자연수 중 소수가 몇개인지처럼 대량의 소수를 한꺼번에 판별하고자 할 때 사용하면 좋은 방법을 추가로 정리한다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당, 그 인덱스에 해당하는 값을 넣어준다. 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자를 모두 지운다. (자기 자신은 지우지 않음) 

n = int(input())

eratos = [True] * (n+1)
m = int(n**0.5) // math.sqrt 사용해도 ok

for i in range(2, m+1):
	if eratos[i] == True:
    	for j in range(i+i, n+1, i): #i의 배수를 모두 삭제, 본인은 제외
        	eratos[j] = False
            
print([i for i in range(2, n+1) if a[i] == True])

https://programmers.co.kr/learn/courses/30/lessons/72410

접근

문제에 친절하게 7단계가 차근차근 나와 있어서 그대로 구현하면 되는 문제였다.

2단계 조건

정규식이 익숙하지 않아서 조금 헤맸다. 이번 기회에 사용해봤다.

파이썬에서 문자열을 치환해주는 메서드로 re.sub을 사용할 수 있다.

import re 해준 뒤, re.sub(정규 표현식, 대상 문자열, 치환 문자) 의 형식으로 쓰면 된다.

정규 표현식은 정확히 사용법을 몰라서 구글링했다.

포함시키고 싶으면 그냥 문자열을, 제외하고 싶으면 r을 붙여주면 된다. 범위를 지정하고 싶으면 [ ] 를 사용한다.

3단계 조건 (꽤 시간 잡아먹은 부분)

최대 '.'이 등장 가능한 경우부터 두번 반복되는 경우까지 거꾸로 접근해서 모두 '.'로 바꿔주면 되는 부분이었다. 너무 어렵게 생각해서 오래 걸렸는데, 파이썬 문자열 replace를 사용하면 쉽게 해결되는 문제였다.

find() 쓰면 여러번 등장해도 가장 맨 앞의 인덱스만 반환하고 끝난다!

find써서 했다가 문자열 안에 등장하는 모든 반복되는 온점을 바꿔야되는데 가장 맨 앞의 요소들만 바꾸고 끝났어서 테케 3개가 죽어도 안잡혔었다 ㅠㅠ 문자열 안에 해당되는 모든 경우를 다 변환하려면 꼭 replace 쓰자~!

replace(현재 문자열에서 바꾸고 싶은 문자, 새로 바꿀 문자, 변경할 횟수)

* 변경할 횟수같은 경우 입력하지 않으면 전체를 의미하는 -1로 지정되어 전체를 변경한다.

주의할 점 (strip 함수 사용할 때)

strip() 사용을 이번에 해봤는데 이거 양 끝에 계속 등장하면 계속 날려버린다...! 

혹시 몰라서 "a..".strip('.') 해봤더니 a 나와서 깜짝 놀라서 코드 수정함

근데 또 인덱스로 냅다 접근하면 out of range가 나와서 길이가 0이 아닐떄만 접근하도록 4단계, 5단계 코드에 조건이 추가되었다. 

6단계 조건

아직도 파이썬 인덱스 범위가 헷갈린다니 이건 혼나야된다.

총 15글자만 남기려면 str[0:15] 해줘야지...!

그리고 첫번째 글자만 날리려면 str[1:], 마지막 글자만 날리려면 str[:-1] 해주면 된다. 앞 뒤를 생략해줘도 친절한 파이썬이 잘 동작해준다 ^-^

회고

사실 문제에서 다 제공해줘서 어렵지 않은 단순 구현 문제였다. 코드를 어렵게 짤 필요 없이 최대한 쉽게 쉽게 간결하게 짜자. 테스트케이스가 주어지지 않는 코딩테스트가 꽤 있으니까 최대한 모든 경우를 다 제어할 수 있게!

소스코드 

import re

def solution(new_id):
    answer = ''
    
    # 1단계
    new_id = new_id.lower()
    
    # 2단계
    new_id = re.sub(r"[^a-z0-9-_.]", "", new_id)
    
    # 3단계
    cnt_point = new_id.count('.')
    for i in range(cnt_point, 1, -1):
        new_id = new_id.replace("."* i, ".")
    
    # 4단계
    if len(new_id) != 0:
        if new_id[0] == '.':
            new_id = new_id[1:]
    
    if len(new_id) != 0:
        if new_id[-1] == '.':
            new_id = new_id[:-1]
        
    # 5단계
    if len(new_id) == 0:
        new_id = 'a'
    
    # 6단계
    if len(new_id) >= 16:
        new_id = new_id[0:15]
    if new_id[-1] == '.':
        new_id = new_id[:-1]
    
    # 7단계
    if len(new_id) <= 2:
        while True:
            new_id += new_id[-1]
            if len(new_id) == 3:
                break
                
    answer = new_id
    return answer

https://programmers.co.kr/learn/courses/30/lessons/42576

try1. in 연산자

썼다가 효율성 0점 맞음 (당연함... 시간복잡도 O(n)... )

try2. binary_search

찾아가면서 진행했더니 효율성 테케 2개 fail

try3. 계수 정렬에서 착안해서 collections.Counter 사용해서 값 찾음

처음에는 set 연산 써서 참가자와 완주자의 차집합을 구해서 그 차집합의 길이가 0이 아니면 동명이인이 있다고 생각해서 동명이인 숫자를 most_common() 써서 출력했음. 

근데 생각해보면 동명이인이 여러명 있고, 그 여러명이 다 통과할지 안할지 모르는 부분임..

try4. Counter 사용해서 등장횟수 체크하고, 완주하지 못한 선수는 딱 1명이니까 Counter 객체의 key, value값 비교해서 다른 요소를 찾아냄

만약 키값이 존재하고 value가 다를때와, 키값이 아예 존재하지 않을때 두가지 경우만 존재해서 풀음.

-> 다른 사람 코드 보니까 Counter객체는 빼기 연산이 가능해서 ... 단순히 빼주고 그 요소의 key값만 출력해줘도 됬었다. 그래도 목표 시간 1시간 안에는 품!

from collections import Counter

def solution(participant, completion):
    answer = ""

    c_p = Counter(participant)
    c_c = Counter(completion)

    for key_cp, value_cp in c_p.items():
        # 만약 key가 존재하고 value값이 다르면 answer에 추가
        if key_cp in c_c and value_cp != c_c.get(key_cp):
            answer += key_cp
            break
        # key가 없으면 answer에 추가
        elif not key_cp in c_c:
            answer += key_cp
            break

    return answer

프로그래머스 고득점 kit 정렬 파트에 있는 문제다.

https://programmers.co.kr/learn/courses/30/lessons/42746

내부에서 제공하는 sort() 함수를 써야 시간 복잡도 상 유리한 걸 머리로는 알면서도 어떻게 써야될지 감이 안와서 무식하게 비교했더니 시간 초과가 났다. 당연한 결과지만서도... 

def solution(numbers):
    answer = ''
    
    while len(numbers) > 0:
        max_num = -1
        for i in range(len(numbers)):
            if str(max_num)*3 < str(numbers[i])*3:
                max_num = numbers[i]
        
        numbers.remove(max_num)
        answer += str(max_num)
    
    return str(int(answer))

마지막에 str(int(answer)) 해준 이유는 숫자 배열이 [0,0,0,0] 이라고 주어질 때 '0000'이 아니라 '0'으로 나와야해서 정수형으로 바꿔주고 다시 문자열로 바꿔준 것이다. 테케 11번이 이건듯?

문자열에 *3을 해주는건 "3" 이랑 "30" 이랑 비교했을 때 후자가 더 커서 그 부분을 해결해주기 위해 작성했다.

그나저나 이 코드로는 시간 초과가 잡힐 수가 없어서 파이썬 기본 제공 라이브러리 sort함수 + 람다 함수써서 어떻게 하나 검색해봤더니 기가 막히는 코드가 있더라... 어떻게 이렇게 깔끔하게 쓰는지 ㅠㅠ

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int("".join(numbers)))

위 코드로 하면 깔끔하게 통과한다. join 함수랑 sort 함수에 람다로 넘겨주는 방법에 더 익숙해지자