dev-eunji

Lv2. 행렬의 곱셈

Mon, 15 Aug 2022 09:06:29 GMT

코딩테스트 연습 > 행렬의 곱셈

1. 풀이 설명

행렬의 곱셈은 (i * j) * (j * k) = (i * k) 이다.
answer 를 (i * k) 크기의 0 을 갖는 리스트로 초기화한다.
i, j, k 를 각각 3중 for문을 돌면서 (arr1, arr2 의 최대 크기는 100이다.) answer[i][k] += arr1[i][j] * arr2[j][k] 로 업데이트하여 answer 를 반환한다.

2. 나의 풀이

python

def solution(arr1, arr2):
    len_i = len(arr1)
    len_j = len(arr1[0])
    len_k = len(arr2[0])
    answer = [[0] * len_k for _ in range(len_i)]

    for i in range(len_i):
        for j in range(len_j):
            for k in range(len_k):
                answer[i][k] += arr1[i][j] * arr2[j][k]

    return answer

kotlin

fun solution(arr1: Array, arr2: Array): Array {
    val lenI = arr1.size
    val lenJ = arr1[0].size
    val lenK = arr2[0].size
    var answer = Array(lenI) { IntArray(lenK) }
    for(i in 0 until lenI) {
        for(j in 0 until lenJ) {
           for(k in 0 until lenK) {
                answer[i][k] += arr1[i][j] * arr2[j][k]
            }
        }
    }
    return answer
}

Lv2. 3 x n 타일링

Mon, 15 Aug 2022 08:53:35 GMT

코딩테스트 연습 > 3 x n 타일링

1. 풀이 설명

홀수인 경우에는 직사각형을 채울 수 없다.
memo 리스트를 0으로 초기화하고, n이 2인 경우에는 3, n이 4인 경우에는 11로 초기화한다.
2중 for문을 돌면서 memo[i] 를 업데이트 한다.

6부터 n까지 for문을 돌면서 memo[i] = memo[i-2] * 3 + 2
- i-2 길이를 채우고, 남은 길이2를 채울 수 있는 방법 3가지
- 특별한 케이스: +2
i-4부터 2까지 j가 2씩 작아지면서memo[i] += 2 * memo[j]
- 각 길이까지 채우고(memo[j]), 남은 길이를 특별한 케이스로 채울 수 있는 방법이
예를 들어 n = 8이라면,
- 6칸 채우고, 남은 2칸을 채우는 방법 3가지 memo[8] = memo[6] * 3
- 8 특별한 케이스: +2
- 4 칸 채우고, 남은 4칸의 특별한 케이스 * memo[4] :memo[8] += 2 * memo[4]
- 2칸 채우고, 남은 6칸의 특별한 케이스 * memo[2] :memo[8] += 2 * memo[2]

2. 나의 풀이

python

def solution(n):
    if n % 2 != 0:
        return 0
    memo = [0] * (n+1)
    memo[2] = 3
    memo[4] = 11
    for i in range(6, n+1, 2):
        memo[i] = memo[i-2] * 3 + 2
        for j in range(i-4, 0, -2):
            memo[i] += 2 * memo[j]
        memo[i] = memo[i] % 1000000007
    return memo[n]

3. 배운점

규칙을 찾기 어려웠던 문제다.
참고 문제

Lv2. 피로도

Mon, 15 Aug 2022 07:34:02 GMT

코딩테스트 연습 > 피로도

1. 풀이 설명

dungeons 의 크기가 최대 8이므로 완전탐색, 순열을 사용하여 문제를 풀었다.
dungeons 를 순열로 만들어서 모든 경우에 대해 count 를 계산하고 최대 count 를 반환한다.
- python: permutations
- kotlin: dfs

2. 나의 풀이

python

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    for dungeon in permutations(dungeons, len(dungeons)):
        current = k
        count = 0
        for d in dungeon:
            if current >= d[0]:
                current -= d[1]
                count += 1
        answer = max(answer, count)
    return answer

kotlin

class Solution {
    private val visited = BooleanArray(8)
    private var count = 0
    private var answer = 0

    fun solution(k: Int, dungeons: Array): Int {
        for (i in dungeons.indices) {
            dfs(k, i, dungeons)
        }
        return answer
    }

