꾸준히 개발하기

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])

소수의 판별: 기본적인 알고리즘 성능 분석

• 2부터 𝑋-1까지의 모든 자연수에 대하여 연산을 수행해야 한다
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X) 

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
  • 예를 들어 16의 약수는 1, 2, 4, 8, 16이다
  • 이때 2 X 8 = 16은 8 X 2 = 16과 대칭이다
• 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다
  • 예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다

import math

# 소수 판별 함수
def is_prime_number(x):
	# 1은 소수가 아니므로 예외처리
	if x == 1:
    	return False
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

에라토스테네스의 체

위의 방법은 특정 범위 내의 모든 소수를 구할 때는 비효율적이다. (실제로 백준 4948번을 위의 방식대로 풀면 시간초과가 난다)

효율적으로 소수를 구하기 위해 에라토스테네스는 범위에서 합성수를 모두 지우는 방식을 제안했다.

1. 1 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. ... (반복)

따라서 n까지의 수가 소수인지 아닌지 True, False로 저장해준 뒤 싹 돌리면 된다. 

import math

# 에라토스테네스의 체 방식 사용
def cntPrimeNums(start, end):
    # 1~end까지
    erato = [True] * end

    # 1은 소수가 아니므로 체크
    erato[0] = False

    for i in range(2, int(math.sqrt(end)) + 1):
        if erato[i] == True:
            for i in range(i + i, end, i):
                erato[i] = False
    cnt = 0
    for i in range(start, end):
        if erato[i] == True:
            cnt += 1
    return cnt

위 방법은 특정 범위 내에 소수가 몇개 있는지 체크해주는 코드다. 위의 코드는 start 이상 end 미만의 수를 중 소수를 체크한다! 만약 end까지 포함시키고 싶다면 수를 유의해서 넣어주자. 

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

2진수 변환을 해주고 n자리에 맞춰서 앞에 숫자까지 채워준 뒤 단순 값 비교해주면 되는 문제였다!

어렵지 않지만 차근차근 집중해서 구현해야 했다.

매번 진법 변환을 건드리게 되는데 divmod 쓰면 참 코드가 깔끔할텐데 매번 직접 나눠서 한다... ㅎㅎ 

def convert10to2(num, n):
    map_data = ''
    while True:
        map_data += str(num % 2)
        num = num // 2
        if (num // 2) == 0:
            map_data += str(num % 2)
            break
    
    if len(map_data) != n:
        return '0'*(n - len(map_data)) + map_data[::-1]
    else:
        return map_data[::-1]
        

def solution(n, arr1, arr2):
    answer = []
    map1 = []
    for a in arr1:
        map1.append(convert10to2(a, n))
    
    map2 = []
    for b in arr2:
        map2.append(convert10to2(b, n))
    
    
    for i in range(len(map1)):
        # map1[i]는 문자열
        result = ''
        for j in range(len(map1[i])):
            # map1[i][j]는 문자
            if map1[i][j] == "0" and map2[i][j] == "0":
                result += " "
            else:
                result += "#"
        answer.append(result)
    return answer

파이썬 진법 변환 코드는 한번 더 적어봤다.

# 진법(base)를 입력받아 변환해주는 코드~
def convert(num, base):
    result = ""
    while num > 0:
        num, mod = divmod(num, base)
        result += str(mod)

    return result[::-1]

n진수 → 10진수

* 결과값은 모두 string

python에서는 기본적으로 int() 라는 함수를 지원한다

int(string, base)

10진수 → n진수

2, 8, 16진수는 bin(), oct(), hex() 함수를 지원한다.

각 결과는 앞에 진법을 표시해서 문자열을 리턴하므로 생략하고 싶다면 [2:]를 붙여주면 되겠다.

물론 직접 코딩해도 된다.

def convert(n, q):
    result = ''

    while n > 0:
        n, mod = divmod(n, q)
        result += str(mod)
	
    # 나머지가 거꾸로 들어가므로 뒤집어줘야 정답
    return result[::-1]

위의 코드에서 divmod를 안쓰면 다음과 같다.

def convert10to2(num, n):
    data = ''
    while True:
        data += str(num % 2)
        num = num // 2
        if (num // 2) == 0:
            data += str(num % 2)
            break
    
    return data[::-1]

 divmod 쓰는 편이 깔끔하긴 하다 ㅎㅎ

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 함수에 람다로 넘겨주는 방법에 더 익숙해지자