문제 : https://www.acmicpc.net/problem/1620

 

1620번: 나는야 포켓몬 마스터 이다솜

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면

www.acmicpc.net

 

▶ 코드(딕셔너리)

# 이진탐색으로 풀이 불가
# 딕셔너리로 풀이

n, m = map(int, input().split())

dic1 = {}
dic2 = {}
for i in range(n):
    name = input()
    dic1[i+1] = name # i=1번째 부터 시작~
    dic2[name] = i+1

for _ in range(m):
    word = input()

    if word.isdigit(): # 입력된 str이 숫자형태면
        word = int(word)
        print(dic1[word])
    else:
        print(dic2[word])

이진탐색으로 어떻게 풀이..?

'■코테 중요개념 > 이분 탐색' 카테고리의 다른 글

[백준 10816] 숫자 카드 2  (0) 2020.05.18
[백준 1654] 랜선 자르기  (0) 2020.05.18
[백준 10815] 숫자 카드  (0) 2020.05.17
[백준 1920] 수 찾기  (0) 2020.05.17

문제 : https://www.acmicpc.net/problem/1920

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안��

www.acmicpc.net

▶ 코드

import sys

# arr배열의 원소가 숫자일때만 가능 
def BinarySearch(arr, val, low, high):
    if low > high:
        return False

    mid = (low + high) // 2
    
    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        return True
    
if __name__ == "__main__":
        N = int(sys.stdin.readline())
        A = list(map(int, sys.stdin.readline().split()))
        M = int(sys.stdin.readline())
        B = list(map(int, sys.stdin.readline().split()))

        A = sorted(A) # 매개변수로 들어갈 배열이 미리 정렬 되어있어야됨 

        for b in B:
            if BinarySearch(A, b, 0, N-1): # 배열, 찾으려는 원소, start, end
                print(1)
            else:
                print(0)

문제 : https://www.acmicpc.net/problem/13458

 

13458번: 시험 감독

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

www.acmicpc.net

▶ 코드

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
a, b = map(int, sys.stdin.readline().split())
#print(a,b)

sum_val = 0
for e in lst:
    if e-a<=0:
        sum_val += 1
        continue
    else:
        sum_val += 1 # 총 감독관(a)은 무조건 한명 들어가야됨 
        if (e-a)%b == 0:
            sum_val += (e-a)//b
        else:
            sum_val += (e-a)//b + 1
print(sum_val)

문제 : https://programmers.co.kr/learn/courses/30/lessons/42747

 

코딩테스트 연습 - H-Index

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표

programmers.co.kr

▶ 코드

def solution(citations):

    ans = []   
    citations.sort() # [0,1,3,5,6]
    #print(citations)
    
    for i in range(1, len(citations)+1): # 1번~N번 인용
        for j in range(len(citations)):
            if i <= citations[j]: # 인용횟수i 보다 크거나 같은 배열원소 찾으면 
                if len(citations[j:]) < i : # 원소갯수가 인용횟수보다 낮다면 
                    break # 다음 i로 넘어가기 
                else: # 원소갯수가 인용회수 '이상' 이라면(=같거나 크다면)
                    ans.append(i)
               
    #print(ans)
    if len(ans) == 0: # 예외처리 
        return 0
    else:
        return max(ans)
        
#solution([3,0,6,1,5])
#solution([5,5,5,5,5])

'[프로그래머스] 코테 고득점 Kit > 정렬' 카테고리의 다른 글

[Level 1] K번째수  (0) 2020.05.16

문제 : https://programmers.co.kr/learn/courses/30/lessons/42748

 

코딩테스트 연습 - K번째수

