문제 https://school.programmers.co.kr/learn/courses/30/lessons/42577 My Solution Idea. any, startswith 이용 def solution(phone_book): ''' string 에서 subset 확인 ''' for phone in phone_book: if any(other_phone.startswith(phone) for other_phone in phone_book if other_phone != phone): return False return True 다른 전화부를 비교하는데 오버헤드 발생 Other’s Solution https://school.programmers.co.kr/learn/courses/30/lessons/..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42576 My Solution Idea 1. remove 사용 def solution(participant, completion): for person in completion: participant.remove(person) return participant[0] list의 remove()는 시간 복잡도가 O(1) ~ O(N) ⇒ 효율성 테스트 통과 불가 Idea 2. dict, counter 사용 from collections import Counter def solution(participant, completion): dict_participant = dict(Counter(partici..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 H-Index( 과학자의 생산성과 영향력을 나타내는 지표)를 구하는 문제 H-Index : 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 Solution 중요 Idea 아무리 인용수(citations) 값이 크더라도 논문 편수가 작으면 H-index 는 작을 수 밖에 없다. ex. [312,521,1021] ⇒ H-index = 3 코드 1 def solution(citations): citations.sort(reverse=True) for h, citation in enumerate(citations, ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42746 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. My Solution (Time Out) Idea1 : Permutation 이용 모든 순열에 대해 시도 ⇒ Time Out from..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 11399번 - ATM : https://www.acmicpc.net/problem/11399 [백준] 1931번 - 회의실 배정 : https://www.acmicpc.net/problem/1931 1931번 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 13305번 - 주유소: https://www.acmicpc.net/problem/13305 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1541번 - 잃어버린 괄호: https://www.acmicpc.net/problem/1541 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 11729번 - 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1436번 - 영화감독 숌 : https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1018번 - 체스판 다시 칠하기 : https://www.acmicpc.net/problem/1018 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 7568번 - 덩치 : https://www.acmicpc.net/problem/7568 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 2231번 - 분해합 : https://www.acmicpc.net/problem/2231 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로..