코딩하는 eroke

문제: 보물

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

크기 N의 배열 A, B이 있고, 위 공식 값이 최소가 되도록 A의 원소 위치를 변경하는 문제이다.

위 공식 값이 최소가 되려면 A[N-1] * B[N-1] 이 A의 최소값 * B의 최대값이 되어야 한다. 

나는 직접 원소를 이동시키진 않았고 A, B 배열을 복사해 최대값, 최소값을 갱신하고 삭제해가며 값을 계산했다.

풀이

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    tmpA = A
    tmpB = B
    answer = 0

    for i in range(N):
        mina = min(tmpA)
        maxb = max(tmpB)
        if len(tmpA)>0:
            tmpA.remove(mina)
            tmpB.remove(maxb)
        answer += (maxb * mina)

    print(answer)

요새 알고리즘을 하는둥 마는둥 깔짝이다

저번 주에 오오오오랜만에 코테를 무려 4개나 치루고,, 많은 자극을 받았다.

기본 문제부터 다시 차근차근 풀어볼 예정으로 오랜만에 백준으로 문풀을 했다.

문제 : 다리놓기

< 그림과 같이 강 동쪽(M)에서 강 서쪽(N)으로 겹치지 않게 다리를

놓을 수 있는 경우의 가지수를 출력하면 된다 ~_~

조합문제여서 python combinations를 사용해서 쓰면 (N=13, M=29)만 되어도

실행시간이 엄청 오래걸리고 제출 시 런타임에러가 발생한다.

문제에서 의도한 바는 조합 공식 (m!/n!(m-n)!) 을 활용해 푸는 거인 것 같지만,,

파이썬에는 조합의 개수를 바로 구해주는 math 함수가 있다. (개꿀)

풀이

import math

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N,M = map(int,input().split()) # mCn
        arr = list(range(1,M+1))

        #print(len(list(it.combinations(arr,N)))) #Runtime ERR
        print(math.comb(M,N))

math.comb(M,N)를 사용하면 M개에서 N개를 조합으로 선택할 때의 경우의 수를 출력한다.

리스트 생성

a = []  #기본

a = [0]*N #크기 N의 1차원 리스트를 0으로 초기화 생성

b = [[0]*N for _ in range(N)] #N*N 2차원 리스트를 0으로 초기화 생성

리스트의 입출력

연속 입력 시 input().split() 을 사용한다. 

input()은 기본적으로 문자열 형식으로 입력받기 때문에 다른 자료형으로 입력받으려면 map을 사용하면 된다.

#변수입출력
N = input() #기본적으로 문자열로 받음, 정수입력 = int(input())
a, b = map(int, input().split()) #int로 연속입력

#리스트입출력
arr = list(input().split()) #공백으로 구분, 연속입력
arr2 = list(map(int, input().split())) #int로 입력 

#리스트 원소 붙여서 출력
arr=''.join(arr)
print(arr)

#리스트 원소 사이의 문자 지정 가능
arr='.'.join(arr)
print(arr)


#2차원리스트입력
for i in range(n):
    arr3.append(list(map(int, input().split())))

arr4=[list(map(int, input().split())) for _ in range(n)]

a=''.join(a)

기본적으로 사용하는 메소드들

import random as r

b= list(range(1,11)) #1~10

r.shuffle(b) #b 무작위로 섞음 

b.insert(인덱스, 값) #해당 인덱스에 값 추가

b.append(값) #리스트 끝에 해당 값 추가

b.pop() #끝값 제거

b.remove(값) #첫번째 값 삭제
del b[인덱스] #해당 인덱스 값 삭제

b.index(값) #해당값의 인덱스 출력

len(b) #리스트 b의 길이

리스트 슬라이스 기능

a[:n] #0~(n-1)인덱스까지 슬라이스

enumerate 

리스트의 인덱스, 값에 각각 접근이 가능하다.

for x in enumerate(b):
	print(x) # len(b) 만큼 리스트 b의 (인덱스, 값)이 tuple형으로 순서대로 출력됨
	print(x[0], x[1]) #괄호, 콤마 없이 인덱스 값 만 출력됨
    
for index, val in enumerate(b):
	print(index, val) # line 3과 출력 같음

all, any

if all(50>x for x in a):
	print("모두 50 이상") 
    
if any(50>x for x in a):
	print("하나라도 50 이상")

python list 내장함수들에 대해 기본적으로 정리해보았고 계속해서 추가할 예정이다,,

문제

예제

Input: prices = [7,1,5,3,6,4]
Output: 5

Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104

주식이 1인 시점에서 6인 시점에 팔아야 최대 이득을 볼 수 있고 이득은 5이다.

브루트포스로 풀면 O(n^2)으로 제출 시 타임아웃 에러가 난다.

주식의 최소값과 이득을 계속해서 갱신하는 방법으로 O(n)에 해결해야 하는 문제이다.

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        minp = sys.maxsize
        
        for p in prices:
            minp = min(p, minp) #최소값 갱신
            result = max(result, p-minp) #이득 갱신
        
        return result

결과

문제 

문자열에서 가장 긴 팰린드롬 문자열을 추출하는 문제이다. (팰린드롬 : 앞뒤가 똑같은 문자열)

(연관문제 : 유효한 팰린드롬)

예제

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