[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

programmers.co.kr

▶ 코드

import copy

def solution(array, commands):
    res = []
    for a in commands:
        tmp = copy.deepcopy(array)
        tmp = tmp[a[0]-1:a[1]]
        tmp.sort()
        res.append(tmp[a[2]-1])
    return res

#solution([1,5,2,6,3,7,4], [[2,5,3],[4,4,1],[1,7,3]])

'[프로그래머스] 코테 고득점 Kit > 정렬' 카테고리의 다른 글

[Level 2] H-Index  (0) 2020.05.16

문제 : https://programmers.co.kr/learn/courses/30/lessons/42579

 

코딩테스트 연습 - 베스트앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 ��

programmers.co.kr

딕셔너리 value값으로 정렬 하기 : https://kkamikoon.tistory.com/138

 

[Python] 딕셔너리 정렬하기

파이썬 딕셔너리에 입력된 key 값과 value 값들을 정렬해야 할 때가 있습니다. 그럴 때 해결할 수 있는 방법을 사용해보려고 합니다. 각각 Key를 이용한 방법과 Value를 이용한 방법이 있습니다. 딕셔

kkamikoon.tistory.com

→ 딕셔너리를 정렬하는 순간 리스트 형태로 바뀐다.

 

▶ 코드

# 장르별로 두개씩 모아 베스트 앨범을 출시 

import operator

def solution(genres, plays):
    ans = []
    dic = {}
    for a, b in zip(genres, plays):
        if a in dic.keys():
            dic[a] += b
        else:
            dic[a] = b
    #print(dic) # {'classic': 1450, 'pop': 3100}
    sdic = sorted(dic.items(), key=operator.itemgetter(1), reverse=True)
    #print(sdic) # [('pop', 3100), ('classic', 1450)]
    for a in sdic:
        c = 0
        target = a[0]
        #print(target)
        tmp_dic = {}
        index = -1
        for i in range(len(genres)):
            
            if genres[i] == target:
                index = i
                tmp_dic[index] = plays[index]
        #print(tmp_dic) # {1: 600, 4: 2500}
        #print(index)
                
        if len(tmp_dic) == 1:
            ans.append(index)
            continue

        tmp_dic = sorted(tmp_dic.items(), key=operator.itemgetter(1), reverse=True)
        #print(tmp_dic) # [(4, 2500), (5, 2500), (1, 600)]
        c = 0
        i = 0
        while c < 2:
            ans.append(tmp_dic[i][0])
            c += 1
            i += 1
    #print(ans)
    return ans        

#solution(['classic', 'pop', 'classic', 'classic', 'pop', 'pop'], [500, 600, 150, 800, 2500, 2500])
#solution(['classic','pop','classic','classic','pop'],[500,600,501,800,900])

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

 

코딩테스트 연습 - 전화번호 목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조��

programmers.co.kr

▶ 코드

def solution(phone_book):
    
    phone_book.sort()  # 숫자로된 문자열을 sort()하면, 앞 숫자 순서대로 정렬.. 
    #print(phone_book) # ['119', '11955678484', '7777', '9876532']

    for p1, p2 in zip(phone_book, phone_book[1:]): # ['119', '11955678484', '7777', '9876532'] 와 ['11955678484', '7777', '9876532']이 하나씩 짝을 이룸
        #print(p1, p2)
        if p2.startswith(p1):
            return False
    return True

#solution(["7777", "119","9876532","11955678484"])

'[프로그래머스] 코테 고득점 Kit > 해시' 카테고리의 다른 글

[Level 3] 베스트앨범  (0) 2020.05.16
[Level 1] 완주하지 못한 선수  (0) 2020.05.16

문제 : https://programmers.co.kr/learn/courses/30/lessons/42576

 

코딩테스트 연습 - 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수��

programmers.co.kr

▶ 코드

from collections import Counter

def solution(p, c):
    p_counter = Counter(p)
    c_counter = Counter(c)

    for a in p_counter.keys():
        if p_counter[a] != c_counter[a]:
            return str(a)

#solution(['mislav', 'stanko', 'mislav', 'ana'], ['stanko', 'ana', 'mislav'])

'[프로그래머스] 코테 고득점 Kit > 해시' 카테고리의 다른 글

[Level 3] 베스트앨범  (0) 2020.05.16
[Level 2] 전화번호 목록  (0) 2020.05.16

문제 : https://programmers.co.kr/learn/courses/30/lessons/42842

 

코딩테스트 연습 - 카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 ��

programmers.co.kr

▶ 코드

def solution(brown, yellow):
    s = brown+yellow

    # 합 :조합 구하기
    temp1 = []
    for i in range(3, s+1):
        flag = 0
        if s%i == 0:
            flag = 1
            left = s//i
            right = i
        if flag==1 and left >= right:
            temp1.append([left,right])

    # yellow 조합 구하기
    temp2 = []
    for i in range(1, yellow+1):
        flag = 0
        if yellow%i == 0:
            flag = 1
            left = yellow//i
            right = i
        if flag==1:
            temp2.append([left, right])

    #print('합 = ',temp1)
    #print('yellow=', temp2)
    #print()

    # yellow와 합 리스트 하나씩 비교
    # 조건: yellow의 left,right는 '합'의 left,right보다 둘다 무조건 작고,
    #       yellow의 left, right보다 '합'의 left,right는 항상 각각 2이상 커야한다.

    for a in temp2: # yellow
        for b in temp1: # '합'
            if a[0]+2 <= b[0] and a[1]+2 <= b[1]:
                res = [b]
                #print(res[0])
                return res[0]
                break
        


#solution(10, 2)
#solution(8, 1)
#solution(24, 24)

 

 

'[프로그래머스] 코테 고득점 Kit > 완전탐색' 카테고리의 다른 글

[Level 2] 소수 찾기  (0) 2020.05.15
[Level 1] 모의고사  (0) 2020.05.15

문제 : https://programmers.co.kr/learn/courses/30/lessons/42839

 

코딩테스트 연습 - 소수 찾기

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 �

programmers.co.kr

에라토스테네스의 체 : 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

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수(소수)를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[��

ko.wikipedia.org

▶ 코드

# 에라토스테네스의 체 : N미만의 소수 찾아서 리스트로 반환 
def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    #print([i for i in range(2, n) if sieve[i] == True])
    return [i for i in range(2, n) if sieve[i] == True]

# numbers에 숫자 하나만 들어있을 경우, 그 숫자가 소수인지 판별 
def isPrime(n):
    c = 0
    for i in range(2, n+1):
        if n%i == 0:
            c += 1
    if c == 1:
        return True
    else:
        return False

def solution(numbers):
    if len(numbers) == 1:
        if isPrime(int(numbers)):
            #print(1)
            #print()
            return 1
        else:
            #print(0)
            #print()
            return 0
    
    t = []
    for a in numbers:
        t.append(int(a))
    t.sort(reverse=True)
    #print('t=', t)
    st = ''
    for a in t:
        st += str(a)
    st = int(st)
    #print('st =', st)
    lst = prime_list(st+1) # st+1 미만의 소수 찾아서 리스트로 반환  

    # 필터링 (각 소수 중, numbers에 없는 숫자 포함된것들을 필터링)
    temp = []
    for a in lst:
        flag = 0
        a = str(a)
        for b in a:
            if int(b) not in t:
                flag = 1
                break
        if flag == 0:
            temp.append(a)
    #print(temp)
    #print(len(temp))
    #print()

    # 필터링 (각 소수를 numbers와 자릿수마다 '해당 숫자' 개수 비교해 필터링)
    res = []
    for a in temp:
        flag = 0
        a = str(a)
        for b in a:
            if a.count(b) > t.count(int(b)):
                flag = 1
                break
        if flag == 0:
            res.append(a)
        
    #print(res)
    #print(len(res))
    #print()      
    
    return len(res)

#solution("013")
#solution("3")
#solution("4")
#solution("007")
#solution("070")
#solution("29")
#solution("17")
#solution("011")
#solution("1234")
#solution("7843")
#solution("999")

'[프로그래머스] 코테 고득점 Kit > 완전탐색' 카테고리의 다른 글

[Level 2] 카펫  (0) 2020.05.15
[Level 1] 모의고사  (0) 2020.05.15

문제 : https://programmers.co.kr/learn/courses/30/lessons/42840

 

코딩테스트 연습 - 모의고사

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 ��

programmers.co.kr

▶ 코드

def solution(answers):
    # 1번 사람 : 1/2/3/4/5         -> cycle: 5개
    # 2번 사람 : 21/23/24/25       -> cycle: 8개
    # 3번 사람 : 33/11/22/44/55    -> cycle: 10개
    
    p1 = [1,2,3,4,5]
    p2 = [2,1,2,3,2,4,2,5]
    p3 = [3,3,1,1,2,2,4,4,5,5]

    c1 = 0
    c2 = 0
    c3 = 0

    # 길이가 다른 두 배열의 각 원소 비교 (answers는 가변 길이)(p1,p2,p3 는 불변 길이)
    for i in range(len(answers)):
        if p1[i%len(p1)] == answers[i]:
            c1 += 1
        if p2[i%len(p2)] == answers[i]:
            c2 += 1
        if p3[i%len(p3)] == answers[i]:
            c3 += 1
    #print(c1,c2,c3)

    max_value = max(c1,c2,c3)
    res = []

    if c1 >= max_value:
        res.append(1)
    if c2 >= max_value:
        res.append(2)
    if c3 >= max_value:
        res.append(3)

    res.sort()
    return res

    
#solution([1,2,3,4,5])
#solution([1,3,2,4,2])

 

▶ 매개변수로 들어오는 answers의 길이만큼 p1,p2,p3 배열 만들어주면 시간초과 

길이가 다른 두 배열의 각 원소 비교하는 방법 으로 풀이해야됨 

'[프로그래머스] 코테 고득점 Kit > 완전탐색' 카테고리의 다른 글

[Level 2] 카펫  (0) 2020.05.15
[Level 2] 소수 찾기  (0) 2020.05.15

문제 : https://programmers.co.kr/learn/courses/30/lessons/64064?language=python3

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

▶ 코드

import re
from itertools import product

def solution(user_id, banned_id):
    # 1.정규표현식 매칭하기 
    my =[]
    for p in banned_id:
        temp = []
        p = p.replace('*','.')
        for a in user_id:
            res = bool(re.match(p, a))
            if (res and len(p)==len(a)):
                temp.append(a)
        my.append(temp)
    #print(my)

    # 2.조합 구하기 
    lst = list(product(*my))
    #print(lst)

    answer = []
    for a in lst:
        if len(a) == len(set(a)):
            tmp_lst = list(a)
            tmp_lst.sort()
            #print(tmp_lst)
            if tmp_lst not in answer:
                answer.append(tmp_lst)

    #print(len(answer))
    return len(answer)
    
#solution(["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "abc1**"])
#solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["*rodo", "*rodo", "******"])

출처 : https://ourcstory.tistory.com/414

 

 

출처 : https://lar542.github.io/Python/2019-07-11-python2/

re.findall

# re.findall(pattern, string) : 매칭되는것들을 배열로 리턴 

import re

inputString = 'aa1b2c3' 

# []: []사이의 문자들과 매칭 
p = '[a-zA-Z]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', 'b', 'c']

# .은 \n을 제외한 모든 문자와 매치 
p = 'a.1'
result = re.findall(p, inputString)
print(result) # ['aa1']

p = '[0-9]'
result = re.findall(p, inputString)
print(result) # ['1', '2', '3']

st = '\d'
p = re.compile(st) 
result = re.findall(p, inputString)
print(result) # ['1', '2', '3']

p = '[^0-9]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', 'b', 'c']

