본문 바로가기

BOJ 알고리즘 (패캠)/정렬, 탐색

 (17)
1668번: 트로피 진열 (탐색) - Fastcampus www.acmicpc.net/problem/1668 1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net # 보이는 트로피의 수 => 최대값이 갱신되는 횟수 카운팅 def search(N, heights): cnt = 0 max_v = -1e9 for x in heights: if x > max_v: max_v = x cnt += 1 return cnt N = int(input()) heights = [int(input()) for _ in range(N)] print(search(N, heights)) print(sear..
1302번: 베스트셀러 (탐색) - Fastcampus www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net # 베스트셀러 찾기 => 분류해서 카운팅 def search(books): d = {x: 0 for x in set(books)} for x in books: d[x] += 1 # lst = sorted(d, key=lambda x: (-d[x], x)) lst = [] for k, v in d.items(): if v == max(d.values()): lst.append(k) lst.sort() re..
1568번: 새 (탐색) - Fastcampus www.acmicpc.net/problem/1568 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현�� www.acmicpc.net O(sqrt(N)) # 모든 새가 날아가기까지 걸리는 시간 => 새 감소시키며 반복횟수 카운팅 def search(bird): sec, song = 0, 0 while bird: sec += 1 song += 1 if song > bird: song = 1 bird -= song return sec bird = int(input()) print(search(bird))
1543번: 문서 검색 (탐색) - Fastcampus www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한� www.acmicpc.net O(NM) = 10만 # 문서에서 단어 카운팅 def search(doc, word): cnt = 0 ld, lw = len(doc), len(word) i = 0 while i + lw
10989번: 수 정렬하기 3 (정렬, 계수정렬) - Fastcampus www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net # [KP] # 1> 메모리 제한으로 기본 정렬 함수로는 안됨 => 계수정렬 (숫자별 카운트) # 2> 시간 초과로 input() 함수로는 안됨 => sys.stdin.readline() import sys N = int(input()) ck = [0] * 10001 for _ in range(N): n = int(sys.stdin.readline()) ck[n] += 1 for i in range(1, 10001): cnt =..
11650번: 좌표 정렬하기 (정렬) - Fastcampus www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net import sys def sort(a): return sorted(a, key=lambda x: (x[0], x[1])) # 정렬 N = int(input()) nums = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)] ans = sort(nums) [print(x, y) for x, ..
10814번: 나이순 정렬 (정렬) - Fastcampus www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net import sys def sort(a): return sorted(a, key=lambda x: x[0]) # 정렬 N = int(input()) members = [] for _ in range(N): age, name = sys.stdin.readline().split() members.append((int(age), name)) ans = sort(members) [print(age, name) for a..
1427번: 소트 인사이드 (정렬) - Fastcampus www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net def sort(a): return sorted(a, reverse=True) # 정렬 def sort(a): res = [] for i in range(9, -1, -1): for j in a: if j == i: res.append(i) return res a = list(map(int, input())) ans = sort(a) print("".join(map(str, ans)))

티스토리툴바