    private fun dfs(k: Int, current: Int, dungeons: Array) {
        for (i in dungeons.indices) {
            if (visited[i].not() && k >= dungeons[i][0]) {
                visited[i] = true
                count += 1
                answer = Math.max(answer, count)
                dfs(k - dungeons[i][1], i, dungeons)
                visited[i] = false
                count -= 1
            }
        }
    }
}

3. 배운점

순열로 완전탐색 풀기

python 순열
```
from itertools import permutations
```

permutations(list, len(list))


- kotlin 순열
```kotlin
fun a() {
    for (i in list.indices) {
        dfs(i, list)
    }
}

fun dfs(current: Int, list: List) {
    for (i in list.indices) {
        visited[i] = true
        dfs(i, list)
        visited[i] = false
    }
}

Lv2. 방문 길이

Sun, 14 Aug 2022 10:27:32 GMT

코딩테스트 연습 > 방문 길이

1. 풀이 설명

"지나가 본 길을 어떻게 저장할지" 가 중요한 문제다.
출발점인 (0,0) 을 visited[5][5] 위치로 설정했다. 점 사이를 거리로 보고, 각 위치의 점은 4개의 False 로 초기화한 아이템을 갖는 list 값을 갖는다. list는 방문 여부에 대한 flag 이다. (오른쪽에서 방문, 아래에서 방문, 왼쪽에서 방문, 위에서 방문) 예를 들어, 출발점인 (5,5)는 visited[5][5] 이고, visited[5][5] = [False, False, False, False] 로 초기화 되어있다.

(6,4)  (6,5)  (6,6) 
-----------------
|          |        |
-----------------
(5,4)  (5,5)  (5,6)

dirs 를 for문 돌면서, index 가능여부를 체크를 하고 이동이 가능하다면, 3-1.d에 맞게 이동을 시킨다. 3-2. 방문한 적이 없다면, 방문 체크를 한 후에 answer +1 을 해준다.

 (이동 후의 점에 해당하는 거리와 이동 전 점에 해당하는 거리의 방문 여부를 모두 True 로 변경한다.)

ex) (3,5) 위치에서 d 가 "U" 라면
y 는 4가 되고 (3,5) 에서 (4,5) 로 이동하는 것이기 때문에
visited[4][5][1] = True # (4,5) 의 아래에서 방문 여부 True 
visited[3][5][3] = True # (3,5) 의 위에서 방문 여부 True

2. 나의 풀이

python

def solution(dirs):
    answer = 0

    # R, D, L, U
    visited = [[[False, False, False, False]  for _ in range(11)] for _ in range(11)]
    y, x = 5, 5

    for d in dirs:
        if d == "U":
            if 0 <= y < 10:
                y += 1
                if not visited[y][x][1] and not visited[y-1][x][3]:
                    visited[y][x][1] = True
                    visited[y-1][x][3] = True
                    answer += 1
        elif d == "D":
            if 0 < y <= 10:
                y -= 1
                if not visited[y][x][3] and not visited[y+1][x][1]:
                    visited[y][x][3] = True
                    visited[y+1][x][1] = True
                    answer += 1
        elif d == "R":
            if 0 <= x < 10:
                x += 1
                if not visited[y][x][2] and not visited[y][x-1][0]:
                    visited[y][x][2] = True
                    visited[y][x-1][0] = True
                    answer += 1
        else:
            if 0 < x <= 10:
                x -= 1
                if not visited[y][x][0] and not visited[y][x+1][2]:
                    visited[y][x][0] = True
                    visited[y][x+1][2] = True
                    answer += 1
    return answer

Lv2. 타겟 넘버

Sun, 14 Aug 2022 08:27:27 GMT

코딩테스트 연습 > 타겟 넘버

1. 풀이 설명

아래와 같은 tree 를 생각하면서 문제를 풀었다.

                                                                                    n
                        0                                            level 1            

          1                             -1                            level 2            1

    2           0               0               -2                    level 3            1

3       1   1       -1      1       -1      -1      -3                level 4            1

parent 리스트에 0을 넣어 초기화하며, numbers for문을 돌면서 (n) 트리가 한 층씩 내려간다.
parent 아이템에 +n, -n 을 한 값들로 parent 를 업데이트 해준다.
parent 리스트 아이템들 중에서 target 의 개수를 반환한다.

2. 나의 풀이

python

def solution(numbers, target):
    parent = [0]
    for n in numbers:
        children = []
        for p in parent:
            children.append(p + n)
            children.append(p - n)
        parent = children
    return sum([1 for p in parent if p == target])

kotlin

fun solution(numbers: IntArray, target: Int): Int {
    var parent = mutableListOf(0)
    numbers.forEach { number ->
        val children = mutableListOf()
        parent.forEach { node ->
            children.add(node + number)
            children.add(node - number)
        }
        parent = children
    }
    return parent.count { it == target }
}

Lv2. 게임 맵 최단거리

Sun, 14 Aug 2022 06:40:37 GMT

코딩테스트 연습 > 게임 맵 최단거리

1. 풀이 설명

전형적인 BFS문제다. 방향좌표 dx, dy 를 활용하여 map 을 최단거리로 이동해야 한다.
visited 리스트에는 현재 위치에 거리가 저장된다. visited[0][0] = 1 로, queue 에는 (0, 0) 을 넣어 초기화한다.
queue 의 아이템을 하나씩 빼면서 비지 않을 때 까지 돌고, queue 에서 빼낸 현재 위치에서 방향좌표에 따라 한 step 씩 움직이며 visited와 queue 를 업데이트 한다.
visited 의 마지막 위치(visited[-1][-1])를 반환한다.

2. 나의 풀이

python

import collections

def solution(maps):
    return bfs(maps)

def bfs(maps):
    dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
    n, m = len(maps), len(maps[0])
    visited = [[-1] * m for _ in range(n)] 
    visited[0][0] = 1
    queue = collections.deque([(0, 0)])

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if visited[ny][nx] == -1 and maps[ny][nx] == 1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append((ny, nx))

    return visited[-1][-1]

3. 배운점

행렬 map을 다룰 때 주의할 점 n * m 행렬에서 ** 행 == n == y ** 이다. 위치를 표현할 때 (x, y) 라고 말하지만 실제 x 위치에는 행에 해당하는 y 를 놓고 문제를 풀어야 한다.
아래 둘은 다르다.

visited = [[-1] * m] * n

visited = [[-1] * m for _ in range(n)]

Lv2. [1차] 캐시

Sat, 13 Aug 2022 13:53:35 GMT

코딩테스트 연습 > 스킬트리

1. 풀이 설명

cacheSize 가 0인 경우에는 캐시를 사용하지 않으므로 5 * cities 의 사이즈를 반환한다.
cities 를 돌면서, city 를 모두 lowerCase로 변경한다 (대소문자 구분 없음)
city 가 cache 에 있다면 (cache hit) 으로 +1 후에 cache 의 key 값으로 city 를 value 로 idx 를 저장한다.
- idx 는 얼마나 최근에 참조되었는지를 나타낸다.
city 가 cache 에 없다면, cache 사이즈를 검사하고 cache 사이즈가 casheSize 보다 작다면 cache[city] = idx 로 저장한다. 그 외 cache 가 찼다면 cache 중 가장 작은 value 값을 찾고, 가장 작은 value 값을 갖는 item을 pop 한 후에 cache[city] = idx 를 저장한다. (새로운 city 저장)

2. 나의 풀이

python

def solution(cacheSize, cities):
    answer = 0
    cache = {}

    if cacheSize == 0:
        return 5 * len(cities)

    for idx, city in enumerate(cities):
        city = city.lower()
        if city in cache:   # cache hit
            answer += 1
            cache[city] = idx
        else:               # cache miss
            answer += 5
            if len(cache) < cacheSize:
                cache[city] = idx
            else:
                least = min(cache.values())
                for key, value in cache.items() :
                    if value == least:
                        cache.pop(key)
                        cache[city] = idx
                        break
    return answer

3. 배운점

OS 페이지 교체 알고리즘

운영체제에서 메모리를 관리할 때, 현재 페이지 중 어떤 것과 교체할 지를 결정하는 알고리즘이다. 대표적으로 FIFO LFU LRU 등이 있다.

그 중 LRU (Least Recently Used Algorithm) 는 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다. 단점으로는 프로세스가 참조한 페이지의 시간을 기록해야하는 오버헤드 발생한다는 점이다.

dictionary 조회

for key, value in dictionary.items():
    print(key, value)

deque 의 최대 길이를 설정하여 푸는 풀이도 있다. (다른 사람 풀이 참고)

함수 내에서 import 문을 사용할 수 있다.
collections.deque(maxlen=cacheSize)

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    answer = 0
    for city in cities:
        c = city.lower()
        if c in cache:
            answer += 1
            cache.remove(c)
            cache.append(c)
        else:
            answer += 5
            cache.append(c)
    return answer

deque(['pangyo', 'seoul', 'newyork'], maxlen=3)

인 상태에서 'LA' 차례가 된다면, 아래와 같이 cache 가 업데이트 된다. 

deque(['seoul', 'newyork', 'la'], maxlen=3) # 'la'가 append 되면서, 제일 앞에 있던 'pangyo'가 삭제됨.

Lv2. 스킬트리

Sat, 13 Aug 2022 13:04:01 GMT

코딩테스트 연습 > 스킬트리

1. 풀이 설명

skill_trees 를 하나씩 돌면서(t) 아래 조건을 만족할 때 answer 개수를 +1 하여 반환한다.

skill 을 list 로 변환한 후(list_skill)
t 의 현재 순서가 list_skill 에 포함되지 않거나, 포함된다면 0번째에 위치하여야 한다.

2. 나의 풀이

python

def solution(skill, skill_trees):
    answer = 0
    for tree in skill_trees:
        success = True
        list_skill = list(skill)
        for t in tree:
            if t in list_skill:
                if t != list_skill.pop(0):
                    success = False
                    break
        if success:
            answer += 1
    return answer

3. 배운점

다른 사람들의 풀이를 보면서 많이 배운 문제다.

for-else 문: flag success 변수를 없앨 수 있다.

for문 중간에 break 로 빠져나올 때가 있다. break 문으로 빠져나오지 않았다면 for-else 문의 else 문으로 들어가게 된다.

개선된 코드

def solution(skill, skill_trees):
 answer = 0
 for tree in skill_trees:
     list_skill = list(skill)
     for t in tree:
         if t in list_skill:
             if t != list_skill.pop(0):
                 break
     else:
         answer += 1
 return answer

list 대신 deque 을 사용할 수 있다: deque.popleft()

import collections

def solution(skill, skill_trees):
    answer = 0
    for tree in skill_trees:
        deque = collections.deque(skill)
        for t in tree:
            if t in deque:
                if t != deque.popleft():
                    break
        else:
            answer += 1
    return answer

string to char(string) list

str = "CBD"

list(str) # ['C', 'B', 'D']

Lv2. 멀리 뛰기

Tue, 09 Aug 2022 14:09:40 GMT

코딩테스트 연습 > 멀리 뛰기

1. 풀이 설명

한 번에 1칸 또는 2칸만 오를 수 있다. 따라서, memo[i] (i번째 칸을 오를 수 있는 방법의 수) 는 memo[i-1] (i-1 번째 칸까지 올라올 수 있는 경우의 수) + memo[i-2](i-2 번째 칸까지 올라올 수 있는 경우의 수) 이다.
- i-1 번째에서 1칸을 오르거나 i-2 번째 칸에서 2칸을 올라올 수 있다.
전형적인 DP 문제로 풀 수 있다.

2. 나의 풀이

python

def solution(n):
    if n == 1:
        return 1

    memo = [0] * n
    memo[0] = 1
    memo[1] = 2

    for i in range(2, n):
        memo[i] = (memo[i-1] + memo[i-2]) % 1234567

    return memo[n-1]

kotlin

fun solution(n: Int): Long {
    if (n == 1) return 1

    val memo = LongArray(n)
    memo[0] = 1L
    memo[1] = 2L

    for (i in 2 until n) {
        memo[i] = (memo[i-1] + memo[i-2]) % 1234567
    }

    return memo[n-1]
}

3. 배운점

n 이 1인 경우에 대한 예외처리

Lv2. 오픈채팅방

Mon, 08 Aug 2022 14:06:19 GMT

코딩테스트 연습 > 오픈채팅방

1. 풀이 설명

python

record 를 split() 하여 0번째 값이 각각 Enter or Leave 일 때와 Enter or Change 일 때 아래 로직을 수행한다.
- Enter or Leave : orders 에 <첫 단어, ID> 를 추가
- Enter or Change : dic[ID] = 닉네임 업데이트
orders를 돌면서 answer 리스트에 첫 단어가 Enter 일 때는 "dic[유저 ID] (== 최종 닉네임) 님이 들어왔습니다.", Leave 일 때는 "~~님이 나갔습니다." 를 리스트에 추가하여 반환한다.

kotlin

record 를 split() 하고, 0번째 값이 각각 Enter,Leave,Change 일 때 아래 로직을 수행한다.
- Enter : map[ID] = 닉네임 업데이트, answer 리스트에 [ID] 들어왔습니다. 추가
- Leave : answer 리스트에 [ID] 나갔습니다. 추가
- Change : map[ID] = 닉네임 업데이트
answer를 돌면서 각 아이템을 split() 하여 map[<0번째 아이템>]님이 <1번째 아이템> 로 변환한 후 반환한다.

2. 나의 풀이

python

def solution(record):
    answer = []
    dic = {}
    orders = []

    for r in record:
        list = r.split()
        if list[0] == 'Enter' or list[0] == 'Leave':
            orders.append([list[0], list[1]])
        if list[0] == 'Enter' or list[0] == 'Change':
            dic[list[1]] = list[2]

    for order in orders:
        if order[0] == 'Enter':
            answer.append(dic[order[1]] + "님이 들어왔습니다.")
        else:
            answer.append(dic[order[1]] + "님이 나갔습니다.")

    return answer

kotlin

fun solution(record: Array): Array {
    val answer = mutableListOf()
    val map = HashMap() // 

    record.forEach { r ->
        val input = r.split(" ")
        val id = input[1]
        when(input[0]) {
            "Enter" -> {
                map[id] = input[2]
                answer.add("$id 들어왔습니다.")
            }
            "Leave" -> answer.add("$id 나갔습니다.")
            "Change" -> map[id] = input[2]
        }
    }

    return answer.map { str ->
        "${map[str.split(" ")[0]]}님이 ${str.split(" ")[1]}"
    }.toTypedArray()
}

Lv2. 짝지어 제거하기

Sun, 07 Aug 2022 13:44:48 GMT

코딩테스트 연습 > 짝지어 제거하기

1. 풀이 설명

stack 변수를 정의하고, s 를 하나씩 for문 돌면서
stack이 비어있거나 stack의 마지막 아이템과 현재 값이 다르면 stack 에 현재 값을 추가하고
stack의 마지막 아이템과 현재 값이 같다면, stack의 마지막 아이템을 pop() 한다.
stack이 비어있으면 1, 비어있지 않다면 0을 반환한다.

2. 나의 풀이

python

def solution(s):
    stack = []    
    for c in s:
        if len(stack) == 0:
            stack.append(c)
        else:
            if c == stack[-1]:
                stack.pop()
            else:
                stack.append(c)
    if stack:
        return 0
    else:
        return 1

3. 배운점

Stack을 활용해야 하는 문제라는 것을 인지하기까지 시간이 걸려서 아쉬웠던 문제. 입력 문자열의 길이가 최대 1,000,000 임에도 앞에서부터 차례로 현재 index와 다음 index의 값이 같으면 pop() 하는 방법을 시도했었다. (current) 결과는 일부 테스트케이스 시간초과 Fail 이었다.

def solution(s): # 시간초과
    current = s
    count = 0
    while True:
        if current == '':
            return 1

        result = ''
        count = 0
        i = 0
        while i < len(current):
            if i < len(current) - 1 and current[i] == current[i+1]:
                i += 2
                count += 1
            else:
                result += current[i]
                i += 1
        current = result

        if count == 0:
            return 0
    return 0

비슷한 문제 (같은 문자일 때 삭제 등)를 다시 만난다면, 또는 입력 값이 커서 위와 같은 탐색방법으로 문제가 풀리지 않는다면 stack, queue 등 자료구조를 하나씩 떠올리며 사용할 수 있을지 점검해 봐야겠다.

리스트가 비어있는지 검사: if not list:

if stack:         # 으로 stack 이 비어있지 않음을 검사한 거 처럼

if not stack: # stack 이 비어있음을 검사한다.

Lv2. 2 x n 타일링

Sun, 07 Aug 2022 10:39:29 GMT

코딩테스트 연습 > 2 x n 타일링

1. 풀이 설명

n=1 부터 하나씩 n 을 늘려가면서 규칙을 찾아본다.

n = 1     1

n = 2    2

n = 3    3    <-- n=1 + n=2

n = 4    5    <-- n=2 + n=3

n = 5    8    <-- n=3 + n=4

그림을 그려서 보면, N 번째 경우 세로 1칸 + (N-1)칸, 가로 2칸 + (N-2)칸으로 나타내 볼 수 있다.

2. 나의 풀이

python

def solution(n):
    list = [1, 2]
    for i in range(2, n):
        list.append((list[i-2] + list[i-1]) % 1000000007)
    return list[n-1]

3. 배운점

주어진 내용 안에서 최대한의 규칙을 찾아본다. 그림을 그려서 보면 더 좋다.

Lv2. 소수 찾기

Sun, 07 Aug 2022 10:21:06 GMT

코딩테스트 연습 > 소수 찾기

1. 풀이 설명

2. 나의 풀이

from itertools import permutations

def solution(numbers):
    result = []
    for i in range(1, len(numbers)+1):
        for tp in permutations(numbers, i):
            num = int(''.join(map(str, tp)))
            if is_prime(num):
                result.append(num)
    return len(set(result))


def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

3. 배운점

python

순열을 구해주는 라이브러리를 알게 되었다: from itertools import permutations
```
from itertools import permutations
```

permutation(list, n) # list 를 n개씩 묶어주는 리스트를 반환

```

