JinWoo Kim

백문이 불여일견, 백견이 불여일행.

6 minute read

코딩테스트 연습

1. 위장

  • 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

    • 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

  • 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

입력

  • 2차원 배열 clothes가 주어집니다.

  • clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.

  • 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.

  • 같은 이름을 가진 의상은 존재하지 않습니다.

  • clothes의 모든 원소는 문자열로 이루어져 있습니다.

  • 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.

  • 스파이는 하루에 최소 한 개의 의상은 입습니다.

출력

  • 서로 다른 옷의 조합의 수를 return합니다.

풀이

def solution(clothes):
    answer = 0
    
    parts = {}
    
	# 옷의 타입에 해당하는 개수를 dict에 저장한다.
    for day_clothes in clothes:
        if day_clothes[1] not in parts:            
            parts[day_clothes[1]] = 1
        elif day_clothes[1] in parts:
            parts[day_clothes[1]] += 1
    
    # 해당 타입의 옷을 안입는 경우도 존재하므로, 각 타입에 +1한 값을 배열에 저장
    arr = [x+1 for x in parts.values()]
    
	# 배열 안의 모든 수를 곱하면 타입의 옷들로 조합할수 있는 경우의 수가 출력된다.
    answer = 1
    for num in arr:
        answer *= num
	
	#이때, 모두 안입는 경우는 존재하지 않으므로, 1을 빼준다.
    answer = answer - 1
        
            
    return answer

채점 결과

  • 정답

더 나은 풀이법

  • 출처 : https://programmers.co.kr/learn/courses/30/lessons/42578/solution_groups?language=python3

      def solution(clothes):
      from collections import Counter
      from functools import reduce
      cnt = Counter([kind for name, kind in clothes])
      answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
      return answer

    더 나은 풀이법 해석

  • from collections import Counter
    • https://docs.python.org/3/library/collections.html#collections.Counter
    • 파이썬 기본 내장 모듈인 collections에 포함되어있는 클래스이다.
    • dictionary를 확장한 구조이므로, dictionary에서 사용 가능한 api를 전부 사용할수 있다.
    • 기본적으로 iterable한 구조를 받아 개수를 리턴하는 클래스로 생각하면 편하다. 
        Counter('hello world') 
		
  실행 결과
  Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})
  • from functools import reduce

    • https://docs.python.org/3/library/functools.html#functools.reduce

    • 파이썬 기본 라이브러리인 functools에 포함되어있는 함수이다.
    • functools.reduce(function, iterable,[initializer])
    • function을 iterable의 요소에 차례대로 (왼쪽에서 오른쪽,인덱스로 0번부터) 누적 적용하여 iterable을 단일 값으로 줄여나가는 함수이다. 
        import functools

  data = [1, 2, 3, 4, 5]
  result = functools.reduce(lambda x, y: x + y, data)
  print(result)

  실행 결과
  15

  실행 과정
  ((((1+2)+3)+4)+5)
    • 함수만 lambda식으로 잘 넣어주면 응용할수 있는것이 많다. 
        # reduce로 최대값 구하기

  num_list = [3, 2, 8, 1, 6, 7]
  max_num = functools.reduce(lambda x, y: x if x > y else y, num_list)
  print(max_num)

  실행 결과
  8
  • cnt = Counter([kind for name, kind in clothes])

    • Counter 클래스 안에 list comprehension을 사용.

    • clothes에서 name(옷의 이름), kind(옷의 종류)를 받아오고, 그 중 kind만 저장하는 리스트를 생성.
    • Counter 클래스의 특성으로 인해 kind와 해당 kind가 나온 횟수가 저장된 cnt가 완성된다.
  • answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    • reduce 함수를 활용하여 cnt.values를 람다식을 이용해 단일값으로 만든다.
    • 사용된 람다식은 x * (y+1)이므로, 이전 항에 현재항+1을 곱한다.
      • 내 풀이에서 사용된것처럼, 안입은 경우의 가짓수를 추가해 kind의 개수+1을 곱해주는것을 의미한다.
    • reduce 함수의 세번째 인자는 초기값이다. 즉, 처음 실행할때 1 * (첫번째 kind의 개수+1)로 시작하는것.
    • 마지막으로, 아무것도 안입는 가짓수(안입은 경우의 가짓수가 모두 골라졌을때)의 경우를 빼서 -1 하는것으로 답을 도출한다.

