[day-16] 기본 역량 문제 풀이

코딩테스트 구현 순서

"코딩 인터뷰 완전분석"이라는 책에 나온 내용이다.

1. 듣기
2. 예제
3. 무식하게 풀기
4. 최적화
5. 검토하기
6. 구현하기
7. 테스트

순서로 진행하는게 좋다고 하는데 강사님은 무식하게 푸는 것에 공감을 많이 한다고 했다.

---

짝수, 홀수 찾기

링크
1. 리스트 컴프리헨션으로 뼈대 구성

def solution(data):
    홀수 = [i % 2 != 0 for i in data]
    짝수 = [i % 2 == 0 for i in data]
    print(홀수, 짝수)
    return data

solution([1, 2, 3, 4, 5])

1-1. 조건에 맞게 수정

def solution(data):
    홀수 = [i % 2 != 0 for i in data]
    짝수 = [i % 2 == 0 for i in data]
    # print(홀수, 짝수)
    return [sum(짝수), sum(홀수)]

2-1. 나머지를 활용한 풀이

def solution(num_list):
    answer = [0, 0]
    for i in num_list:
        answer[i % 2] += 1
    return answer

3. 이런 풀이도 있다

# 좋은 풀이는 아님
# sum은 순회를 돈다!
def solution(data):
    짝수 = [i % 2 == 0 for i in data]
    return [sum(짝수), len(data) - sum(짝수)] # sum이 순회합니다.

머쓱이보다 키 큰 사람

링크

# 예시
def solution(array, height):
    pass

solution([149, 180, 192, 170], 167)

데이터의 형태가 리스트인데 여러개의 리스트로 구현되있는 등의 경우에는 언패킹을 해서 사용하는 편이 가독성이 좋다!

def solution(data):
    array, height = data 
    pass

solution([[149, 180, 192, 170], 167])

1. for문 풀이

def solution(array, height):
    count = 0
    for i in array:
        if i > height:
            count += 1
    return count

2. filter 풀이

# filter는 len가 없다
def solution(array, height):
    return list(filter(lambda x: x> height, array))

위의 코드에서 filter는 len() 함수를 쓸 수 없는데 이는 순회(loop) 돌기 전까지 실행이 되지 않는 함수라서 그렇다. 수강생중 한분이 했던 말이 더 와닿을 수도 있을 것 같다.

"주문만 하고 아직 제조되지 않은 커피"

3. map, sum을 활용한 풀이

def solution(array, height):
    return sum(map(lambda x: x > height, array))
    
solution([149, 180, 192, 170], 167)

4. 컴프리헨션

def solution(array, height):
    return sum(i > height for i in array)
    
solution([149, 180, 192, 170], 167)

숨어있는 숫자의 덧셈

문제

# 오답, 그러나 이렇게도 많이 사용한다.
def solution(my_string):
    count = 0
    for i in my_string:
        if i.isdigit():
            count += 1

solution("aAb1B2cC34oOp")

1. 단순한 방법

def solution(my_string):
    result = 0
    for i in my_string:
        if i.isdigit():
            result += int(i)

    return result

solution("aAb1B2cC34oOp")

짤막상식

# isdigit에 () 가 있고 없고의 차이는 무엇인가?
def 함수(x):
    return x.isdigit()

def solution(my_string):
    return list(filter(함수, my_string))

solution("aAb1B2cC34oOp")

괄호가 있으면 함수이고, 아니라면 메서드
2. 효율적이진 않은 코드

# 문법 복습차원
def solution(my_string):
    return sum(map(int,(filter(str.isdigit, my_string))))

solution("aAb1B2cC34oOp")

2-1. 효율적이진 않은 코드

def solution(my_string):
    return sum(map(lambda x: int(x) if x.isdigit() else False, my_string))

solution("aAb1B2cC34oOp")

짤막상식

이 문제는 정규표현식으로도 풀 수 있는데, 이때 들어가는 r이 무엇일까? re.sub(r'무언가', '', 데이터)에서 r이다.

여기서 r은 raw(날것)이라는 뜻으로 이스케이프 문자를 포함해서 전부에서 원하는 문자만 뻡겠다는 것이다.

참고로 정규표현식에서 \로 시작하는 문자는 이스케이프 문자이다. \n, \t 등
3. 정규표현식

import re

def solution(s):
    return sum(map(int, re.findall(r'[0-9]', s)))

solution('aAb1B2cC34oOp')

3-1. 정규표현식

import re