참고

Lv2. 피보나치 수

Sun, 07 Aug 2022 05:11:42 GMT

코딩테스트 연습 > 피보나치 수

1. 풀이 설명

memo 리스트에 계산 결괏값을 저장한 후, memo[n] 을 반환한다.
- 리스트 변수 저장 없이 재귀함수를 사용하면 메모리 초과 실패가 발생한다.

2. 나의 풀이

python

 def solution(n):
    memo = [0, 1]
    for i in range(2, n+2):
        memo.append((memo[i-1] + memo[i-2]) % 1234567)
    return memo[n]

kotlin

fun solution(n: Int): Int {
   val memo = IntArray(n + 1)
   for (i in 0..n) {
       when (i) {
           0 -> memo[0] = 0
           1 -> memo[1] = 1
           else -> memo[i] = (memo[i - 1] + memo[i - 2]) % 1234567
       }
   }
   return memo[n]
}

3. 배운점

저장된 값을 12345로 나눈 나머지를 반환해야하는 문제일 때, 저장하는 시점부터 12345로 나눈 나머지 값을 저장할 수 있다.

Lv2. 최댓값과 최솟값

Sun, 07 Aug 2022 04:57:46 GMT

코딩테스트 연습 > 최댓값과 최솟값

1. 풀이 설명

