bright

Input = [ [1,3] , [4,3], [4,10] ] 

def solution(v):
    
    tmp = dict()
    
    for i in v : 
        if i[0] in tmp:
            tmp[i[0]].append(i[1])
        else:
            tmp[i[0]]=[i[1]]
            
    k = list( tmp.keys() ) 
    
    if len( tmp[k[0]]) > len( tmp[k[1]]) : 
        answer= [k[1]]
        for i in tmp[k[0]] :
            if i not in tmp[k[1]]:
                answer.append( i )
    else:
        answer= [k[0]]
        for i in tmp[k[1]] :
            if i not in tmp[k[0]]:
                answer.append( i )

    return answer

import itertools

L, c = map(int,input().split()) # 암호 길이, 문자의 수 
data = list(map(str,input().split()))
data.sort()

# c 개 중에 L 개 뽑아 나열하기 
# 최소 모음 1개 최수 2개 자음 

vowel = [ 'a', 'e', 'i', 'o', 'u']

for i in itertools.combinations( data,L):

    cnt = 0 

    for k in i : 
        if k in vowel:
            cnt += 1 
    
    if cnt >= 1 and cnt <= L-2 : 
        print( ''.join( i ))

풀이 방법 : 조합 ( combination ) 사용  /  import itertools 

L 개 중, c 개의 문자를 뽑아 암호를 만든다. 문제에서 순서는 알파벳 순이라고 지정해 주었으므로 

순열 ( permutations ) 가 아닌 조합을 사용하면 된다. 

암호의 조건으로 모음이 최소 1개, 자음이 최소 2개이다. 

따라서, 우선 가능한 조합을 모두 나열한 다음,

모음을 세는 변수를 만들어 암호 안의 모음의 개수를 세고 이를 활용하여 자음의 개수 까지 센다. 

( 모음이 아닌 건 다 자음이므로 모음의 수가 ( 전체 암호 길이 ) - 2 이하라면 조건을 만족한다 ) 

import math

m, n = map(int,input().split()) # m ~ n 사이 소수 구하기 

prime = [ True for i in range(1000001)]
prime[1] = False # 1 은 소수가 아님 

for i in range(2, int(math.sqrt(n))+1):
  if prime[i] == True:
    j = 2
    while i*j <= n : 
      prime[i*j] = False
      j += 1 

for i in range(m,n+1):
  if prime[i] : 
    print( i)

약수는 대칭적인 구조로 이루어져 있으므로, n 의 제곱근 까지만 구하면 된다. 

ex ) 8 ( 제곱근 : 약 2.9 ) 

1*8 = 2*4 = 4*2 = 8*1 

에라토스테네스의 체 알고리즘을 이용하여 n 까지의 모든 소수를 구하고나서, 

m~ n 까지 출력하면 간단하게 구현 가능하다. 

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        
        for i in s:
            if i not in table:
                stack.append(i)
            elif not stack or table[i] != stack.pop():
                return False 
            
        return len(stack) == 0 

입력된 괄호 식이 올바른지 판단하는 문제. 

테이블에 없는 값이 들어오면 스택에 넣고 있는 값이 들어오면 스택에서 꺼내서 값이 맞는지 확인한다. 

딕셔너리 자료형을 활용해서 풀이한다. 

leetcode.com/problems/valid-parentheses/

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(x,y):
            if x < 0 or y < 0 or x>= len(grid) or y>= len(grid[0]) : 
                return False 
            
            if grid[x][y] == "1" :
                grid[x][y] = 0 
                
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y+1)
                dfs(x,y-1)
                
                return True
            return False 
        
        cnt = 0 
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if dfs(x,y) == True:
                    cnt += 1 
        return cnt

음료수 얼려 먹기 문제와 거의 유사한 dfs 문제이다. 

입력 받는 방식이 조금 특이하다. 

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

leetcode.com/problems/number-of-islands/

1. 표준 라이브러리 

특정한 프로그래밍 언어에서 자주 사용되는 표준 소스 코드를 미리 구현해 놓은 라이브러리 

docs.python.org/ko/3/library/index.html

2. 내장함수 

- sum()

- print()

- min()

- max()

- eval()  : 수식이 문자열 형식으로 들어오면 계산해서 결과를 반환 

- sorted() 

3. itertools 

- permutations() :  순열 계산 ( 순서 신경 o ) 