p = '[a-zA-Z0-9]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', '1', 'b', '2', 'c', '3']

p = '\w'
result = re.findall(p, inputString)
print(result) # ['a', 'a', '1', 'b', '2', 'c', '3']



inputString = 'ct'

# *은 * 바로 앞에 있는 문자 a가 0부터 무한대로 반복될 수 있다는 의미이다.
p = 'ca*t'
result = re.findall(p, inputString)
print(result) # ['ct']

# +는 최소 1번 이상 반복될 때 사용한다. 즉 *가 반복 횟수 0부터라면 +는 반복 횟수 1부터인 것이다.
p = 'ca+t'
result = re.findall(p, inputString)
print(result) # []



inputString = 'caat'

# {2} : 반드시 2번 반복
p = 'ca{2}t'
result = re.findall(p, inputString)
print(result) # ['caat']

# {2,5} : 2~5번 반복
p = 'ca{2,5}t'=
result = re.findall(p, inputString)
print(result) # ['caat']



inputString = 'ac'

# ? : 있어도 되고 없어도 된다
p = 'ab?c'
result = re.findall(p, inputString)
print(result) # ['ac']

 

re.sub

# re.sub(pattern, repl, string) : string에서 pattern과 매치하는 텍스트를 repl로 치환한다

# 문제) 
# aabbbca -> ['aa', 'bbb', 'c']         -> 2a3bc
# aabbbca -> ['aa', 'bbb', 'c', 'a']    -> 2a3bca
# abbcabb -> ['a', 'bb', 'c', 'a', 'bb']      -> a2bca2b

