Home

[백준] 2696번 중앙값 구하기 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/2696 2. 풀이 배열을 모두 입력 받은 후에, 요구하는 크기만큼 정렬하여 중간값을 출력해주면 쉽게 문제풀이 할 수 있습니다. 하지만 매번 정렬하는데 시간이 매우 걸립니다. 시간을 줄이기 위해서는 최소힙, 최대힙을 이용하여 중간값보다 작은 숫자, 큰 숫자를 따로 저장하고 있다가 매번 힙의 크기를 맞춰주면서 수를 추가해주면 훨씬 더 빠르게 풀이 할 수 있습니다. T = int(input()) for _ in range(T): M = int(input()) print(M//2 + 1) arr = [] for __ ...

Read more

[백준] 2304번 창고 다각형 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/2304 2. 풀이 N = int(input()) cols = [] for _ in range(N): cols.append(list(map(int,input().split()))) cols.sort(key=lambda x: x[0]) # 최대 col 찾기 max_idx = cols.index(max(cols, key=lambda x: x[1])) answer = cols[max_idx][1] # 왼쪽. 맨 왼쪽에서부터 최대 인덱스까지 자신과 크기가 작은 얘들은 무시하고, 크거나 같은 얘를 만나면 지붕을 세움 this_idx = 0 f...

Read more

[백준] 2075번 N번째 큰 수 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/2075 2. 풀이 2.1. 메모리 초과 코드 배열 하나에 모든 수를 넣은 뒤에 정렬하고 답을 출력. 메모리 초과가 발생하였습니다. n = int(input()) arr = [] [arr.extend(list(map(int, input().split()))) for _ in range(n)] print(sorted(arr)[-n]) 2.2. 정답 코드 n개만큼 계속 배열을 추가하면서 정렬하고 추가하는 과정을 반복합니다. n = int(input()) arr = [] for _ in range(n): arr.extend(lis...

Read more

[백준] 1302번 베스트셀러 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/1302 2. 풀이 개수를 딕셔너리를 이용하여 확인해 줍니다. 이후, (-개수, 이름) 으로 만들어진 배열을 정렬하면 개수가 가장 많고 사전순으로 가장 이름이 빠른 요소가 맨 앞에 나오게 됩니다. n = int(input()) dict = {} for _ in range(n): now_str = input() if dict.get(now_str, 0): dict[now_str] += 1 else: dict[now_str] = 1 print(sorted([(-val, key) for key, ...

Read more

[백준] 9095번 1, 2, 3 더하기 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/9095 2. 풀이 2.1. 내 풀이 dfs 를 이용하여 문제를 해결해주었습니다. 방문한 곳은 visited 배열로 표기하여 사용한 숫자를 체크하였고, 이후 reduce를 이용하여 사용한 숫자의 배치 가능한 개수를 구했습니다(예_ 1,2,3,3 은 4!/2! ). from functools import reduce def val(n, n_1, n_2, n_3): global is_visited, answer if is_visited[n_1][n_2][n_3]: return is_visited[n_1][n...

Read more

[백준] 3986번 좋은 단어 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/3986 2. 풀이 스택을 이용하여 문제를 해결하면 손쉽게 해결할 수 있습니다. 스택에 문자열을 넣으면서 같은 문자열이 2개 겹치면 바로 제거해줍니다. 아닌 경우 계속 진행하고 최종으로 배열에 아무 문자도 남아있지 않으면 좋은 단어로 판별합니다. n = int(input()) ans = 0 for _ in range(n): stk = [] for x in input(): if len(stk) == 0: stk.append(x) continue if stk...

Read more

[백준] 4963번 섬의 개수 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/4963 2. 풀이 dfs 를 이용하여 문제를 해결해주었습니다. 8방향 모두를 확인하면서 문제를 해결해야합니다. import sys sys.setrecursionlimit(10**4) # 상, 상우, 우, 우하, 하, 좌하, 좌, 좌상 dr = [-1, -1, 0, 1, 1, 1, 0, -1] dc = [0, 1, 1, 1, 0, -1, -1, -1] def dfs(w, h, maps, is_visited, r, c): if is_visited[r][c] or maps[r][c] == 0: return is_vi...

Read more

[백준] 11729번 하노이 탑 이동 순서 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/11729 2. 풀이 hanoi 탑은 출발지(from), 임시장소(sub), 도착지(to) 3가지로 이루어져있습니다. 순서는 아래와 같습니다. n번째 요소를 제외한 n-1개의 요소들을 sub로 옮깁니니다. n번째 요소를 바로 도착지 to로 옮깁니다. sub에 있는 요소들을 from을 임시장소로 이용하여 to로 옮깁니다. move_arr = [] def hanoi(n, fromm, sub, to): if n == 0: return hanoi(n - 1,...

Read more