풀이 (python)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def expand(l:int, r:int)->str: #left, right 이중 포인터
            while l>=0 and r<len(s) and s[l]==s[r]:
                l-=1
                r+=1
            return s[l+1:r] # 인덱스 l부터 r-1까지 
        
        result = ''
        
        if len(s)<2 or s==s[::-1]:  #예외처리
            return s
        
        for i in range(len(s)-1):
            result = max(result,
                         expand(i, i+1), #팰린드롬 길이가 짝수인 경우
                         expand(i, i+2), #팰린드롬 길이가 홀수인 경우
                         key=len)
                         
        return result

투 포인트를 사용해 팰린드롬 길이가 짝수/홀수 인 경우를 구분했고

인덱스를 확장하며 팰린드롬을 리턴하는 expand(left, right) 함수를 만들어 길이 기준 (key=len)으로

최대길이 문자열을 반환했다.

문제

풀이

import collections as coll
def solution(numbers):
    answer = []
    dic = coll.defaultdict(int)
    numbers.sort()
    
    ln = len(numbers)
    
    for i in range(ln):
        for j in range(ln):
            if i==j: continue
            x=numbers[i]+numbers[j]
            if x not in dic:
                dic[x]=0
    
    answer = list(dic.keys())
    answer.sort()
    return answer

ㅋㅋ.. 3월에 코테를 왕창 볼 예정이어서 빡공해야 하는데

쉬운 문제만 골라 풀고있다 ㅠㅠㅠㅠ 흑흑 정신채리~~~

2022 마이다스 공채가 떴다.
1차는 3/5까지 AI 역량검사 필수로 응시 후 3/6까지 지원완료해야하는 일정이다.
마이다스에서 개발한 역량검사 플랫폼인 JOBDA(https://m.jobda.im/getjob/299)에서 지원가능하다.

자소서가 없고 신입초봉 5000이라는 파격 조건에 절찬 모집중이다..
자소설닷컴 채팅에 의하면 5000이 계약연봉은 아니고 성과금이 포함된 금액이라고 한다... (그래도 영끌 5300이상)

원래는 JOBDA에서 월 3회 역검 응시가 지원되는데 (작년은 월 2회였는데 늘어난듯)
마이다스 공채가 진행 중이다보니 특별히 2월은 5회 지원된다고 한다.
3월까지 합치면 총 8회 응시 가능하다.

AI 면접

AI 면접은 세 유형으로 이루어져 있고 1시간 30분 정도 소요된다.

1. 성향파악 (인성검사)
2. 영상면접 (AI화상면접)
3. 게임

성향파악은 인성검사로 느껴졌다. 여러 방식으로 질문의 답들을 편하게 선택하면 된다.

영상면접은 정말 면접스러웠다. 기술 외의 것들을 물어보는데
질문하고도 생각할 시간도 30초 정도 주고 대답 기회도 1분 정도씩 두번 주어진다. (오픽같다..)

아무 준비없이 한번 응시해봤는데 작년에 있던 게임은 다 사라지고 새로운 게임들이 생겼다.
더 어려워진 것 같다. (아직도 마법약은 전혀 모르겠음)

밤에 응시하고 다음날 일어났더니 결과가 나와있었다.
결과도 세 단계 (치얼업/굿/베리굿)로 나오는 것 같다.

+ 서류 마감 후 2일 뒤 저녁(3/8)에 코딩테스트 안내 문자와 메일이 왔다.

코딩테스트 일정
3/10, 19:00~22:00
2문제 (180분)
플랫폼 : 프로그래머스

이틀만에 평일 저녁에 시험을 봐야해서
일정에 아쉬움이 있었다 ㅜ.ㅜ (주말에 볼줄)

• OS 인강 - 반효경 교수님 KOCW 강의

• 깃허브 기술 면접 Repository
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner
• https://github.com/WooVictory/Ready-For-Tech-Interview
• https://github.com/gyoogle/tech-interview-for-developer
• https://github.com/WeareSoft/tech-interview

Reference

sorted()

1. sorted()는 리스트, 문자, 숫자 모두 정렬이 가능하다 list 형으로 반환한다. (용도에 맞게 join 하기)

   ※ sort()는 리스트 자료형만!

2. key 옵션으로 정렬 기준을 지정할 수 있다. 

a = ['aaa', 'aa', 'b', 'cccc']
sorted(a, key=len) # ['b', 'aa', 'aaa', 'cccc']

b = ['cde', 'ctc', 'abc']
# b의 문자열 중 첫문자를 우선, 다음은 마지막 문자 기준 정렬
sorted(a, key=lambda s: (s[0], s[-1])) # ['abc', 'ctc', 'cde'] 

#람다대신 함수지정도 가능
def fn(s):
  return s[0], s[-1]

print(sorted(a, key=fn))

#딕셔너리 key로 정렬
d1 = sorted(d.items())

#딕셔너리 val로 정렬
d2 = sorted(d.items(), key=lambda x: x[1])

문제

애너그램 : ate=tea=eat > 같은 문자들로 문자열을 재배열

애너그램끼리 그룹짓는 문제이다.

풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        dic = collections.defaultdict(list)
        
        for arr in strs:
            tmp = ''.join(sorted(arr)) #sorted(arr) -> list 반환, sorted("tea")=['a', 'e', 't']
            dic[tmp].append(arr)

        return dic.values()

 sorted()는 리스트, 문자, 숫자 모두 정렬이 가능하다 list 형으로 반환한다. (용도에 맞게 join 하기)