재밌는 코딩 공부

나의 풀이 

def bs(arr, start, end, wanted):
    if end == start:
        return arr[start]
    mid = (start + end) // 2
    
    total = 0
    for i in range(len(arr)):
        dok = arr[i] - arr[mid]
        if dok <0:
            dok = 0
        total += dok
    if total == wanted:
        return arr[mid]
    if total > wanted:
        bs(arr, mid+1, end, wanted)
    else:
        bs(arr, start, mid-1, wanted)

n, k = map(int, input().split())
doks = list(map(int, input().split()))
result = bs(doks, 0, n-1, k)
print(result)

정답

    # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
    n, m = list(map(int, input().split(' ')))
    # 각 떡의 개별 높이 정보를 입력받기
    array = list(map(int, input().split()))

    # 이진 탐색을 위한 시작점과 끝점 설정
    start = 0
    end = max(array)

    #이진 탐색 수행(반복적)
    result = 0
    while(start <= end):
        total = 0
        mid = (start + end) // 2
        for x in array:
            # 잘랐을 때의 떡의 양 계산
            if x > mid:
                total += x - mid
        # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
        if total < m:
            end = mid - 1
        # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
        else:
            result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
            start = mid + 1
    # 정답 출력
    print(result)

정답을 통해 나의 풀이가 잘못 된 것을 깨달았다. 나는 단순하게 배열을 이진 탐색해서 구할 생각을 하였는데

생각해보니 떡의 길이를 이진 탐색을 하는게 맞는거 같다. 

나의 풀이

n = int(input())
nArray = list(map(int, input().split()))
m = int(input())
mArray = list(map(int, input().split()))
answer = list()
s, e = 0, n-1

def binarySearch(arr, target, start, end):
    if end >= start:
        mid = (end + start) // 2
        if arr[mid] == target:
            answer.append('yes')
        elif arr[mid] > target:
            binarySearch(arr, target, start, mid-1)
        else:
            binarySearch(arr, target, mid+1, end)
    else:
        return answer.append('no')
        
for i in range(m):
    binarySearch(nArray, mArray[i], s, e)
    
for ans in answer:
    print(ans, end=' ')

정답

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None
    
n = int(input())
array = list(map(int, input().split()))
array.sort()
m = int(input())
x = list(map(int, input().split()))

for i in x:
    result = binary_search(array, i, 0, n - 1)
    if result != None:
        print('yes', end=' ')
    else:
        print('no', end=' ')

정답을 보고나니 이진 탐색은 작은 인덱스에는 작은 값이 인덱스가 높아지면 큰 값이 저장 되여 있다는 전제가 깔려야

해당 함수가 올바르게 작동한다. 하지만 나는 정렬하는 것을 까먹었다. 하지만 테스트케이스에서는 문제가 발생하지 않아서 잘 모르고 있었다.

n = int(input())
array = [0] * 1000001

for i in input().split():
    array[int(i)] = 1
    
m = int(input())
x = list(map(int, input().split()))

for i in x:
    if array[i] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

위와 같이 계수정렬로 풀수도 있다.

또한 아래와 같이 집합 해결할 수 있다.

n = int(input())
array = set(map(int, input().split()))

m = int(input())
x = list(map(int, input().split()))

for i in x:
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

나의 풀이

n, k = map(int, input().split())
sum = 0
a = list(map(int,input().split()))
b = list(map(int,input().split()))


a.sort()
b.sort(reverse = True)

for i in range(k):
    a[i] = b[i]
    
for i in range(n):
    sum += a[i]

print(sum)

정답

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]
    else:
        break
print(sum(a))

정답을 본 후 나의 풀이

n, k = map(int, input().split())
sum = 0
a = list(map(int,input().split()))
b = list(map(int,input().split()))


a.sort()
b.sort(reverse = True)

for i in range(k):
    if a[i] < b[i]:
        a[i] = b[i]
    else:
        break
    
for i in range(n):
    sum += a[i]

print(sum)

b의 가장 큰값이 a의 가장 작은 값보다 작을 수 있다는 가정을 빼먹고 문제를 풀었다. 정답을 본 후 그것을 빼먹었다는 것을 깨달았다.

나의 풀이

n = int(input())
dictGrade = {}

for i in range(n):
    name, grade = input().split(' ')
    dictGrade[name] = grade

sDictGrade = sorted(dictGrade, key = lambda x : dictGrade[x])

for key in sDictGrade:
    print(key, end=' ')

정답

n = int(input())

array = []
for i in range(n):
    input_data = input().split()
    array.append((input_data[0], int(input_data[1])))
    
array = sorted(array, key=lambda student: student[1])

for student in array:
    print(student[0], end = ' ')

이번 문제같은 경우 정답이 조금 해깔린다.

array = sorted(array, key=lambda student: student[1])

for student in array:
    print(student[0], end = ' ')

위 부분에 lambda 식에 처음 사용된 student가 갑자기 for문을 통해 정렬된 값을 나타내는 것으로 사용된다.

정렬된 값 array를 내버려두고 선언도 안한 student가 사용 되는 것은 혼란스러웠다

나의 풀이

n,m = map(int, input().split())
mins = list()

for i in range(n):
    min = 10001
    nums = list(map(int, input().split(' ')))
    for j in range(m):
        if min > nums[j]:
            min = nums[j]
    if min < 10001:
        mins.append(min)