2. 행운의 수

  • 한슬이는 5와 8이 행운의 수라고 생각한다. 그래서 한슬이는 각 자리가 5와 8로만 이뤄져 있는 수를 행운의 수라고 한다.

  • 정수 수열 A, B, C가 주어졌을 때 세 수열에서 각각 하나의 정수를 골라서 만들 수 있는 서로 다른 행운의 수의 개수를 구해보자.

  • 예를 들어 A = [1, 10, 100], B = [3, 53], C = [4, 54]라고 한다면, 행운의 수를 만드는 방법은 8 = 1 + 3 + 4, 58 = 1 + 3 + 54, 58 = 1 + 53 + 4와 같이 총 3가지가 있다. 58은 2가지 방법으로 만들 수 있으니, 서로 다른 행운의 수의 개수는 8과 58, 총 2개이다.

입력

  • 첫째 줄에 테스트 케이스의 수가 주어진다.

  • 각 테스트 케이스의 첫째 줄에 A의 크기 N이 주어지고, 둘째 줄에 수열 A의 원소가 주어진다. 수열 A의 원소는 공백으로 구분되어 있다.

  • 다음 셋째 줄에는 B의 크기 M, 넷째 줄에는 수열 B의 원소, 다섯째 줄에는 C의 크기 K, 여섯째 줄에는 C의 원소가 주어지며, 수열 A의 정보와 같은 형식으로 되어 있다.

  • 수열의 크기는 50을 넘지 않는 양의 정수이고, 수열의 원소는 30,000보다 작거나 같은 양의 정수이다.

출력

  • 각각의 테스트 케이스마다 입력으로 주어진 수열을 이용해 만들 수 있는 서로 다른 행운의 수의 개수를 한 줄에 하나씩 출력한다.

풀이


# your code goes here
 
import sys
from collections import Counter
 
 
# 첫째 줄에 테스트 케이스의 수가 주어진다.
TestCase = int(sys.stdin.readline())
 
for _ in range(0,TestCase):
	# 각 테스트 케이스의 첫째 줄에 A의 크기 N이 주어지고, 둘째 줄에 수열 A의 원소가 주어진다. 
	# 수열 A의 원소는 공백으로 구분되어 있다.
	N = int(sys.stdin.readline())
	A = list(map(int,sys.stdin.readline().split()))
 
	# 다음 셋째 줄에는 B의 크기 M, 넷째 줄에는 수열 B의 원소, 
	M = int(sys.stdin.readline())
	B = list(map(int,sys.stdin.readline().split()))
 
	# 다섯째 줄에는 C의 크기 K, 여섯째 줄에는 C의 원소가 주어지며, 수열 A의 정보와 같은 형식으로 되어 있다.
	K = int(sys.stdin.readline())
	C = list(map(int,sys.stdin.readline().split()))
 
	# 세 수열에서 각자 하나의 정수를 뽑아 더했을때 만들수 있는 행운의 수를 고르는 과제이다.
	# 행운의 수란, 각 자리수가 5와 8로만 이루어져있는 수를 의미한다.
 
	# 예제 입력 1로 알수 있는것은, 중복된 숫자는 하나로 취급한다.
	# 예제 입력 1로 알수 있는것 두번째는, 중복된 행운의 수 역시 하나로 취급한다.
	
	cnt_a = list(Counter(A).keys())
	cnt_b = list(Counter(B).keys())
	cnt_c = list(Counter(C).keys())
 
	answer = []
	
	for i in range(0,len(cnt_a)):
		for j in range(0,len(cnt_b)):
			for k in range(0,len(cnt_c)):
				sum = str(cnt_a[i] + cnt_b[j] + cnt_c[k])
				for p in range(0,len(sum)):
					if (sum[p] != '5') and (sum[p] != '8'):
						break
					if (p == len(sum)-1) and ((sum[p] == '5') or (sum[p]=='8')):
						answer.append(sum)
	
	cnt_answer = list(Counter(answer).keys())
	
	print(len(cnt_answer))

