[240510] 코딩테스트 문제풀이

1. 2개 이하로 다른 비트

• 짝수일 때 : 가장 뒷쪽에 있는 0 숫자를 1로 바꿔줌
• 홀수일때 :  가장 뒷쪽에 있는 0 숫자를 1로 바꿔줌 -> 그런 다음, idx + 1 의 

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

def solution(numbers):
    answer = []

    for number in numbers :
        bin_number = list('0' + bin(number)[2:])  #bin함수를 사용해서 이진수 형태로 
        idx = ''.join(bin_number).rfind('0') # rfind 함수 사용 -> 가장 뒤에 0이라는 값이 몇 번째 인덱스 ? 
        bin_number[idx] = '1'

        if number % 2 == 1 :
            bin_number[idx + 1] = '0'

        answer.append(int(''.join(bin_number),2)) #다시 10진수 형태로 바꿔줌

    return answer

 

---

2. 좋은단어

https://www.acmicpc.net/problem/3986

n = int(input())
count = 0

for k in range(n) :
    word = list(input())
    stack = []
    for i in word :
        if len(stack) == 0 :
            stack.append(i)
        elif stack[-1] == i :
            stack.pop()
        else :
            stack.append(i)
    if len(stack) == 0 :
        count += 1

print(count)

 

---

3.  균형잡힌 세상

https://www.acmicpc.net/problem/4949

while True :
    word = input()
    stack = []
    if word == '.' :
        break
    for i in word :
        if i in ['[',']','(',')']:
            if len(stack) == 0 :
                stack.append(i)
            elif (stack[-1] == '[' and i == ']') or (stack[-1] == '(' and i == ')') :
                stack.pop()
            else :
                stack.append(i)


    if len(stack) == 0 :print('yes')
    else : print('no')

 

---

4.  AC (🥲해결못함)

• 런타임 에러 (Valueerror) 원인을 못 찾겠다 정말 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

from collections import deque
m = int(input())

for _ in range(m) :
    word = input()
    n = int(input())
    A = input()
    # 리스트로 바꾸기
    A = deque(A[1:-1].split(","))
    direction = 1
    
    for i in range(len(word)) :
        a = word[i]
        if len(A) == 0 and a == 'D' :
            print('error')
            break
        if a == 'R' :
            direction *= -1
        elif direction > 0 and a == 'D' :
            A.popleft()
        elif direction < 0 and a == 'D' :
            A.pop()


    if len(A) == 0 :
        print("error")
    else :
        if direction < 0 :
            A = list(map(int, A))
            A.reverse()
            print(A)
        else :
            A = list(map(int, A))
            print(A)

 

---

5. 할인행사

• 문제 정확히 읽어야 함.. 총 몇 개인지 !!! 최소가 아니라 !!! 제발 제발 ㅠㅠ 쓸데없는데 고민 시간 낭비 하지 말자고 !!!!!!!! 

https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

from collections import Counter
def solution(want, number, discount):
    dict_a = {}
    for i in range(len(number)) :
        dict_a[want[i]] = number[i]

    answer = 0
    for i in range(len(discount) - 9) :
        start_index = i
        end_index = i + 10
        dict_b = Counter( discount [ start_index : end_index ] )

        if dict_a == dict_b :
            answer += 1

    return answer

 

---

6. 귤 고르기

• 내가 dict를 다루는 법을 참 몰라서,, 맨날 list로 바꿈 --> 엄청난 반성과 노력 필요
• Counter 함수에 냅다 list 하면, keys values 엉망됨..  -> 이유는 모름.. ㅜㅜ

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

from collections import Counter

def solution(k, tangerine):
    dict_count = (Counter(tangerine))
    dict_list = list(zip(dict_count.values(),dict_count.keys()))
    dict_list.sort(reverse=True)
    answer_set = set()

    answer = 0

    for i in range(len(dict_list)) :
        if answer >= k :
            break

        else :
            answer += dict_list[i][0]
            answer_set.add(dict_list[i][1])

    return len(answer_set)

 

---

7. 영어 끝말잇기

https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

import math
def solution(n, words):
    TF = True
    for i in range(0,len(words)) :

        if i == 0 :
            continue
        elif (words[i-1][-1] != words[i][0]) or (words[i] in words[0:i-1]) :
            TF = False
            break

    if TF :
        answer = [0,0]
    else :
        turn_count = math.ceil((i+1)/n)
        turn_people = (i+1) % n
        if turn_people == 0 :
            turn_people = n

        answer = [turn_people, turn_count]

    return answer

 

---

8. 점프와 순간이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

• dp로 풀면.. 시간초과 발생함

