파이썬 자료구조 알고리즘, programmers 코딩 기초 트레이닝

 

Queue 

First In First Out 자료구조라고 해서 FIFO 라고 부른다. 선입선출이라고 이해하면 된다. 놀이기구 줄 처럼 처음에 줄 선 사람이 가장 빨리 타고 마지막에 줄 선 사람이 가장 늦게 타는 구조라고 생각하면 쉽다.

 

그럼 큐를 활용한 예제 문제를 풀어보자.

근데 문제를 풀기 전에 deque를 알아야 한다.

 

deque는 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 양쪽 끝에서 빠르게 삽입과 삭제를 할 수 있는 자료 구조를 뜻한다. list와 비슷하지만 성능면에서 훨씬 높은 효율성을 가진다.

 

deque 사용법

from collections import deque

# deque 생성
deq = deque()

# 요소 추가
deq.append       # 오른쪽 끝에 추가
deq.appendleft   # 왼쪽 끝에 추가

# 요소 제거
right = deq.pop()     # 오른쪽 끝에서 제거
left = deq.popleft()  # 왼쪽 끝에서 제거

# 유요한 메소드
append(x): x를 오른쪽 끝에 추가
appendleft(x): x를 왼쪽 끝에 추가
pop(): 오른쪽 끝의 요소를 제거하고 반환
popleft(): 왼쪽 끝의 요소를 제거하고 반환
extend(iterable): iterable의 모든 요소를 오른쪽 끝에 추가
extendleft(iterable): iterable의 모든 요소를 왼쪽 끝에 추가 주의: iterable의 순서가 반대로 추가됨
rotate(n): 덱을 오른쪽으로 n번 회전합니다. n이 음수면 왼쪽으로 회전
reverse(): 덱의 모든 요소의 순서를 뒤집는다
clear(): 모든 요소를 제거

 

 

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

 

일단 맨 위를 맨 왼쪽으로 생각하고 제일 아래를 맨 오른쪽으로 생각한다.

 

1. N카드면 N개의 숫자카드를 의미하니까 deq에 들어가는 수의 범위는 range(1, N+1)이 되고, deq는 [1, 2, ... N ]이 된다.

2. 그럼 일단 for문 돌려서 카드 deq를 만들어준다.

3. N이 클수록 반복 횟수가 많아지고, 무조건 마지막 한장이 남을 때까지 반복해야 한다. 즉, 반복횟수를 미리 알 수 없고 조건에 맞춰 반복을 종료하므로 while반복문, while의 조건은 데크의 길이가 1보다 크면 계속 반복하는거니까 while len(deq) > 1 이 된다.

4. 맨 앞에 숫자 버릴거니까 deq.popleft() 쓰고..

5. 그 다음은, 제거한 왼쪽 끝 숫자를 오른쪽 끝에 추가한다. deq.append.(dq.popleft())

6. 왼쪽 끝 숫자카드를 제거한 데크를 반환해야하니까 return deq.popleft()

 

from collections import deque

def last_card_deq(num):
    card_numbers = list(i for i in range(1, num + 1))
    deq = deque(card_numbers)

    while len(deq) > 1:  # 카드 한장 남을 때까지 반복
        deq.popleft()    # 맨 위(맨 왼쪽) 카드 제거
        deq.append(deq.popleft())  # 맨 위(맨 왼쪽) 카드를 맨 오른쪽으로 이동
        
    return deq.popleft() # 마지막 남은 카드 반환

print(last_card_deq(4))
print(last_card_deq(5))
print(last_card_deq(6))
print(last_card_deq(7))

 

 deq가 리스트와 동일한 개념이니까.. 그냥 맨 위 range(1, num+1)을 deque애 넣어서 코드를 줄여보면..

def last_card_deq(num):
    deq = deque(range(1, num + 1)) # 1부터 n까지의 카드를 데크에 바로 넣어어서 리스트화 한다.

    while len(deq) > 1:  # 카드 한장 남을 때까지 반복
        deq.popleft()    # 맨 위(맨 왼쪽) 카드 제거
        deq.append(deq.popleft())  # 맨 위(맨 왼쪽) 카드를 맨 오른쪽으로 이동
        
    return deq.popleft() # 마지막 남은 카드 반환
    
print(last_card_deq(4))
print(last_card_deq(5))
print(last_card_deq(6))
print(last_card_deq(7))

 

조금 더 간결하게 만들 수 있다. (출력 시 값↓)

4
2
4
6

 

 

이제 스택 괄호문제 풀어야하는데... 휴.. 사랑니같은.. 괄호문제... 빨리 풀어서 없애고 싶다ㅠㅠ

---

codekata 19번 - 23번

 

 

Q19. 정수 제곱근 판별

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.

n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

 

def solution(n):
    x = int(n ** 0.5) # 변수 x를 정의하는 동시에 n의 제곱근의 정수부분을 구함 
    if n == x ** 2: 
        return (x+1)**2
    else:
        return -1

 

처음엔 x = int(n ** 0.5) 이걸 안 해줘서 오류가 났다. 

 

제곱근(sqrt)을 구하는 구하는 방법에는 두가지가 있다. n의 제곱근을 구한다고 했을 때

