BOJ
-
[백준] 6443 애너그램 with PythonPS 2022. 3. 2. 23:42
📌 BOJ 6443 애너그램 💡 조건 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin def solve(l, s): if l == 0: visited.add(s) return for i in range(26..
-
[백준] 2697 다음수 구하기 with PythonPS 2022. 3. 1. 22:59
📌 BOJ 2697 다음수 구하기 💡 조건 A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수. A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때. 첫째 줄에 테스트 케이스의 개수 T(1 data[idx]: a.append(b.pop(i)) a.extend(b) break print(''.join(map(str, a)))🔖 예제 및 실행결과 예제 3 123 279134399742 987실행결과 132 279134423799 BIGGEST⌨️ 문제 풀이 입력받은 숫자를 역순으로 탐색합니다. 왼쪽에 있는 값이 오른쪽보다 작아질 경우, idx에 해당 인덱스 값을 넣어줍니다. 숫자를 a 와 b 로 나누는데..
-
[백준] 1855 암호 with PythonPS 2022. 3. 1. 22:42
📌 BOJ 1855 암호 💡 조건 먼저 암호화 할 문자열을 1,1부터 위에서 아래 순서대로 채운다. 그리고 가장 밑의 행을 채운 후에는 오른쪽 열에서 다시 같은 과정을 반복한다. 암호화 된 문자열과 몇 개의 열로 암호화를 하였는지 주어져 있을 때 원래의 문자열을 구하는 프로그램을 작성하는 문제. 열의 개수 K(1 ≤ K ≤ 20)가 주어진다. 두 번째 줄에는 암호화 된 문자열(모두 영소문자)이 주어진다. (문자열의 길이는 200 이하이며 K의 배수이다.) 구현, 문자열 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) s = stdin.readline().rstrip() arr = [] for i in range(0, len(s), n): a..
-
[백준] 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..