def solution(n):

    d = [0 for _ in range(n+1)]
    d[1] = 1

    for i in range(2,n+1) :

        if i%2 == 0 :
            d[i] = min(d[i-1]+1, d[i//2])

        else :
            d[i] = d[i-1]+1

    return d[-1]

 

• 그나마 효율성 있는 코드인데,, 그래도 2개의 케이스에서 시간초과 발생
  • 2로 n을 나누면서 홀수만나면 count 값 증가..

def solution(n):
    count = 1
    while n > 1 :

        if n%2 == 0 :
            n /= 2

        else :
            n = n-1
            count += 1

    return count

• 정답 코드 : 위에 방식이랑 똑같음... 홀수면 count 값에 1을 더해주고, 계속해서 2을 나누기

def solution(n):
    count = 1
    while n > 1 :
        count += n%2
        n //=2
    return count

 

 

---

9.  N개의 최소공배수

• 유클리드 호제법 개념 이용해서 풀기.. 
  • 큰 수를 작은 수로 나누는 MOD 연산 수행
  • 앞 단게에서 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산 수행
  • 나머지 값이 0이 되는 순간의 작은 수를 최대 공약수로 선택

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

def solution(arr):
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)

    number = arr[0]
    for i in range(len(arr)) :
        a = gcd(number, arr[i])
        number = ( number * arr[i]) / a

    return int(number)

 

---

10. 프로세스(⭐️복습하기)

• 인덱스와 값 같이 계산하는 법
  
  • queue = [(i,j) for i,j in enumerate(리스트)]
  • 값이 하나라도 있으면 -> any 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

def solution(priorities, location):
    queue = [(i,j) for i,j in enumerate(priorities)]
    count = 0

    while True :
        number = queue.pop(0) #가장 왼쪽 첫번째 요소 제거
        if any(number[1] < j[1] for j in queue) :  #하나라도 있으면 !! 
            queue.append(number) # 다시 append 시켜주기

        else :
            count += 1
            if location == number[0] :
                return count

 

---

11. 야근지수

 

시간초과

def solution(n, works):

    for i in range(n) :
        if len(works) == 0:
            break
        max_number = max(works)
        works.remove(max_number)

        if max_number != 1 :
            works.append(max_number - 1)

    answer = 0
    for i in works :
        answer += i * i
    return answer

 

 

힙을 공부해야겠다 .. !!

# 파이썬의 heapq 모듈로 힙 자료구조 사용하기

# 모듈 불러오기
from heapq import heappush, heappop

# 힙 생성 : 파이썬에서 heap 생성할 땐, 리스트 선언과 같음
heap = []
# 힙에 원소 추가
heap = []
heappush( heap, 4 )
heappush( heap, 1 )
heappush( heap, 7 )
heappush( heap, 3 )
heappush( heap, 8 )
heappush( heap, 5 )
print(heap)  #[1, 3, 5, 4, 8, 7]

#      1
#    /   \
#   3      5
#  /        \
# 4          8

# 힙에서 원소 삭제
heappop(heap)
print(heap) # [3, 4, 5, 7, 8]
heappop(heap)
print(heap) # [3, 4, 5, 7, 8] -> 원소가 제거될 때마다 재배치가 일어나는 것을 알 수 있음

# 최소값을 삭제하지 않고 접근하기
print(heap[0])

# 기존 리스트를 힙으로 변환 -> heapify
from heapq import heapify
heap = [4,1,5,3,8,5]
heapify(heap)
print(heap) # [1, 3, 5, 4, 8, 5]

# [응용] 최대힙
from heapq import heappush, heappop
nums = [4,1,5,3,8,5]
heap = []

for num in nums :
    heappush(heap, (-num,num))

while heap :
    print(heappop(heap)[1])


# [응용] n번째 최소값 / 최대값
from heapq import heappush, heappop

def nth_smallest(nums, n) :
    heap = []
    for num in nums :   # 혹은 heapify 호출해서 heapift(nums) 해줘도 됨 !!
        heappush(heap,num)

    nth_min = None
    for _ in range(n) :
        nth_min = heappop(heap)

    return nth_min

# 혹은 nsmallest
from heapq import nsmallest
print(nsmallest(3,[4,1,7,3,8,5]))

# nlargest
from heapq import nlargest
print(nlargest(3,[4,1,7,3,8,5]))

 

✅ 힙으로 해결하는 풀이법  ✅

import heapq
def solution(n, works):
    if n >= sum(works) :
        return 0

    works = [-w for w in works ]
    heapq.heapify(works)

    for _ in range(n) :
        i = heapq.heappop(works)
        i += 1
        heapq.heappush(works, i)


    return sum([w ** 2 for w in works])

---

12. 최대 힙

https://www.acmicpc.net/problem/11279

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

n = int(input())

heap = []
for i in range(n) :
    number = int(input())

    if number != 0 :
        heappush( heap, (- number, number ) )

    if number == 0 :
        if len(heap) == 0:
            print(0)
        else :
            print(heappop(heap)[1])

 

 

---

13. 최소 힙

https://www.acmicpc.net/problem/1927

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

n = int(input())

heap = []
for i in range(n) :
    number = int(input())

    if number != 0 :
        heappush (heap, number)

    else :
        if len(heap) == 0 :
            print(0)

        else :
            print(heappop(heap))