# 풀이)
import re

inputString = 'aabbbca'

p = r'(.)(\1+)'
repl = lambda c: str(len(c.group())) + c.group(1)

result = re.sub(p, repl, inputString)

print(result) # 2a3bca

# r : Raw String. 컴파일해야하는 정규식이 'Raw String'임을 알려줌 
# 괄호()를 써서 묶은 부분은 '1번부터 시작하는 그룹'으로 참조할 수 있다.
  (.)	-> 1번 그룹 
# 앞서 매치한 그룹을 '패턴 내에서 재사용'하려면 \1과 같이 그룹번호를 역슬래시로 이스케이프하여 표현한다. 

 

re.match

# re.match(pattern, string) : string에서 pattern과 매치하는 텍스트를 탐색한다

# 문제) 
# MAC Address는 항상 0~9,A~F사이의 값으로만 2개씩 총 6묶음으로 이루어져 있다. 
# MAC Address는 항상 똑같은 형식, 똑같은 길이를 갖는다.

# 풀이)
import re

inputString = "00-1B-63-84-45-E6"

p = '^([\dA-F]{2}-){5}([\dA-F]{2})$'

result = bool(re.match(p, inputString))
print(result) # True

# \d : 숫자를 나타냄
# {2} : 반드시 2번 반복 
# ^ : 문자열의 처음
# $ : 문자열의 끝 
# 문자열 처음 ~ 끝 지정해주는 이유 ? : 무조건 여기서 범위는 문자열의 처음~끝 으로 고정으로 해야 예외가 안생김
lst = ['1', '2', '3']