1. n ** 0.5

2. math.sqrt(n)

 

두번째 방법은 math 모듈을 import해서 사용해야 한다.

import math

n = 16
n_sqrt = int(math.sqrt(n))
print(n_sqrt)

 

해보면

4

---

Q20. 정수 내림차순으로 배치하기

 

1. 일단 n을 map으로 하나하나 똑똑 떼어내서 int로 바꿔주고, 리스트 n_list 에 넣어줬다.

2. 내림차순으로 정렬

3. 다시 리스트에 있던거 map으로 똑똑 문자열로 떼어내고 (join이 문자열로 구성된 시퀀스만 결합주기 때문에 문자열로 떼어냄)

4. ('') 공백없이 join으로 합쳐주고, 이거 전체를 int로 바꿔주면 끝!

 

def solution(n):
    n_list = list((map(int, str(n))))
    reversed_list = sorted(n_list, reverse=True)
    reversed_list_to_int = int(''.join(map(str, reversed_list))) # join은 문자열로 구성된 것만 결합
    return reversed_list_to_int

print(*map(int, str(132)))
print(solution(132))

 

출력해보면 잘 나온다.

1 3 2
321

 

programmers도 통과

---

Q21. 하샤드 수

# 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다.

# 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다.

# 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.

 

def is_harshad(x):
    sum_digit = sum(int(digit) for digit in str(x))
    return x % sum_digit == 0

print(is_harshad(1729))
print(is_harshad(123))

 

x가 하샤드 수인지 검사만 하면 되니까, x를 x의 자릿수의 합으로 나눴을 때 나머지가 0이면 된다.

그럼 각 자릿수의 합만 구하면 되는데, x를 문자열로 바꿔서 for문으로 각 자릿수를 가져오고 다시 int로 바꿔서 더해주면 된다.

 

출력해보면 해당 숫자가 하샤드 수인지 아닌지 판별된다.

True
False

---

Q22. 두 정수 사이의 합

두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수(예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴, a = 3, b = 3 이면 3리턴, a = 3, b = 1이면 3+2+1 = 6이므로 6 리턴 )

 

a < b 일 때, a > b 일 때를 나눠서 생각했다. 

a가 b보다 작으면 a부터 b까지 범위를 두고 a부터 1씩 더해주면 되고, b가 a보다 작으면 b부터 a까지 범위를 두고 b부터 1씩 더해주면 된다.

나머지 경우인 a 와 b가 같으면, a나 b 둘 중 아무거나 하나를 반환하면 된다.

def solution(a, b):
    if a < b:
        return sum(int(i) for i in range(a, b+1))
    if a > b:
        return sum(int(i) for i in range(b, a+1))
    else:
        return a

print(solution(3, 5))
print(solution(4, 2))

 

출력해보면 3+4+5 =12 / 4+3+2 =9 잘 나온다.

12
9

---

 

Q23. 콜라츠 추측 (주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측)

 

  1-1. 입력된 수가 짝수라면 2로 나눕니다.

  1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.

  2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

(예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 된다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성하시오. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환.)

 

1. 단, 주어진 수가 1인 경우에는 0 이라는 조건이 붙었으므로 먼저 if문으로

 

if num == 1 :

        return 0 조건을 달아주고.

 

1이 될 때까지 계속 반복해야하고 몇 번을 반복해야 종료될 지 모르므로 while 반복문을 쓰면 된다.

 

2. 우리가 구해야하는건 몇번을 돌려야 1이 나오는지를 구하는거니까 일단 count = 0 을 주고

3. while문을 돌려서 (num이 1이 아니면 계속 반복. 즉, num이 1이 되면 반복 종료) 짝수일때 2로 나눈 몫을, 홀수일 때 3을 곱한 후 1을 더한 값을 계산하도록 계속 반복하고, 반복할때마다 count를 1씩 더해준다.

4. 만약 반복문을 도는 중에 count가 500번째에 도달하면 그냥 -1을 반환하면 된다.  

5. num이 1이 되면, while문을 빠져나오고 count값을 반환한다.

 

def solution(num):
    if num == 1:
        return 0

    count = 0
    while num != 1: # num이 1이 아니면 계속 반복문 돌리기
        if num % 2 == 0:
            num = num // 2
        elif num % 2 != 0:
            num = num*3 + 1

        count += 1

        if count == 500:
            return -1

    return count

---

 

Q24. 서울에서 김서방 찾기

String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.

 

입출력 예

seoul	return
["Jane", "Kim"]	"김서방은 1에 있다"

 

복잡하게 생각했는데 입출력 예를 보니 seoul 리스트의 요소 중 Kim의 index값을 구하면 되는 거였다.

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

seoul = ["Kim", "Lee", "Jane"]
solution(seoul)

 

x를 seoul.index("Kim")으로,

return값을 "김서방은 x에 있다"를 출력해주도록 하면 된다.

 

근데 틀렸다.... 문제에서 단지 "김서방은 x에 있다"는 str값을 반환하라고만 했지 출력하라고는 안했기 때문이다..

 

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

 

이렇게 하면 정답이 된다. 사고도 문제를 읽는 것도 잘게 쪼개서 정확하게 하기로..