greentea31's Note

https://programmers.co.kr/learn/courses/30/lessons/12926

풀이 과정

ord()로 문자의 아스키 코드를 감지할 수 있고, chr()로 아스키코드를 문자로 바꿀 수 있다.

A-Z의 문자는 아스키 코드로 65-90에 대응되고, a-z는 97-122에 대응됨을 이용하여 아스키 코드가 90, 122를 넘어가면 26을 빼줘서 처음으로 돌아가게끔 해주었다. n이 큰 수가 들어오는 조건이였다면 나머지 연산으로 문제를 해결해야 했겠지만 25까지 들어오기 때문에 그냥 범위를 넘어갈시 25를 빼주는 방법으로 문제를 해결할 수 있다.

소스 코드

def solution(s, n):
    answer = ''
    for letter in s:
        if letter == ' ':
            answer += ' '
            continue
        temp = ord(letter) + n
        if 'A' <= letter <= 'Z':  # letter.isupper()로도 판단 가능
            if temp > 90:
                temp -= 26
        else:  # letter.islower()로도 판단 가능
            if temp > 122:
                temp -= 26
        answer += chr(temp)

    return answer

https://programmers.co.kr/learn/courses/30/lessons/42577

풀이 과정

1. 정렬해서 풀기

처음 풀었을 때는 phone_book.sort(key=lambda x: len(x)) 방법으로 길이순으로 정렬하고 string.find() 명령어를 이용해서 풀었다. len(phone_book)이 4라고 한다면 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)의 순서쌍에 대해 뒤의 인덱스가 앞의 인덱스의 문자열을 포함하고 있는지를 살펴봤으나 이렇게 풀면 문제를 잘못 읽은 것이다. 특정 전화번호가 다른 전화번호를 포함하고 있는지를 묻지 않았고 다른 전화번호로 시작했는지를 물어봤으니 다른 전화번호를 문자열 중간에 포함하고 있는 경우에 잘못된 답을 출력하게 된다.

그리고 위와 같은 순서쌍을 만들어서 비교하는 방법은 2중 for문을 돌려야 하는데 시간복잡도 문제때문에 효율성 테스트 3, 4번을 통과할 수 없다. 예전에는 효율성 테스트 3, 4번 케이스가 없었으므로 2중 for문으로 해결한 코드도 좀 보이는 것 같은데 지금은 for문을 2번 사용해서는 효율성 테스트에서 통과할 수가 없다.

파이썬에서 문자열에 대해 sort()를 사용하면 첫번째 문자에 대해 정렬, 첫번째 문자가 같다면 두번째 문자에 대해 정렬... 순으로 이루어진다 아래 예시를 보자

a = ['567', '88', '123', '1235', '12']

a.sort()

a = ['12', '123', '1235', '567', '88']

예시를 보면 이미 한번 정렬을 했으면 for문을 2번 돌릴 필요가 없다는 것을 알게 된다. 그냥 뒤의 문자열이 앞의 문자열로 시작하는지만 체크해주면 모든 문자열의 접두어 시작 여부를 알 수가 있게 된다.

2. 해쉬로 풀기

모든 전화번호를 딕셔너리에 넣은 후, 각 전화번호의 처음부터 일정 부분까지의 부분 문자열을 딕셔너리의 키 값으로 주고 딕셔너리를 조회하면서 각 전화번호의 부분 문자열이 다른 전화번호와 같은지 확인하면서 푸는 방법이 있다.

부분 문자열은 문자열과 같아서는 안된다. 그러면 부분 문자열이 문자열과 같아지면 딕셔너리에 항상 존재하게 되고, 한 번호가 다른 번호의 접두어인 경우가 아니더라도 접두어가 존재한다고 판단하게 된다.

만약에 처음부터 일정 부분까지의 부분 문자열이 다른 전화번호와 동일하다면 다른 전화번호가 문자열의 접두사가 된다.

소스 코드

1번

def solution(phone_book):
    answer = True
    phone_book.sort()
    length = len(phone_book)
    for i in range(length-1):
        if len(phone_book[i+1]) >= len(phone_book[i]) and phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
            answer = False
            break
    return answer

2번

def solution(phone_book):
    answer = True
    phone_hash = {}
    
    for address in phone_book:
        phone_hash[address] = 1
    
    for address in phone_book:
        temp = ""
        if not answer:
            break
        for number in address:
            temp += number
            if temp in phone_hash and temp != address:
                answer = False
                break
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12921

풀이 과정

일정 범위에 있는 모든 소수를 찾아야 하는 문제이다. 1부터 n까지의 수에 대해 모두 소수 판정을 하면서 개수를 세면 답이야 구해지겠지만 시간복잡도가 O(NrootN)인 방법이 되어 효율성 테스트를 통과할 수가 없다.