채점 결과

  • 정답

    더 나은 풀이법

더 나은 풀이법 해석

3. 스텔라(STELLA)가 치킨을 선물했어요

  • 스텔라는 대회의 5등과 푼 문제 수는 같지만 패널티 차이로 수상하지 못한 학생들에게만 치킨 기프티콘을 보내주고자 한다.

  • 각 참가자는 해결한 문제 개수와 패널티 총합을 가진다.
  • 해결한 문제의 개수가 더 많은 참가자가 더 높은 순위를 가진다.
  • 해결한 문제의 수가 같을 때, 패널티 총합이 더 작은 참가자가 더 높은 순위를 가진다.

입력

  • 첫 줄에 참가자의 수 N(5 ≤ N ≤ 66)이 주어진다.
  • 이후 N개의 줄에 걸쳐 각 참가자가 해결한 문제 개수와 패널티 총합이 주어진다.
  • 각 참가자가 해결한 문제의 개수는 8개보다 작거나 같은 음이 아닌 정수이며 패널티 총합은 100,000보다 작거나 같은 음이 아닌 정수이다.
  • 5등 학생은 적어도 한 문제 이상을 해결하였음이 보장되며, 한 문제 이상을 푼 학생 중 문제 수와 패널티가 모두 같은 학생은 존재하지 않는다.

출력

  • 한 줄에 5등과 해결한 문제 개수가 같지만 수상하지 못하는 학생의 수를 출력한다.

풀이


# your code goes here
 
import sys
from collections import Counter
 
# 첫 줄에 참가자의 수 N(5 ≤ N ≤ 66)이 주어진다. 
N = int(sys.stdin.readline())
 
solve_arr = []
penalty_arr = []
 
# 이후 N개의 줄에 걸쳐 각 참가자가 해결한 문제 개수와 패널티 총합이 주어진다.
for i in range(0,N):
	solve, penalty = list(map(int,sys.stdin.readline().split()))
	solve_arr.append(solve)
	penalty_arr.append(penalty)
 
	if i > 0:
		# 맞춘문제가 많은순으로 패널티와 맞춘문제를 정렬
		for j in range(0,len(solve_arr)-1):
			if solve_arr[i] > solve_arr[j]:
				tmp1 = solve_arr[i]
				tmp2 = penalty_arr[i]
				solve_arr[i] = solve_arr[j]
				penalty_arr[i] = penalty_arr[j]
				solve_arr[j] = tmp1
				penalty_arr[j] = tmp2
			# 만약 맞춘 개수가 같다면, 패널티가 적은 순서로 정렬
			elif solve_arr[i] == solve_arr[j]:
				if penalty_arr[i] < penalty_arr[j]:
					tmp1 = solve_arr[i]
					tmp2 = penalty_arr[i]
					solve_arr[i] = solve_arr[j]
					penalty_arr[i] = penalty_arr[j]
					solve_arr[j] = tmp1
					penalty_arr[j] = tmp2
 
 
# 5등과 같은 문제를 풀었지만, 패널티 차이로 밀려난 인원의 수
cnt = 0
 
# 5명 이상이 시험에 참가했다면, 5등 아래의 인원이 나오므로 해당 반복문 실행.
# 5등은 적어도 1문제 이상 풀었음.
if len(solve_arr) > 5 and solve_arr[4] > 0:
	# 5등 아래 순위를 탐색
	for i in range(5,len(solve_arr)):
		# 5등과 푼 문제가 같다면, cnt를 증가
		if solve_arr[i] == solve_arr[4]:
			cnt += 1
		elif solve_arr[i] != solve_arr[4]:
			break
 
 
print(cnt)

채점 결과

  • 정답

더 나은 풀이법

더 나은 풀이법 해석

You May Also Enjoy