두 배열에서 숫자를 하나씩 골라 두 수를 곱한 값의 누적 합이 최솟값을 갖도록 구하는 문제다.
한 배열의 최솟값과 다른 배열의 최댓값을 차례로 계산한다.

2. 나의 풀이

python

def solution(A,B):
    answer = 0
    A.sort()
    B.sort(reverse = True)
    for i in range(len(A)):
        answer += A[i] * B[i]
    return answer

3. 배운점

두 배열의 곱한 값의 누적 합의 최솟값은 각 배열의 최솟값 최댓값을 곱해주어 구할 수 있다.

python

한 줄 코드: sum(), zip()

def solution(A,B):
 return sum(a*b for a, b in zip(sorted(A), sorted(B, reverse=True)))

Lv2. 최댓값과 최솟값

Sun, 07 Aug 2022 04:00:03 GMT

코딩테스트 연습 > 최댓값과 최솟값

1. 풀이 설명

s를 " " 기준으로 split() 한 후에 리스트 아이템을 int 형으로 변환한다.
int list 중에서 최솟값과 최댓값을 string으로 반환한다.

2. 나의 풀이

python

def solution(s):
    value = list(map(int, s.split()))
    return " ".join([str(min(value)), str(max(value))])

kotlin

fun solution(s: String): String =
    s.split(" ").map { c ->
        c.toInt()
    }.run {
        return "${minOf { it }} ${maxOf { it }}"
    }

