🚗 프로그래머스 42839. 소수 찾기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers return
"17" 3
"011" 2
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
풀이
- 각 문자열에 대해 nP1, nP2, nP3, ... , nPn을 구해본다.
- 해당 숫자들이 소수인지 확인한다.
코드
import itertools
def is_prime(num): # 소수 판단 함수
if num < 2: # 2보다 작으면 소수가 아니다.
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0: # 0~num으로 나누었을때 나누어지는 수가 있으면 소수가 아니다.
return False
return True
def solution(numbers):
answer = []
for n in range(1, len(numbers) + 1): # nP1, nP2, nP3, ... , nPn 구하기
nPr = itertools.permutations(numbers, n)
pt = [''.join(p) for p in nPr] # join으로 튜플을 문자열로 바꾸어 리스트화 한다.
for l in pt:
if is_prime(int(l)): # 소수일때 정답리스트에 저장
answer.append(int(l))
return len(set(answer)) # 중복수 제거오답코드
import itertools
def solution(numbers):
answer = []
arr = []
for i in range(len(numbers)): # 문자열 -> 리스트
arr.append(numbers[i])
for n in range(1, len(arr)+1): # nP1, nP2, nP3, ... , nPn 구하기
nPr = itertools.permutations(arr, n)
pt = list(nPr)
for l in pt:
for m in range(2, l): # 소수 확인 반복문
if l % m == 0: # 소수일때
break
answer.append(l)
return len(answer)참고링크
🚗 백준 14889. 스타트와 링크
문제
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
-
스타트 팀: S12 + S21 = 1 + 4 = 5
-
링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다. -
스타트 팀: S13 + S31 = 2 + 7 = 9
-
링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
예제 입력 1
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
예제 출력 1
0
예제 입력 2
6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0
예제 출력 2
2
예제 입력 3
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0
예제 출력 3
1
힌트
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
알고리즘 분류
- 브루트포스 알고리즘
- 백트래킹
코드
def dfs(depth, idx):
global num
if depth == n//2: # 주어진 수의 절반이 한 팀으로 선택되었을때 가지치기 시작
team1, team2 = 0, 0
for i in range(n):
for j in range(n):
if visited[i] and visited[j]: #True의 값을 가지는 팀을 스타트팀이라 할때 스타트 팀의 능력치를 모두 team1에 더한다.
team1 += s[i][j]
elif not visited[i] and not visited[j]: # 나머지 절반 False의 값을 가지는 팀을 링크팀이라 할때 링크 팀의 능력치를 모두 team2에 더한다.
team2 += s[i][j]
num = min(num, abs(team1-team2)) # 능력치 차이 최소값 구하기
return
for i in range(idx, n): # 스타트 팀을 완성하지 못했을때) 백트래킹 실시
if not visited[i]: # 처음 방문하는 곳일때
visited[i] = True
dfs(depth+1, i+1) # 깊이 +1, 같은 번호 중복을 막기위한 idx+1로 재귀호출
visited[i] = False
if __name__ == '__main__':
import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
visited = [False for _ in range(n)]
num = 1000000000
dfs(0, 0)
print(num)참고링크
🚗 백준 16943. 숫자 재배치
문제
두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.
가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.
입력
첫째 줄에 두 정수 A와 B가 주어진다.
출력
B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.
제한
1 ≤ A, B < 109
예제 입력 1
1234 3456
예제 출력 1
3421
예제 입력 2
1000 5
예제 출력 2
-1
예제 입력 3
789 123
예제 출력 3
-1
알고리즘 분류
- 수학
- 브루트포스 알고리즘
- 조합론
- 백트래킹
코드
import sys
import itertools
input = sys.stdin.readline
if __name__ == '__main__':
a, b = input().split()
c = -1
nPn = itertools.permutations(a, len(a)) # nPn 구하기
pt = [''.join(p) for p in nPn] # join으로 튜플을 문자열로 바꾸어 리스트화 한다.
for i in pt:
if i[0] == '0': # 0으로 시작하는 경우
continue
i = int(i)
if int(i) < int(b): # b보다 작을 때
c = max(c, int(i)) # 최댓값 저장
print(c)🚗 14888. 연산자 끼워넣기
문제
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
출력
첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
예제 입력 1
2
5 6
0 0 1 0
예제 출력 1
30
30
예제 입력 2
3
3 4 5
1 0 1 0
예제 출력 2
35
17
예제 입력 3
6
1 2 3 4 5 6
2 1 1 1
예제 출력 3
54
-24
힌트
세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.
최댓값: 1-2÷3+4+5×6
최솟값: 1+2+3÷4-5×6
알고리즘 분류
- 브루트포스 알고리즘
- 백트래킹
코드
import sys
from itertools import permutations
input = sys.stdin.readline
if __name__ == '__main__':
N = int(input())
num = list(map(int, input().split()))
op_num = list(map(int, input().split())) # +, -, *, /
op_list = ['+', '-', '*', '/']
op = []
for k in range(len(op_num)): # 사칙연산 순환
for i in range(op_num[k]): # 해당 사칙연산에 대한 숫자 만큼
op.append(op_list[k]) # op에 저장한다.
maximum = -1000000000000000
minimum = 1000000000000000
for case in permutations(op, N - 1): # 사칙연산으로 만들 수 있는 경우의 수 모두 계산
total = num[0]
for r in range(1, N):
if case[r - 1] == '+':
total += num[r]
elif case[r - 1] == '-':
total -= num[r]
elif case[r - 1] == '*':
total *= num[r]
elif case[r - 1] == '/':
total = int(total / num[r])
if total > maximum: # 최댓값
maximum = total
if total < minimum: # 최솟값
minimum = total
print(maximum)
print(minimum)🚗 14891. 톱니바퀴 (오답)
문제
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.
이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.
톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.
두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.
위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.
톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
출력
총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.
- 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
- 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
- 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
- 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점
예제 입력 1
10101111
01111101
11001110
00000010
2
3 -1
1 1
예제 출력 1
7
예제 입력 2
11111111
11111111
11111111
11111111
3
1 1
2 1
3 1
예제 출력 2
15
예제 입력 3
10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1
예제 출력 3
6
예제 입력 4
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1
예제 출력 4
5
알고리즘 분류
- 구현
- 시뮬레이션
풀이
- 극이 다르면 서로 반대방향으로 회전
- 극이 같으면 회전 X
코드
import collections
import sys
from collections import deque
input = sys.stdin.readline
# 왼쪽 톱니바퀴 확인
def left(num, direction):
if num < 0: # 첫번째 톱니는 확인안함
return
if s[num][2] != s[num+1][6]: # 극이 다른경우
left(num-1, -direction) # 그 왼쪽 톱니바퀴도 조사
s[num].rotate(direction) # 현재 톱니바퀴는 회전
# 오른쪽 톱니바퀴 확인
def right(num, direction):
if num > 3: # 마지막은 확인안함
return
if s[num][6] != s[num-1][2]: # 극이 다른경우
right(num+1, -direction) # 그 오른쪽 톱니바퀴도 조사
s[num].rotate(direction) # 현재 톱니바퀴는 회전
if __name__ == '__main__':
s = []
for _ in range(4):
s.append(collections.deque(list(input())))
k = int(input()) # 회전횟수
r = [list(map(int, input().split())) for _ in range(k)]
for i in range(k):
num = r[i][0] - 1 # 돌아가는 톱니바퀴
direction = r[i][1] # 시계, 반시계방향
left(num-1, -direction) # 왼쪽조사
right(num+1, -direction) # 오른쪽조사
s[num].rotate(direction) # 현재 톱니바퀴는 회전
res = 0 # 점수
if s[0][0] == '1':
res += 1
if s[1][0] == '1':
res += 2
if s[2][0] == '1':
res += 4
if s[3][0] == '1':
res += 8
print(res)참고링크