lst = list(map(lambda x: int(x), lst))

print(lst) # [1,2,3]

'코테 핵심노트 > 노트' 카테고리의 다른 글

노트 #6: 파이썬 2차원 배열 선언(초기화)  (0) 2020.05.22
노트 #5 : 파이썬 join()  (0) 2020.05.18
노트#4 : 파이썬 리스트 조합 구하기  (0) 2020.05.13
노트#3 : 정규표현식  (0) 2020.05.13
노트 #1  (0) 2020.05.10

문제 : https://programmers.co.kr/learn/courses/30/lessons/64065

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

▶ 코드

# 문자열 문제 

def solution(s):
    s = s[1:-1]
    s = s.replace('{','[')
    s = s.replace('}',']')
    #print(s)
    s = s[1:-1]
    s = s.split('],[')
    #print(s)
    s = sorted(s, key=lambda t: (len(t)))
    #print(s)
    #print()

    temp = []
    for a in s:
        temp.append(a.split(','))
    #print(temp)
    #print()
    
    result = []
    for a in temp:
        for b in a:
            if b not in result:
                result.append(b)
    #print(result)

    result = list(map(int, result))
    #print(result)

    return result
            
#solution("{{2},{2,1},{2,1,3},{2,1,3,4}}")
#solution("{{1,2,3},{2,1},{1,2,4,3},{2}}")
#solution("{{20,111},{111}}")
#solution("{{123}}")
#solution("{{4,2,3},{3},{2,3,4,1},{2,3}}")

문제 : https://programmers.co.kr/learn/courses/30/lessons/64061

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

▶ 코드

def solution(board, moves):
    n = len(board)
    p = [[] for i in range(n)] # 1번~N번 세로라인 배열 
    
    for i in range(n):
        for j in range(n):
            if board[i][j]!=0:
                p[j].append(board[i][j]) # 각 N번째 라인에 담아주기

    # 각 N번째 라인의 원소 순서 뒤집기 
    for a in p:
        a.reverse()
                
    my = [] # 뽑힌것 담을 배열 
    c = 0
    for a in moves:
        if len(p[a-1]) > 0:
            if len(my)>0 and p[a-1][-1] == my[-1]:
                my = my[:-1]
                p[a-1].pop()
                c += 1
            else:
                my.append(p[a-1].pop())
    #print(my)
    
    return c*2

문제 : https://programmers.co.kr/learn/courses/30/lessons/12987

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

▶ 코드

# 문제: A의 순서를 알고있을때, B의 순서 조작해서 최대한 많이 이겨라.

import heapq

def solution(A, B):
    A.sort(reverse=True) # A를 내림차순 정렬
    
    B = [-i for i in B] # B를 음수화 (최대힙 만들기 위해..)
    heapq.heapify(B) # B를 힙구조로 변환 (B는 최대힙)
    
    c = 0
    for a in A:
        if a >= abs(B[0]): # 음수화된 B에 절대값 씌워서 비교 !
            continue
        else:
            heapq.heappop(B) # B의 원소가 빠져나가도 최대힙 구조를 유지
            c += 1
    print(c)
    return c

'■코테 기출문제 > Summer,Winter Coding(~2018)' 카테고리의 다른 글

[Level 4] 쿠키 구입  (0) 2020.05.22
[Level 3] 방문 길이  (0) 2020.05.08
[Level 2] 영어 끝말잇기  (0) 2020.05.08
[Level 2] 점프와 순간 이동  (0) 2020.05.08
[Level 2] 소수 만들기  (0) 2020.05.08
[Level 3] 기지국 설치  (0) 2020.05.08
[Level 3] 배달  (0) 2020.05.08
[Level 1] 예산  (0) 2020.05.06

