Jang's coding blog

[LV2]전화번호 목록 문제링크 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. www.programmer.co.kr 문제해설 이번 문제는 리스트를 통해서 모든 탐색을 하면 정확성을 만점을 받을 수 있지만 효율성에서 시간초과가 나오게 된다. 그렇기 때문에 해시(hash) 알고리즘을 사용해야하는데 파이썬은 딕셔너리가 이 역할을 한다. def solution(phone_book): answer = True hash={}#딕셔너리 선언 for i in phone_book: #모든 전화번호를 (전화번호:0) 으로 설정 hash[i]=0 for i in phone_book: tmp='..

[LV2]조이스틱 문제링크 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 www.programmer.co.kr 문제 해설 우선 전체 알파벳의 중간지점을 기준으로 현재 문자부터 'A' 까지 걸리는 거리의 최소값을 answer에 더함으로써 상하의 이동값을 계산한다. 좌우에서 최소한의 이동을 가지려면 'A'가 연속적으로 있는곳으로는 갈 필요가 없고 만약 연속된 'A'가 여러곳에 있다면 연속된 길이가 긴 곳보다 짧은곳을 가는것이 이득이다. 연속된 A의 왼쪽으로 가는 방법과 오른쪽으로 가는 방법과 기본 움직임 중에서 최소값을 구한다. def solution(name): answe..

[LV2]타겟 넘버 문제 링크 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. www.programmers.co.kr 문제해설 이 문제는 기본적으로 숫자의 개수가 2~20개이기 때문에 모든 경우를 탐색해도 시간초과가 일어나지 않는다. 그렇기 때문에 앞에서부터 연산한 숫자들을 모두 리스트에 넣은 후 COUNT함수를 사용하여 target과 동일한 숫자가 몇개인지 찾으면 되는 문제이다. def solution(numbers, target): start=[0] #초기값 for i in numbers: #앞에서부터 연산 num=[] for j in start: #앞서 연산되어있던 숫자들에 각각 +,-연산을 실행하여 다시 리스트에 저장 num..

[LV2]짝지어 제거하기 링크 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. www.programmers.co.kr 문제해설 이 문제는 반복문을 사용하여 각각의 문자를 스택에 집어넣어 비교하여 서로 같은 문자이면 제거하여 최종적으로 스택에 문자가 남아있으면 0을반환 그렇지 않으면 1을 반환하면 되는 문제이다. 이 문제에서 길이가 홀수인 문자는 항상 스택에 문자가 남을 수 밖에 없으므로 0을 반환하게 처리하였다. def solution(s): stack=[] #스택 for i in range(len(s)): #문자열의 길이만큼 반복 if len(s)%2==..

# 백준 2012번 등수매기기 문제 링크 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. www.acmicpc.net 문제해설 이 문제는 그리드 문제이며 간단하게 생각해보면 기대등수를 오름차순으로 정리하여 실제 등수를 배정하게 되면 불만도의 합은 최소가 되게된다. 입력값이 커지게 되면 시간초과가 발생함으로 sys.stdin.readline을 사용하여 시간을 줄여주는것이 필요하다. import sys input=sys.stdin.readline #시간초과 방지 n=int(input()) rank=[] #각..

# 백준 1543번 문제검색 링크 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문제해설 이번 문제에서는 입력받는 값이 항상 영어이므로 비교하는값도 영어라는점을 이용하여 replace함수를 사용하여 겹치는 부분을 '0'으로 바꾸는 반복문을 사용하여 총 몇번 바꾸는지 출력하는 코드를 만들었다. sen=input() #전체 문자열 입력받기 tmp=input() #찾을 문자열 입력받기 cnt=0 while True: #전체 문자열에 찾을 문자열이 없을때까지 비교 if tmp not in sen: break sen=sen.replace(tmp..