3. 배운점

python

string list to int list: list(map(int, str_list))

convert-all-strings-in-a-list-to-int

kotlin의 "${value1} ${value2}" == str(value1) + " " + str(value2)

# asis
" ".join([str(min(value)), str(max(value))])

# tobe
str(min(value)) + " " + str(max(value))
``

Lv2. 더 맵게

Sun, 07 Aug 2022 03:41:09 GMT

코딩테스트 연습 > 더 맵게

1. 풀이 설명

최솟값을 계속해서 얻어야 하는 문제기 때문에 min heap을 사용한다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 가 언제일지를 고민해봐야 한다.
- 가장 맵지 않은 음식(a)과 두 번째로 맵지 않은 음식(b) 2개의 아이템을 heap 에서 pop 하여 a+b*2로 계산한 새로운 1개의 아이템을 heap 에 넣게 된다. 즉, heap 아이템 수가 1개씩 줄어든다.
- while문은 heap 의 최솟값이 K 미만일 때 계속 돌게 되는데, heap 의 개수가 1개이면서 최솟값이 K 미만일 때 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 케이스가 된다.
while 문을 1번 돌 때마다 count 를 더하여 반환한다.

2. 나의 풀이

import heapq

def solution(scoville, K):
    heap = []
    answer = 0
    for s in scoville:
        heapq.heappush(heap, s)

    while heap[0] < K:
        if len(heap) == 1:
            return -1
        mixed = heapq.heappop(heap) + heapq.heappop(heap) * 2
        heapq.heappush(heap, mixed)
        answer += 1
    return answer