일정 범위에 있는 모든 소수를 찾아야 할 때는 에라토스테네스의 체를 사용하는게 효과적이다. 에라토스테네스의 체가 무엇인지 모르면 아래 위키백과를 참조하면 좋다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체의 시간복잡도는 O(NloglogN)으로 더 효율적이다 N이 100만이라 할때 일일이 소수 판정을 하면 연산 횟수가 약 10억번 언저리까지 나올 수 있지만 에라토스테네스의 체로는 2천만번 언저리의 연산으로 해결이 가능하다.

소스 코드

def solution(n):
    answer = 0
    check = [False for _ in range(1000001)]
    prime = [] 

    for i in range(2, 1000001):
        if not check[i]:
            prime.append(i)
            for j in range(2*i, 1000001, i):
                check[j] = True

    for prime_number in prime:
        if prime_number > n:
            break
        else:
            answer += 1

    return answer

https://programmers.co.kr/learn/courses/30/lessons/12919

풀이 과정

리스트에서 Kim을 찾고 Kim의 index가 어디있는지 문자열에 담아 출력해주면 되는 문제이다.

파이썬에서 index 함수를 사용하면 리스트에서 찾는 값이 몇 번째 index에 있는지 찾을수 있다.

예시)

seoul = [1, 'hello', b]

seoul.index('hello') = 1

index 함수를 활용하여 문제를 해결하였다.

소스 코드

def solution(seoul):
    return f"김서방은 {seoul.index('Kim')}에 있다"

https://programmers.co.kr/learn/courses/30/lessons/12918

풀이 과정

isdigit()으로 문자열이 숫자만으로 구성되어 있는지 확인할 수 있고, len()으로 특정 객체의 길이를 판별할 수 있다.

소스 코드

def solution(s):
    return len(s) in (4, 6) and s.isdigit()

https://programmers.co.kr/learn/courses/30/lessons/12917

풀이 과정

파이썬 내장함수를 사용해 문자열을 내림차순으로 배치해주면 문제의 모든 조건을 만족하게 된다.

문자열에서 바로 sort 사용은 불가능하니 문자열을 리스트로 바꾸고 sort를 사용한 다음에 다시 문자열로 바꿔주었다.

소스 코드

def solution(s):
    answer = list(s)
    answer.sort(reverse=True)
    answer = ''.join(answer)
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12916

풀이 과정

1. 문자열 s의 문자를 하나 하나 들여다 보면서 p, P를 인식시 p의 개수를 늘리고, y, Y를 인식시 y의 개수를 늘리면서 카운팅하는 것이 정석적인 풀이 방법이다.

파이썬 내장 함수를 좀 더 간결하게 해결할 수 있다.

2. lower()를 이용해 대문자를 전부 다 소문자로 바꾸고 count()로 p와 y의 개수를 세주고 같은지 체크해주면 된다

소스 코드

첫번째 방법

def solution(s):\
    count_p = 0
    count_y = 0
    for letter in s:
        if letter in ('p', 'P'):
            count_p += 1
        if letter in ('y', 'Y'):
            count_y += 1

    return count_p == count_y

두번째 방법

def solution(s):
    return s.lower().count('p') == s.lower().count('y')

https://programmers.co.kr/learn/courses/30/lessons/12915

풀이 과정

파이썬의 lambda식을 이용해서 정렬하여 문제를 해결하였다.

list.sort(key=lambda x:x[n])식은 list의 n번째 인덱스로 리스트를 정렬해준다.

인덱스 n의 문자열이 같은 원소가 여럿일 경우, 사전순으로 배치해야 하므로 먼저 list.sort()로 사전순으로 정렬하고 인덱스 정렬을 시행하였다.

소스 코드

def solution(strings, n):
    strings.sort()
    strings.sort(key=lambda x:x[n])
    answer = strings
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12912

풀이 과정

a, b를 보고 a가 b보다 크면 두 수를 서로 바꿔준 다음에 a ~ b까지의 누적 합을 구했다.

소스 코드

def solution(a, b):
    answer = 0
    if a > b:
        a, b = b, a
    answer = sum(range(a, b+1))
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12910

풀이 과정

중복이 없는 리스트가 들어왔을때 리스트 내의 원소중 divisor로 나누어 떨어지는 것들의 집합을 오름차순으로 반환해주면 된다. 단 나누어 떨어지는게 없으면 리스트에 -1을 담아 반환해야 한다.

그냥 문제가 시키는 대로 구현하면 된다. 리스트 내포와 삼항 연산자 문법을 사용하면 코드를 더욱 간략하게 구현할 수 있다.

소스 코드

def solution(arr, divisor):
    answer = [x for x in arr if x % divisor == 0]  # 리스트 내포
    answer.sort()
    return answer if answer else [-1]  # 삼항 연산자