def solution(s):
    return sum(map(int, (re.sub(r'[a-zA-Z]', '', s))))

solution('aAb1B2cC34oOp')

암호해독

문제

1. 슬라이싱

def solution(cipher, code):
    return cipher[code-1::code]

solution("dfjardstddetckdaccccdegk", 4)

2. 반복문(for)

def solution(cipher, code):
    count = 1
    for i in cipher:
        if count == code:
            print(i)
            count = 0
        count += 1

solution("dfjardstddetckdaccccdegk", 4)

3. enumerate, 나머지 연산자

def solution(cipher, code):
    count = 1
    for i, j in enumerate(cipher, 1):
        if i % code == 0:
            print(j)

solution("dfjardstddetckdaccccdegk", 4)

369게임

문제

1.문자열 count

def solution(order):
    order = str(order)
    return order.count('3') + order.count('6') + order.count('9')

2. 정규표현식

import re

def solution(order):
    order = str(order)
    return len(list(re.findall(r'[369]', order)))

중복문자 제거

문제

1. set 자료형으로 제거하기

set("people") # 중복 제거 완료, 그러나 순서를 보장하지 않음!

2. 반복문

def solution(s):
    answer = ''
    for i in s:
        if i not in answer:
            answer += i
    return answer

3. 딕셔너리

def solution(my_string):
    return ''.join(dict.fromkeys(my_string))

solution('people')

3번은 중요하니 짚고 넘어가겠다. dict.fromkeys()로 문자열의 각 원소를 키로 딕셔너리를 만들었다. 그 다음 join으로 합치는데 딕셔너리에서 join을 하면 key값 끼리 합쳐진다!

A로 B만들기

문제

1. counter 모듈

import collections

# collections.Counter("olleh") == collections.Counter("hello")
# collections.Counter("olleh") == collections.Counter("hhhhhhhhhello")
collections.Counter("olleh")

2. 반복문

def solution(before, after):
    a = list(after)
    for i in before:
        if i in a:
            a.remove(i)
        else:
            return 0
    if a:
        return 0
    return 1

solution("olleh", "hello")

반복문에서 if문을 많이 활용하여 예외처리를 하는게 좋다. 리소스도 별로 잡아먹지 않는다고 한다.

3. 비슷한 문제 - 회문

# 'hello' => 'elloh' => 'llohe'
# 'hello' => 'ohell' => 'lohel'
# collections.deque를 사용해서 풀면 쉽게 풀림

# 문제1 'hello'를 앞뒤로 이동시켜 'llohe'를 만들 수 있나?
# 문자열을 2배한다
# 'hellohello'

# 문제2 몇칸 이동했나?
# 문자열을 2배해서 인덱스를 찾기
# 'hellohello'.index('llohe')

저주의 숫자 3

문제

# 예시
# 십진수    3숫자마을
# 1         1
# 2         2
# 3         4
# 4         5
# 5         7
# 6         8
# 7         10
# 8         11
# 9         14
# 10        16

1. 마스킹

# 숫자 크기만큼 False배열을 만들고 
조건에 맞는 부분만 True로 바꿔서 구현

2. filter

def solution(num):
    return list(filter(lambda x: (x % 3 != 0) and
    ('3' not in str(x)), range(1000)))[num-1]

3. 컴프리헨션

solution = lambda n:[i for i in range(10000) if i % 3 != 0 and '3' not in str(i)][n-1]

진료 순서 정하기

문제

# 예시
# emergency     result
# [3, 76, 24]   [3, 1, 2]

def solution(emergency):
    pass


solution([3, 76, 24] )

문제는 이런식으로 접근한다.

data = ['제주', '경기', '전주'] # ['064', '031', '063']
data2 = {
    '제주': '064',
    '경기': '031',
    '전주': '063'
}

[data2[i] for i in data]

1. 인덱싱

# emergency     result
# [3, 76, 24]   [3, 1, 2]

def solution(emergency):
    sorted_emergency = sorted(emergency, reverse=True)
    return [sorted_emergency.index(i) + 1 for i in emergency]

solution([3, 76, 24])

가까운 수

문제

# [3, 10, 28, 30, 12] => [17, 10, 8, 10, 8]
# [3, 10, 28, 30, 12] => [(17, 3), (10, 10), (8, 28), (10, 30), (8, 12)]
# 원하는 숫자: 20
# result: 28

array = [3, 10, 28, 30, 12]
n = 20

28 - 20 == 8
12 - 20 == -8

20 - 28 == -8
20 - 12 == 8

