코딩테스트 문제풀이

문제풀이

1번 문제

2309: 일곱 난쟁이

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

예제 입력 1
20
7
23
19
10
15
25
8
13

예제 출력 1
7
8
10
13
19
20
23

import itertools
array = []
for i in range(9):
  array.append(int(input()))
# 조합을 사용해서 2명씩 짝지음
dd = list(itertools.combinations(array,2))
# 
for i in range(len(dd)):
  re = sum(dd[i])
  remain = sum(array) - 100 # 100이 넘는 두명의 키 합을 구함
  if re == remain:
    answer =list(dd[i])
    for i in answer:
      if i in array:
        array.remove(i) # 100을 넘게 만드는 두사람을 remove를 사용하여 제거
print("\n".join(map(str,sorted(array))))

2번 문제

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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

예제 입력 1
2
5 6
0 0 1 0

예제 출력 1
30
30

import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
a,b,c,d = map(int,input().split())
#최대값, 최소값 지정하기
min_num, max_num = 1e9, -1e9
#
def solution(num, idx, add, sub, mul, div):
  global min_num, max_num #global을 통해서 최대값 최소값 가져오기
  if idx == n: #계산 회수와 계산해야 하는 숫자 갯수가 같을 때
    max_num = max(max_num,num)
    min_num = min(min_num,num)
	#재귀함수 사용
  if add >0:
    solution(num+nums[idx], idx+1, add-1, sub, mul, div)
  if sub >0:
    solution(num-nums[idx], idx+1, add, sub-1, mul, div)
  if mul>0:
    solution(num*nums[idx], idx+1, add, sub, mul-1, div)
  if div>0:
    solution(int(num/nums[idx]), idx+1, add, sub, mul, div-1)
solution(nums[0], 1, a,b,c,d)
print(max_num)
print(min_num)

3번문제

1251: 단어나누기

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

단어 : arrested
세 단어로 나누기 : ar / rest / ed
각각 뒤집기 : ra / tser / de
합치기 : ratserde
단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

예제 입력 1
mobitel

예제 출력 1
bometil

word = input().rstrip()
el = []
#총 세번 나눠야 하기 때문에 중간단어 최소길이 1, 마지막 단어 최소길이 1 총 2를 빼준다
for i in range(1, len(word)-2):
#처음 나눈 숫자 뒤부터 잘라줘야하기 때문에 i+1
  for j in range(i+1,len(word)):
    first_word = word[:i]
    second_word = word[i:j]
    last_word = word[j:]
#[::-1]을 통해서 단어들을 모두 뒤집은 후 더해준다.
    con = first_word[::-1] + second_word[::-1] + last_word[::-1]
    el.append(con)
#오름차순으로 정렬해주기
el.sort()
print(el[0])