Archive

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 DFS문제. 처음 시작노드 -> 방문안한노드를 방문 -> 방문한 노드를 마주치면 while문 밖으로 처음 시작노드 = 최종 도착노드일 경우(cycle) count 변수 +1해줌. def solution(): n = int(input()) lst = [0] + list(map(int, input().split())) cnt = 0 vi..

https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀� programmers.co.kr 풀이 특정 단어 word, html 소스로 구성된 pages를 입력으로 받음. 각 page별로 word에 대한 점수를 부여해야 하는데 다음 과정으로 구함. 본문(body tag)에서 word의 개수를 기본 점수로 정함. 본문은 알파벳을 제외한 다른 문자로 구별가능하고, 대소문자 상관 없이 word와 딱 맞아야함. word = 'abc', body에 'abcd',..

https://www.hackerrank.com/challenges/candies/problem Candies | HackerRank Help Alice to save money by minimizing the total number of candies. www.hackerrank.com 풀이 2번 iteration을 사용. 오른쪽으로 iteration돌 때는 오름차순일 때 dp 값을 채워줌. 왼쪽으로 iteration돌 때는 내림차순일 때 dp값을 채워줌. def candies(n, arr): n = len(arr) # 최소값은 1로 문제에서 주어짐. dp = [1] * n for i in range(1, n): # 다음 원소가 더 크면 dp값을 증가해줌. if arr[i-1] < arr[i]: dp[..

https://www.hackerrank.com/challenges/reverse-shuffle-merge/problem Reverse Shuffle Merge | HackerRank Given a string, find the lexicographically smallest substring that satisfies the given conditions. www.hackerrank.com 풀이 입력으로 문자열 s를 받을 때 아래 조건을 만족하는 알파벳 순으로 가장 앞선 문자열 A를 찾는 문제 s \in merge( reverse(A) , shuffle(A) ) merge 연산은 파라미터로 두 개의 string을 받는데, 각 string의 입력 순서만 맞으면 됨. merge( 'abac', 'bcbc'..

https://www.hackerrank.com/challenges/special-palindrome-again/problem Special String Again | HackerRank Find Special sub-strings in a string. www.hackerrank.com 풀이 입력으로 문자열 길이, string이 주어졌을 때, 다음 조건에 만족하는 substring 개수를 구하는 문제 substring에 포함된 모든 문자가 같은 경우. ex) aaa substring의 가운데 하나를 제외한 양 옆의 모든 문자가 같은 경우. ex) aadaa ex) s = mnonopoo special substrings = {m, n, o, n, o, p, o, o, non, ono, opo, oo} ..

https://www.hackerrank.com/challenges/ctci-merge-sort/problem Merge Sort: Counting Inversions | HackerRank How many shifts will it take to Merge Sort an array? www.hackerrank.com 풀이 예제처럼 bubble sort로 구현하면 timeout 발생 merge sort로 구현해도 timeout 발생함 merge 부분에서 list의 append함수를 지역 변수로 사용하는게 빠름. 필요한 정보들( len(list) 등)을 미리 변수에 할당하고 사용하는게 빠름. 가운데 index를 계산해 둘 씩 나누다가, 합칠 때 inversion 경우를 count함. i < j 일 때, a..