print(max(mins))

답안

n, m = map(int, input().split())

result = 0
for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)
print(result)

해당 문제 풀이를 통해서 max와 min 사용법을 다시 익힐 수 있었고 해당 문제는 그리디 문제중 하 정도 되는 문제이다. 하급이라도 아직은 배울게 많은거 같다.

n, m, k = map(int, input().split())
nums = list(map(int, input().split()))
result = 0
nums.sort(reverse = True)

for i in range(2,m+2):
    if (k+1)%i != 0 :
        result += nums[0]
    else :
        result += nums[1]

print(result)

위와 같은 방식으로 문제를 해결하였다. 

range의 시작값과 끝 값을 각각 2를 더해준 이유는 0,1은 값이 나누어 떨어져서 시작부터 작은값을 넣고 시작해서 값에 오차가 발생해버린다. 이제 정답을 보겠다.

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n - 1]
second = data[n - 2]

result = 0

while True:
    for i in range(k):
        if m == 0:
            break;
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1

위와같이 효율적으로 처리하는 것이 정답이다.

k번 for문을 통해 최고의 값만 더하고 한번은 2번째 값을 더하는 것이 핵심 원리이다.

오늘은 이것이 코딩테스트에서 미로 탈출 문제를 풀어보았다.

# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.

from collections import deque

# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    # N, M을 공백으로 구분하여 입력받기
    n, m = map(int, input().split())
    # 2차원 리스트의 맵 정보 입력받기
    graph = []
    for i in range(n):
        graph.append(list(map(int ,input())))

    # 이동할 네 방향 정의(상, 하, 좌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # BFS 소스코드 구현
    def bfs(x, y):
        # 큐(Queue) 구현을 위해 deque 라이브러리 사용
        queue = deque()
        queue.append((x,y))
        # 큐가 빌 때까지 반복
        while queue:
            x, y = queue.popleft()
            # 현재 위치에서 네 방향으로의 위치 확인
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 미로 찾기 공간을 벗어난 경우 무시
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                # 벽인 경우 무시
                if graph[nx][ny] == 0:
                    continue
                # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx,ny))
            # 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1]
        # BFS를 수행한 결과 출력
    print(bfs(0, 0))

해당 문제를 풀다가 pycharm을 깔고 실행해보기위해서 깔고 reboot를 실행했는데 이전에

pythontutor에서 풀던 문제를 날려버리는 바람에 나의 답안은 버리게 되었다. 하지만 해당 방식은 dfs 방식이였기 때문에 위 방식이 답안이기 때문에 올바른 방식이다. 위 방식으로 한번 풀어보니 놀랍도록 멋진 코드인거 같다. 

해당 문제를 해커랭크에서 풀어보았습니다. 해당 문제는 해쉬로 푸는 문제지만 이번 문제의 경우 집합이 유리해보여서 set을 사용하였습니다. 

해당 문제의 코드는 아래와 같습니다.

def twoStrings(s1, s2):
    # Write your code here
    s1_set = set()
    isSub = False
    answer = 'NO'
    for str1 in s1:
        s1_set.add(str1)
    for str2 in s2:
        if str2 in s1_set:
            answer = 'YES'
            break
    return answer

해당문제를 풀면서 긴가민가 했던 부분이 있는데 스트링을 포문으로 그냥 range를 안쓰고 문자열로만으로 가능할지 의문이였는데 시도해보니 잘되는 것을 확인할 수 있었습니다.

https://www.acmicpc.net/problem/1325

오늘은 백준 문제 중 1325번 효율적인 해킹 문제를 해결해보았다. 해당 문제는 한번의 해킹으로 최대한 많은 컴퓨터를 해킹하기를 원한다. 각 컴퓨터는 신뢰 관계가 있는데 만약 신용 받는 컴퓨터를 해킹하면 신용하는 컴퓨터는 자동으로 해킹이 된다. 

해당 문제의 특징은 그래프가 일반 그래프가 아니라는 점과 한번에 가장 많은 수의 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 리턴해주어야 한다는 특징이 있다.

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)
    
def bfs(v):
    q = deque([v])
    visited = [False] * (n+1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in adj[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count
    
result = []
max_value = -1

for i in range(1, n+1):
    c = bfs(i)
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.append(i)
        max_value = c
for e in result:
    print(e, end=" ")

오늘은 백준 1012번 문제 유기농 배추 문제를 풀어보았다. 해당 문제를 보고 고민하다가 많은 시간을 고민하여도 해결되지 않아서 패스트캠퍼스 강의를 참조하여 많은 깨달음을 얻었다.

https://www.acmicpc.net/problem/1012

import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    visited[x][y] = True
    directions = [(-1,0),(1,0), (0,-1), (0,1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx,ny)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i, j)
                result += 1
    print(result)

위 코드를 활용해 답을 구하였다. 재밌는 점은 directions 리스트의 하나의 값에 x와 y 좌표를 담아 두었다. 그리고 for문을 돌면서 x,y좌표에 값을 더해서 돌도록 만들엇고 값의 범위가 올바른지 그리고 방문하지 않았던 좌표인지 그리고 벌레가 방문 할 수 있는 좌표인지 검증을 통해 dfs함수를 다시 호출한다. 해당 문제를 풀면서 dfs문제의 핵심이라 해도 될 정도로 중요한 문제라고 느꼈고 가끔식 복습해야겠다