3. 배운점

Heap (힙)

힙은 완전이진트리로 최솟값과 최댓값을 찾는 연산을 빠르게 수행할 수 있다.
- Min Heap: 부모 키값이 자식 노트 키값보다 항상 작음 (<-> Max Heap)
- 형제 노드 사이에 대소 관계 규칙 없음

Heap 사용법
```
import heapq
```

heap = [] # default: Min Heap

heapq.heappush(heap, item) # push heapq.heappop(heap) # pop heap[idx] # 조회

Max Heap

heapq.heappush(heap, (-item, item)) # (priority, value)

Lv2. 영어 끝말잇기

Sat, 06 Aug 2022 14:02:58 GMT

코딩테스트 연습 > 영어 끝말잇기

1. 풀이 설명

words 를 for 문을 돌면서 이전에 나왔던 단어이거나, 직전 알파벳과 현재 처음 알파벳이 다르거나, 단어의 개수가 1인 경우에 [번호, 순서]를 반환한다.
위의 3가지 경우에 포함되지 않는다면 [0,0] 을 반환한다.

2. 나의 풀이

def solution(n, words):
    list = []
    last_c = ''
    for i, word in enumerate(words):
        if (word in list) or (last_c != '' and last_c != word[0]) or len(word) == 1:
            return [i%n+1, i//n+1]
        list.append(word)
        last_c = word[-1]
    return [0,0]

3. 배운점

last_c 로 직전 마지막 알파벳을 저장해서 다음번 for 문에 이용할 수 있다.
입력 parameter를 print 해보면서 로직과 반환 값에 대해 생각해본다: 번호i%n+1, 순서i//n+1

Lv2. N개의 최소공배수

Sat, 06 Aug 2022 09:36:14 GMT

코딩테스트 연습 > N개의 최소공배수

1. 풀이 설명

lcm 을 1로 초기화 한다.
arr 를 for 문 돌면서, lcm 과 현재 숫자의 lcm 을 구하여 업데이트 한다.
lcm 을 반환한다.

arr: 2 6 8 14
                lcm
2                2
2 * 3            2 * 3
2 * 2 * 2        2 * 2 * 2 * 3
2 * 7            2 * 2 * 2 * 3 * 7

2. 나의 풀이

python

def solution(arr):
    size = len(arr)
    lcm = 1
    for n in arr:
        lcm = lcm * n  / gcd(lcm, n)
    return lcm

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

kotlin

fun solution(arr: IntArray): Int =
    arr.fold(1) { lcm, n ->
        lcm * n / gcd(lcm, n)
    }

fun gcd(a: Int, b: Int): Int {
    if (a % b == 0) return b
    return gcd(b, a % b)
}

3. 배운점

최대공약소, 최소공배수: 참고문제

Lv2. 땅따먹기

Sat, 06 Aug 2022 09:01:46 GMT

코딩테스트 연습 > 땅따먹기

1. 풀이 설명

2번째 row부터 for 문을 돌면서 이전 row 중 현재 col과 다르고, 가장 큰 값을 land[i][j] 에 더한다.
마지막 row 의 값 중 가장 큰 값을 반환한다.

2. 나의 풀이

def solution(land):
    for i in range(1, len(land)):
        for j in range(4):
            land[i][j] += max(land[i-1][k] for k in range(4) if k != j)
    return max(land[-1])

3. 배운점

이전 값을 활용해서 현재 값 (land[i][j])을 업데이트 하는 방법

이전 row 중 최대 값
```
max(land[i-1][k] for k in range(4))
```