꾸준히 개발하기

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

풀이

조건에 맞춰서 차근차근 구현만 하면 되는 문제였다.

파이썬 내 올림 기능을 지원하는 메소드가 math.ceil 인데 실수로 반올림하는 round() 메서드를 썼다... 주의하자!

먼저 수도코드로 쭉 작성한 뒤 구현했고, 바로 통과됬다.

1. records 내 값을 공백 기준으로 split해서 time, car_num, inout에 넣기

2. 딕셔너리에 car_num을 키로 time 넣어주기. 각 딕셔너리 value값은 배열. (in, out 순서로 들어간다)

 * 만약 배열 길이가 홀수면 출차 내역이 입력되지 않은 요소이므로 23:59를 직접 넣어준다

3. records 배열 순회가 끝나면 딕셔너리를 살펴보면서 시간을 계산한다.

 - [짝수] : IN / [홀수] : OUT 이므로 홀수 - 짝수 해주면 된다.

   인자를 받아올 때 ":"를 기준으로 hour, min을 쪼개주었다.

   시간은 상관없는데 분은 음수값이 나왔을 때 예외처리를 해주자. (hour -= 1, min += 60)

4. 총 누적시간이 기본 시간을 넘는다면 문제 조건대로 계산하고, 넘지 않는다면 기본 요금을 저장한다.

 * 여기에서 문제 조건 상 차량번호가 작은 요소부터 출력해달라고 했으므로 [차량번호, 요금] 을 저장하는 배열을 만들어준 뒤 차량번호를 기준으로 정렬한 뒤 요금값을 차례대로 answer에 넣어주자.

python 코드

import math
def solution(fees, records):
    carnum_fee = [] # (차량번호, 요금) 순 저장
    car_dict = {}
    
    for r in records:
        time, car_num, inout = r.split(" ")
        if car_num in car_dict:
            car_dict[car_num].append(time)
        else:
            car_dict[car_num] = [time]
    
    
    for k in car_dict.keys():
        # 출차 기록이 없는 경우
        if len(car_dict[k]) % 2 != 0:
            car_dict[k].append("23:59")
        
        # 시간 계산
        total_time = 0
        for i in range(0, len(car_dict[k]), 2):
            # OUT : i+1, IN : i
            out_h, out_m = map(int,car_dict[k][i+1].split(":"))
            in_h, in_m = map(int, car_dict[k][i].split(":"))
            
            hour = out_h - in_h
            minute = out_m - in_m
            
            if minute < 0:
                hour -= 1
                minute += 60
            
            total_time += hour * 60 + minute

        # 요금 계산
        if total_time > fees[0]:
            carnum_fee.append([k, fees[1] + math.ceil((total_time-fees[0]) / fees[2]) * fees[3]])
        else:
            carnum_fee.append([k, fees[1]])
    
    carnum_fee.sort(key = lambda x : x[0])
    
    answer = [v[1] for v in carnum_fee]
    return answer

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

풀이

두 큐의 합을 같게 만들어주려면, 합이 더 큰 큐에서 pop해가면서 중간값을 맞춰봐야 최소횟수.

이 과정에서 완전히 빈 큐가 생겨버리면 두 큐의 합을 같게 만들 수 없는 것이므로 -1을 리턴해주면 된다.

로직 자체는 맞게 접근한 것 같은데 테스트케이스 몇개가 계속 시간초과가 나서 파이썬 메서드의 시간복잡도를 봤더니 답이 나왔다.

배열의 가장 앞의 요소를 pop해주기 위해 배열 자료형의 pop(0) 메서드를 사용했는데, pop() 연산 자체는 복잡도가 O(1)인데 pop(0)은 O(n)이다. 그 이유는 맨 앞에 있는 값을 출력해주기 위해 전체 복사를 하기 때문이다..! 따라서 리스트 말고 deque를 사용하여 pop(0) 대신 popleft()를 사용하는 것이 시간복잡도 상 매우 유리하다.

자료형을 list -> deque로 바꾸고 테스트케이스 22~24번이 해결됬으며,

최대 가능한 횟수를 모든 요소끼리 서로 다 바꿔도 안될 때 (리스트의 최대길이만큼 교환했을 때) 300,000번으로 제한해두니 테스트케이스 11, 28번이 해결되었다.

sum() 메서드와 len() 메서드 역시 매번 연산해줄 필요는 없어서 산술연산만 할 수 있게 코드를 약간 길게 적었다.

python 코드

from collections import deque
def solution(queue1, queue2):
    answer = 0
    
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    len1 = len(queue1)
    len2 = len(queue2)
    
    goal = (sum1 + sum2) / 2
    
    while len1 != 0 and len2 != 0:
        if sum1 == goal and sum2 == goal:
            return answer
        
        if answer > 300000:
            break
            
        if sum1 > sum2:
            value = deque1.popleft()
            deque2.append(value)
            sum1 -= value
            sum2 += value
            len1 -= 1
            len2 += 1
        elif sum1 < sum2:
            value = deque2.popleft()
            deque1.append(value)
            sum1 += value
            sum2 -= value
            len1 += 1
            len2 -= 1
        else:
            if sum1 == goal and sum2 == goal:
                return answer
            
        answer += 1
    
    answer = -1
            
    return answer

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

풀이

문제에서 시키는 대로 차근차근 구현하면 되는 문제다.

input 이해

survey[i][0] : i+1번 질문 비동의 선택 시 성격유형

survey[i][1] : i+1번 질문 동의 선택 시 성격유형

choices[i] : 4로 나눈 몫이 1 이상 : 동의 -> survey[i]의 [1] 유형에 4로 나눈 나머지 점수 부여 ('모르겠음' 선택지는 0점인데 나머지도 0점이라 케이스를 쪼개지 않아도 괜찮음)

choices[i] : 4로 나눈 몫이 1 미만 : 비동의 -> survey[i]의 [0] 유형에 (4 - choices[i]) 점수 부여 

지표 체크

각각의 성격유형을 key-value 형태로 저장하는 것이 검색에 수월하여 dictionary 형태를 사용하였다. 다른 사람의 풀이를 보니 많이들 비슷하게 접근했더라.

python 코드

def solution(survey, choices):
    answer = ''
    
    score = {'R': 0, 'T': 0, 'C' : 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    
    # 점수 부여
    for i in range(len(choices)):
        # 동의
        if choices[i] // 4 >= 1:
            score[survey[i][1]] += choices[i] % 4
        # 비동의
        else:
            score[survey[i][0]] += (4 - choices[i])
    
    # 지표별 유형 판단
    if score['R'] >= score['T']:
        answer += 'R'
    else:
        answer += 'T'
    
    if score['C'] >= score['F']:
        answer += 'C'
    else:
        answer += 'F'
        
    if score['J'] >= score['M']:
        answer += 'J'
    else:
        answer += 'M'
        
    if score['A'] >= score['N']:
        answer += 'A'
    else:
        answer += 'N'
        
    
    return answer

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

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