PS
-
[백준] 1342 행운의 문자열 with PythonPS 2022. 3. 1. 03:58
📌 BOJ 1342 행운의 문자열 💡 조건 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin arr = stdin.readline().rstrip() cnt = 0 point = [0 for _ in range(26)] for i in arr: point[ord(i) - 97] += 1..
-
[백준] 18243 Small World Network with PythonPS 2022. 3. 1. 02:19
📌 BOJ 18243 Small World Network 💡 조건 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 모든 사람은 1부터 N까지 번호가 매겨져 있다. 두 번째 줄부터 K+1번째 줄까지 친구 관계를 나타내는 A B가 한 줄에 하나씩 주어진다. (1 ≤ A, B ≤ N) A와 B가 친구면 B와 A도 친구다. 자기 자신과 친구인 경우는 없다. A와 B의 친구 관계는 중복되어 입력되지 않는다. 해당 네트워크가 작은 세상 네트워크를 만족하면 "Small World!"를, 만족하지 않는다면 "Big World!"를 출력 BFS, 그래프 이론 유형의 문제 🖥 소스 코드 from sys import stdin from collec..
-
[백준] 15722 빙글빙글 스네일 with PythonPS 2022. 2. 27. 22:03
📌 BOJ 15722 빙글빙글 스네일 💡 조건 달팽이는 원점에서 시작하여 1초에 한 칸 씩, 시계방향으로 아래 그림과 같이 움직인다. 1초일 때 달팽이의 위치는 (0, 1)이다. 몇 초가 지났는지가 입력으로 주어질 때, 현재 달팽이의 위치를 좌표로 출력하는 문제 달팽이가 움직인 시간이 n초로 주어진다. (0 ≤ n ≤ 1000, n은 0이상의 정수) 구현, 시뮬레이션 유형의 문제 🖥 소스 코드 from sys import stdin def solve(): n = int(stdin.readline()) pos = [0, 0] mode, length = 0, 1 cnt = 0 while 1: for i in range(2): for _ in range(2): # Add if i == 0: if mode ==..
-
[백준] 14425 문자열 집합 with PythonPS 2022. 2. 27. 21:25
📌 BOJ 14425 문자열 집합 💡 조건 N개의 문자열로 이루어진 집합 S 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000) 어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 문자열, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) strings = {} for _ in range(n): strings[stdin.readline().rstrip()] = 0 for i in range(m): s = st..
-
[백준] 11501 주식 with PythonPS 2022. 2. 24. 18:26
📌 BOJ 11501 주식 💡 조건 홍준이는 요즘 주식에 빠져있다. 아래 세가지 중 하나의 행동을 한다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 테스트케이스 수를 나타내는 자연수 T. 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다. 최대 이익이 얼마나 되는지 계산을 해 출력하는 문제. 그리디 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin for tc in range(int(stdin.readline())): n = int(stdin.readline()) day..
-
[백준] 10546 배부른 마라토너 with PythonPS 2022. 2. 24. 18:13
📌 BOJ 10546 배부른 마라토너 💡 조건 참가자 수 N이 주어진다. (1 ≤ N ≤ 105) N개의 줄에는 참가자의 이름이 주어진다. N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다. 참가자들 중엔 동명이인이 있을 수도 있다. 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까? 해시맵 자료구조 응용 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) mara_tang = {} for _ in range(n): name = stdin.readline().rstrip() if name not in ..
-
[백준] 9372 상근이의 여행 with PythonPS 2022. 2. 22. 20:17
📌 BOJ 9372 상근이의 여행 💡 조건 N개국을 여행할 상근이에게 가장 적은 비행기를 타고 여행할 수 있게 도와주자. 테스트 케이스의 수 T(T ≤ 100) 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 그래프이론, 유니온-파인드 유형의 문제 🖥 소스 코드 from sys import stdin def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, paren..
-
[백준] 2628 종이 자르기 with PythonPS 2022. 2. 22. 20:01
📌 BOJ 2628 종이 자르기 💡 조건 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램 정렬 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin..
-
[백준] 2168 터널 위의 대각선 with PythonPS 2022. 2. 21. 17:23
📌 BOJ 2168 터널 위의 대각선 💡 조건 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 문제. x와 y는 1,000,000,000 이하의 자연수 수학, 정수론, 유클리드 호제법유형의 문제 🖥 소스 코드 from sys import stdin from math import gcd x, y = map(int, stdin.readline().split()) print(x + y - gcd(x, y))🔖 예제 및 실행결과 예제 ..
-
[백준] 2075 N번째 큰 수 with PythonPS 2022. 2. 21. 17:05
📌 BOJ 2075 N번째 큰 수 💡 조건 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 표에 채워진 수는 모두 다르다. N(1 ≤ N ≤ 1,500) 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 자료구조 응용, 우선순위 큐 활용, 정렬 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n = int(stdin.readline()) q = [] cnt = 0 for _ in range(n): data = list(map(int, stdin.readline().split())) for j in data: if cnt != n: heapq.heap..