PS 162

18352번 - 특정 거리의 도시 찾기

문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (..

PS/백준 2022.07.15

소수 찾기 (lv2)

처음엔 에라토스테네스의 체로 소수 집합을 만들어 풀었는데, 정석으로 다시 풀었다. 전자보다 후자가 시간, 용량면에서 우세하다. 코드 에라토스테네스의 체 from itertools import permutations def solution(numbers): answer = 0 primeNumbers = eratosthenes(int(''.join(sorted(numbers, reverse=True)))) s = set() for i in range(1,len(numbers)+1): s = s | set(map(lambda x : int(''.join(x)), permutations(numbers,i))) for v in s: if v in primeNumbers: answer += 1 return answ..

조이스틱 (lv2)

문제 설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조..

최대공약수와 최소공배수 (lv1)

파이썬 3.9 이상 버전에서는 math 모듈의 gcd, lcm 메서드를 사용가능하다. [Python] 최소공배수, 최대공약수란? 파이썬 알고리즘으로 쉽게 구현하기 / for문, 유클리드 호제법 이용 (tistory.com) [Python] 최소공배수, 최대공약수란? 파이썬 알고리즘으로 쉽게 구현하기 / for문, 유클리드 호제법 최대공약수란 ? GCD (Greatest Common Divisor) Common Divisor -> 라는 이름에서 알 수 있듯이 두 수 혹은 그 이상의 여러 수의 공통인 약수 중, 최대인 것. 즉, 수들의 각각의 약수 중 공통이며 가장 큰 수를.. codingpractices.tistory.com 코드 def solution(n, m): gcd = 0 x, y = n, m wh..

수박수박수박수박수박수? (lv1)

문제 설명 길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다. 제한 조건 n은 길이 10,000이하인 자연수입니다. 코드 def solution(n): watermelon = ''.join(['수박'] * (n//2)) last = '' if n % 2 == 0 else '수' return watermelon + last 나름 간결하게 짰다고 생각했으나... def water_melon(n): s = "수박" * n return s[:n] 문자열도 저렇게 곱셈 연산을 적용할 수 있는지 몰랐다. 그 외에는... 글쎄 내가 짠 코드보다 우위에 있는지는 잘 모..

소수 찾기 (lv1)

지금까지 소수를 찾는 문제는 제곱근까지 나눠보는 방법을 사용했다. 그러나 에라토스테네스의 체 라는 약 10배정도 빠른 알고리즘이 존재한다는 사실을 알아냈다. 에라토스테네스의 체 - 나무위키 (namu.wiki) 에라토스테네스의 체 - 나무위키 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른[2] 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자. 일단 1부터 100까지 숫자를 쭉 쓴다. 1234567891011121314151617181920212223 namu.wiki 코드 my def solution(n): answer = 0 for v in range(2,n+1): for divisor in range(2, int(v**0.5)+1): if v % divisor =..

문자열 다루기 기본 (lv1)

문제 설명 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 이상, 길이 8 이하인 문자열입니다. 코드 def alpha_string46(s): return s.isdigit() and len(s) in (4, 6) isdigit이라는 메서드의 존재, 그리고 뒷부분인 len(s) in (4, 6) 모두 생각 못한 풀이이다. 숫자인지 확인할 때는 isdigit, 그리고 in 을 활용한 기법 모두 기억해두자...

문자열 내 p와 y의 개수 (lv1)

문제 설명 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다. 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. 제한사항 문자열 s의 길이 : 50 이하의 자연수 문자열 s는 알파벳으로만 이루어져 있습니다. 코드 def numPY(s): # 함수를 완성하세요 return s.lower().count('p') == s.lower().count('y') 난 Counter로 각 알파벳의 개수를 ..

같은 숫자는 싫어 (lv1)

문제 설명 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요. 제한사항 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 ..

[1차] 다트 게임 (lv1)

문제 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 ..