본문 바로가기

ALGORITHM/백준67

[BOJ/PYTHON] 1764. 듣보잡 백준 문제 링크: https://www.acmicpc.net/problem/1764 문제 요약 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하기 핵심 아이디어 듣도 못한 사람과 보도 못한 사람 둘 다에 들어가있는 사람을 출력하면 된다. set을 사용하여 교집합으로 풀어줬다. 풀이 # silver4-1764. 듣보잡 # for문으로 순회해가며 not_seen_people에 not_heard_people 있으면 리스트에 넣는 식으로 했는데 시간 초과 import sys input = sys.stdin.readline n, m = map(int, input().split()) not_heard_people = [input().rstrip() for _ in .. 2023. 7. 27.
[BOJ/PYTHON] 16916. 부분 문자열 백준 문제 링크: https://www.acmicpc.net/problem/16916 문제 요약 P가 S의 부분문자열이면 1 출력 부분문자열: 문자열의 연속된 일부 핵심 아이디어 완전 쉽게 풀면 완전 쉽고 아니면 아닌 문제. 간단하게는 p in s로 s가 p 안에 있는지 판단하면 된다. 어렵게 풀면 KMP 알고리즘을 사용하면 된다. KMP 공부하는 겸 이 방법으로도 풀었다. 풀이 # gold3-16916. 부분 문자열 import sys input = sys.stdin.readline s = str(input().rstrip()) p = str(input().rstrip()) if p in s: print(1) else: print(0) # gold3-16916. 부분 문자열 import sys inpu.. 2023. 7. 27.
[BOJ/PYTHON] 1701. Cubeditor 백준 문제 링크: https://www.acmicpc.net/problem/1701 문제 요약 문자열에서 두 번 이상 나오는 부분문자열 중 가장 긴 길이 출력 abcabc : 3 abc ababcabab : 2 ab 핵심 아이디어 KMP에서 사용하는 테이블 만들기 알고리즘을 사용하면 된다. 풀이 # gold3-1701. Cubeditor import sys input = sys.stdin.readline string = input().rstrip() result = 0 # 매칭이 실패했을 때 얼마나 점프해야하는지를 접두사 접미사가 일치하는 것 기준으로 길이 알려줌. def make_table(pattern): table = [0] * len(pattern) j = 0 for i in range(1, le.. 2023. 7. 27.
[BOJ/PYTHON] 6996. 애너그램 백준 문제 링크: https://www.acmicpc.net/problem/6996 문제 요약 두 단어가 애너그램인지 아닌지 구하기 (애너그램: A에 속하는 알파벳의 순서를 바꾸어서 B를 만들 수 있음) 핵심 아이디어 구성 요소가 동일하면 되기에 두 단어 각각을 정렬하고 둘이 같은지 확인하면 된다. 풀이 # bronze1-6996. 애너그램 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): words = list(map(str, input().split())) first_word = sorted(list(words[0])) second_word = sorted(list(words[1])) if first_word == se.. 2023. 7. 27.
[BOJ/PYTHON] 11003. 최솟값 찾기 백준 문제 링크: https://www.acmicpc.net/problem/11003 문제 요약 본인 포함 본인부터 본인 기준 L번째 왼쪽(Ai-L+1 ~ A)까지 중 최솟값 리스트 출력 핵심 아이디어 슬라이딩 윈도우를 사용한다! 문제 자체는 플래티넘 수준이 아니지만 시간초과 기준 때문에 플래티넘 문제가 된 것 같다. 덱을 이용할 경우 인덱스 정보를 저장하는 게 핵심인데, 봐야 할 범위의 최소 인덱스보다 더 작은 인덱스가 남아있으면 볼 필요가 없으니까 버리면 된다. 그리고 while을 이용해 이번에 들어올 수보다 더 큰 수가 큐에 남아있다면 다 버린다. 최솟값을 찾는 거라 큰 수는 큐에 남아있을 필요가 없기 때문이다. 각 맨 앞에 있는 값을 출력하면 된다. 풀이 # platinum5-11003. 최솟값 .. 2023. 6. 15.
[BOJ/PYTHON] 4583. 거울상 백준 문제 링크: https://www.acmicpc.net/problem/4583 문제 요약 거울상 관계인 글자는 글자를 거울로 비추었을 때 거울에 반사되기 전 모습을 유추 가능 서로 거울상: b, d / p, q 자신과 거울상: i, o, v, w, x 거울상이 있으면 거울상 모습 출력, 없으면 INVALID를 출력. 핵심 아이디어 자신과 거울상인 경우의 self_mirror_list 리스트, 짝을 이뤄 거울상인 pair_mirror_list 리스트를 만들어줬다. 거울에 비춰지기 전 모습을 구해야 하는데, b가 오면 d를, d가 오면 b를, p가 오면 q를, q가 오면 p를 넣어주면 된다. 이것을 위해 pair_mirror_list에 각자의 거울상이 본인 바로 다음에 오게 배치해놨다. b 다음에 d,.. 2023. 6. 1.

티스토리툴바