- combinations() :  조합 계산 ( 순서 신경 x ) 

4. heapq 

python 에서 heap 기능을 위해 사용한다. 다익스트라 최단 경로 알고리즘 등에서 우선순위 큐를 구현하고자 할 때 사용된다. 파이썬에서는 힙을 최소 힙으로만 구성함을 기억한다. ( 최대 힙으로 만들고 싶으면 파라미터에 - 를 붙여 활용 ) 

- heapq.heappush() : 힙에 원소 삽입 

- heapq.heappop()  : 힙에서 원소 꺼냄 

5. bisect 

이진탐색을 쉽게 구현할 수 있도록 제공되는 라이브러리로, 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. 

- bisect_left (a, x )  :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 왼쪽 인덱스를 찾아줌. 

- bisect_right(a, x ) :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 오른쪽 인덱스를 찾아줌.

6. collections 

유용한 자료구조를 제공하는 표준 라이브러리

- deque   :  큐를 구현하는데 사용함. popleft, pop, appendleft, append 로 원소 배치. 

- Counter :  등장 횟수를 세는 기능을 제공. 리스트 같은 iterable 객체에서 원소가 몇 번 등장했는지 알려줌. 

7. math

자주 사용되는 수학적인 기능을 포함하는 라이브러리

- factorial()

- sqrt()   : 제곱근 

- gcd()   : 최대 공약수 

- pi 

- e 

1. 개념 

식별자 없이 실행 가능한 일회성 함수. 

def 의 함수 선언 없이도 하나의 식으로 함수를 단순하게 표현할 수 있음. 

2. 사용 예시 

1) 리스트 정렬 시, key 값으로 전달 // 정렬의 우선 순위를 부여하는 경우에 사용하면 매우 편리 

s = [ ( 'A', 1 ) , ( 'Z', 2 ) , ( 'N', 9 ) , ( 'B', 3 ), ( 'H', 3 ) ] 을  숫자 기준 내림차순 , 문자 기준 오름차순으로 정렬하시오. 

s.sort( key = lambda x: ( -x[1], x[0] ) ) 

결과 : [('N', 9), ('B', 3), ('H', 3), ('Z', 2), ('A', 1)]

문자 순으로 정렬하되, 문자가 동일한 경우에는 식별자 순으로 나열하라. 

logs = ["let1 art ","let2 own","let3 art", "let4 cat", "let5 book"]

logs.sort( key = lambda x: ( x.split()[1:] , x.split()[0] ) ) 

결과 : ['let1 art ', 'let3 art', 'let5 book', 'let4 cat', 'let2 own']

3. 주의 사항 

map, filter 등과 함께 사용하면 가독성이 매우 떨어질 수 있으므로 주의해서 사용한다. 

또한, 꼭 필요한 경우가 아닐 때는 람다 표현식 보다는 리스트 컴프리핸션이 더 많이 사용된다. 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 
        
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]
                
        return result 

쌀 때 사서 비쌀 때 팔아 가장 높은 수익을 얻는 문제.

그리디 알고리즘을 사용하여 풀면 간단하다. 

만약, 현재보다 다음 값이 오른다면 사고 판다. 

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

팰린드롬 : 앞 뒤가 똑같은 문자열. 

주어진 문자열이 팰린드롬인지 확인할 것. 대소문자 구분 x 영문자와 숫자만을 취급. 

ex ) 

INPUT = "A man, a plan, a canal: Panama"  

OUTPUT = True

INPUT = "0P"
OUTPUT = False 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        real_s = []
        for i in s : 
            if 48<=ord(i)<=57 or 65<= ord(i) <=90 or 97<=ord(i)<=122 :
                real_s.append(i)
        
        for i in range( len(real_s)//2 ):
            if real_s[i].upper() != real_s[ len(real_s)-i-1 ].upper():
                return False 
        return True

tip!  

real_s.append(i)  할 때, real_s.append( i.upper() ) 로 리스트에 추가하면 더 효율적으로 코드를 작성할 수 있다. 

leetcode.com/problems/valid-palindrome/

문자열 n 에서 m 을 제외한 문자열을 출력하시오. 

n = input()
m = input() 
k = 0 
p=''

for i in n : 
  if k == len(m) or i != m[k] :
    p = p + i 
    
  else:
    k += 1 

print(p)