sorted(array, key=lambda x:(abs(x-n), x))[0]
sorted(array, key=lambda x:(abs(x-n), n-x))[0] # 팁, n-x이거나 x-n 2개 중에 하나입니다.

기본적으로 절대값으로 정렬하고, 같으면 value값이 작은 순으로 정렬한다. 순서를 바꾸고 싶으면 sorted의 두번째 조건에 n-x 혹은 x-n을 넣으면 정답이다.

k의 개수

문제

# 문제 접근 방식
# i    j    k
# 1    13    1

i = 1
j = 13
k = 1

str(list(range(i, j+1)))
'[1, 2, 3]'.count(',')

1. for문

i = 1
j = 13
k = 1

count = 0
for temp in range(i, j):
    count += str(temp).count(str(k))

count

짤막상식

파이썬의 swap과 다른 언어의 swap은 다르다

a = 10
b = 20

# swap

temp = a
a = b
b = temp

# python에서 사용하는 swap

a = 10
b = 20
a, b = b, a
a, b

2. 정석 풀이

def solution(i, j, k):
    return str(list(range(i, j+1))).count(str(k))

정해진 범위만큼 range로 반복하고 이를 count해주기 위해 리스트를 문자형으로 바꾸고 count를 적용하였다.

---

직접 출제 문제

1. 선분의 총 길이 합 구하기

# step1
# 각 선분이 있는 곳에 총 길이 합을 구하라
# [[0, 5], [3, 5], [7, 10]]

선 = [False] * 10
선

for i in range(0, 5):
    선[i] = True

for i in range(3, 5):
    선[i] = True
    
for i in range(7, 10):
    선[i] = True    

sum(선)

짤막상식

;로 구분해서 선언 가능하다

a = 10;b = 10
a, b

2. 소수 판별

1. 에라토스테스트의 체

# 에라토스테스트의 체 => 소수판별 => 이것을 알고리즘 문제로 내는 것은 저는 반대
소수 = [True] * 120
소수[0] = 소수[1] = False

for i in range(4, 120, 2):
    print(i)

for i in range(6, 120, 3):
    print(i)

# for i in range(4, 120, 4):  # 2의 배수에 속하기에 할 필요가 없음
#     print(i)

# https://nahwasa.com/entry/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%ED%98%B9%EC%9D%80-%EC%86%8C%EC%88%98%ED%8C%90%EC%A0%95-%EC%8B%9C-%EC%A0%9C%EA%B3%B1%EA%B7%BC-%EA%B9%8C%EC%A7%80%EB%A7%8C-%ED%99%95%EC%9D%B8%ED%95%98%EB%A9%B4-%EB%90%98%EB%8A%94-%EC%9D%B4%EC%9C%A0

수학 공식을 활용하여 제곱근까지 반복돌리며 그 수의 배수를 False로 바꾼다. 그러면 남은 수는 자동으로 소수이다.

for 소수, 판별 in enumerate(소수):
    if 판별:
        print(소수)

---

행렬 연산

행렬의 연산은 numpy를 활용하면 아주 쉽게 풀 수 있다!

s = [[1, 3, 5], [7, 9, 11], [13, 15, 17]]
s = np.array(s)
cols, rows = np.where(s == 7)
cols

import numpy as np

x = np.array([1, 2, 3])
x * 2

지뢰찾기와 같은 알고리즘도 쉽게 풀 수 있다!

# 지뢰찾기
x = [[0, 1, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 0, 1]]

x = np.array(x)
np.where(x == 1)

x = [[0, 1, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 0, 1]]

s = 0
for i in x:
    s += i.count(1)

s

---

피드백

오늘은 이론보다는 실전이라는 느낌으로 코딩테스트 기본 문제들을 풀어보았다. 예전에 풀어봤던 문제들이긴 한데 몇개는 완전히 잘못 풀었다는거를 깨달았다. 좀 부끄러워 진다. 하지만! 이런 것도 마주하고 계속 정진하다 보면 어디가서 관련 지식을 뽐낼 순간이 오지 않을까? 그날을 기다리며 오늘도 공부한다

오늘이 호준 강사님의 마지막 시간이었는데 장고할때 또 오시긴 한다 ㅋㅋ. 파이썬 심화과정을 세세하게 잘 가르쳐 주시고 실무얘기를 듣는 등 어렵지만 아주 유익한 시간이었다고 생각한다. 이런 강사님들만 계신다면 끝까지 믿고 진행할 수 있을 것 같다.