Home

[백준] 2002번 추월 _ 문제 풀이

1. 문제 https://www.acmicpc.net/problem/2002 2. 풀이 ZG431SN : 0 ZG5080K : 1 ST123D : 2 ZG206A : 3 들어가는 차 번호 문자열을 들어온 순서대로 번호를 매겨줍니다. (0, 1, 2, 3) ZG206A : 3 ZG431SN : 0 ZG5080K : 2 ST123D : 1 나오는 차 번호 문자열을 매겨진 번호를 확인하여 배열에 집어 넣습니다. (3, 0, 2, 1) 배열에서 최소 값을 먼저 찾은 후에 앞에 있는 차들을 확인합니다. 앞에 있는 차들은 추월한차이기 때문에 정답에 추가해줍니다. 위에서 찾은 최소 값 이후에 ...

Read more

[백준] 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