▶ 출처 : https://www.youtube.com/watch?v=rI8NRQsAS_s

문제1) 배열의 특정 연속된 구간을 처리하는 경우 ( 시간제한: O(n) )

ex) [1,2,3,2,5]중에서 합이 5인 '연속 수열의 개수'를 구하는 문제 

 

투 포인터를 활용한 알고리즘 코드

# 데이터 개수:n, 부분연속수열의 합: m
n = 5
m = 5
data = [1,2,3,2,5]

start = 0
end = 0
result = 0
sum_val = data[0]

end_flag=0 # end는 범위를 넘어버릴 가능성이 있으므로 while조건 체크후, flag체크후 sum_val 늘려주기

while start < n and end < n:

    if end_flag == 1:
        sum_val += data[end]
        end_flag=0

    print(start, end, sum_val)

    if sum_val < m:
        end += 1
        end_flag = 1
    elif sum_val > m:
        sum_val -= data[start]
        start += 1
        start_flag = 1
    elif sum_val == m:
        print('>>find!')
        result += 1
        end += 1
        end_flag = 1

print(result)

'''
n, m = 5, 5 # 데이터 개수:n, 부분연속수열의 합: m
data = [1,2,3,2,5]

result = 0
sum_val = 0
end = 0

for start in range(n):
    # end를 가능한 만큼 이동시키기
    while sum_val < m and end < n:
        sum_val += data[end]
        end += 1
    # 부분합이 정확히 m일때 카운트 증가
    if sum_val == m:
        result += 1
        print('현재 인덱스: start, end=', start, end)

    # 다음 start넘어가기 전에 data[start]를 sum_val에서 빼주기 
    sum_val -= data[start]

print(result)
'''

 

 

 

문제2) 구간 합 빠르게 계산하기 ( 시간제한: O(n+m) )

ex) [10,20,30,40,50]에서 Left와 Right정보가 들어왔을때 구간합 계산하기

 

Prefix Sum을 활용한 알고리즘 코드

n = 5 # 데이터 개수:n
data = [10,20,30,40,50]

# Prefix Sum 배열 계산후 저장
sum_val = 0
prefix_sum = [0]
for a in data:
    sum_val += a
    prefix_sum.append(sum_val)

# left = 2, right=4 일때 구간 합 계산 ?
left = 2
right = 4

print(prefix_sum[right] - prefix_sum[left-1])

▶ 문제 : https://www.acmicpc.net/problem/2252

 

2252번: 줄 세우기

첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이��

www.acmicpc.net

 

▶ (참조)위상 정렬 : https://blog.naver.com/ndb796/221236874984

 

25. 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ...

blog.naver.com

 (참조)deque 사용법 : https://dongdongfather.tistory.com/72

 

[파이썬 기초] 스택과 큐의 기능을 한번에 deque

deque는 스택과 큐의 기능을 모두 가진 객체로 출입구를 양쪽에 가지고 있다. 스택처럼써도 되고, 큐처럼 써도 된다. 여러가지 메서드를 이용해서 이런 기능을 구현한다. 먼저 deque를 만들어보자 >>> from collec..

dongdongfather.tistory.com

▶ 코드

# 위상 정렬 - 사이클이 없어야 가능하다.
# 단계1) 진입차수가 0인 정점들을 큐에 삽입한다.
# 단계2) 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
# 단계3) 간선 제거 이후에 진입차수가 0 이 된 정점을 큐에 삽입한다.
# 큐가 빌 때까지 단계2~3을 반복한다.
# 모든 원소를 방문하기전에 큐가 빈다면 사이클이 존재하는것이다.

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())

dq = deque()
indegree = [0]*(n+1) # 진입차수 (노드 : 1~N)
tree = [[] for i in range(n+1)] # 트리 구조 (노드 : 1~N)
result = []

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    indegree[b] += 1
#print('tree=', tree)
#print('indegree=', indegree)

# 단계1
for i in range(1,n+1):
    if indegree[i] == 0:
        dq.appendleft(i)
#print('dq=', dq)

# 큐가 빌 때까지 단계2 ~ 3 을 반복 
while dq:
    a = dq.pop() # 단계2
    result.append(a)
    for b in tree[a]:
        indegree[b] -= 1
        if indegree[b] == 0: # 단계3
            dq.appendleft(b)
#print('result=', result)

for a in result:
    print(a, end=' ')