알고리즘/프로그래머스
프로그래머스 - (Java)입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 1. 유형 이분탐색 2. 시뮬레이션 이분탐색과 수학적 지식이 있어야 풀 수 있는 문제다. 우선 시뮬레이션일 돌려보자. 그렇다면 위의 과정에서 28은 어떻게 구해야할까. 이분탐색이다. 로직 먼저 head, tail의 초기값을 설정 head가 tail보다 커질때까지 반복문을 돌린다 조건에 따라 mid값을 변경해준다. 3. 코드 class Solution { publi..
프로그래머스 - (Java) 경주로 건설
https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 1. 유형 DP, BFS 2. 로직 테스트 케이스가 약간 빈약한것 같다. 반례가 존재하..
프로그래머스 - (Java) 보석쇼핑
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 1. 유형 해쉬맵, 큐 2. 로직 총 보석의 종류를 파악 해쉬맵에서 {보석이름, 개수}형태로 딕셔너리 생성 투포인터를 사용해서 모든 종류의 보석을 포함하고 있는 범위를 구함 gems가 아래처럼 주어졌다고 할때, ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 위의 그림처럼 시뮬레이션을 하면 start=3, end=4가 된다. 위의 방법처럼..
프로그래머스 - (Java)단체사진 찍기
https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 1. 유형 구현, 순열 2. 로직 순열 구하기 사람들끼리의 거리를 구한다 data배열의 조건대로 내가 구한 순열이 만족한지 판단 각 사람들끼리 떨어진 거리는 String.indexOf를 사용해서 쉽게 구할수 있었다. 3. 코드 class Solution { static char info[] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', '..
프로그래머스 - (Java)땅따먹기
https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 1. 유형 동적프로그래밍 2. 로직 그림으로 이해 제한 조건을 잘 읽어보면 N이 100,000씩 되는걸 확인 가능하다 이러면, 부르트포스로는 4*3^(n-1)시간이 걸리고 시간초과로 실패가 뜰것이다. 제한조건을 잘 읽어보고 푸는 습관을 들이자 3. 코드 import java.util.*; class Solution { int solution(..
프로그래머스 - (Java) 괄호 회전하기
https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 1. 유형 구현, 문자열, 스택 2. 로직 문자열 회전하는 코드 올바른 괄호인지 판단 [](){}문자열을 회전하면 ](){}[이 된다. 이런 문자열을 만드려면 덱 자료구조를 사용한다. 맨 앞의 엘리먼트를 빼고 맨 뒤에 추가해준다. 이것을 s의 길이만큼 반복해준다. 올바른 괄호판단은 너무 흔한 유형이고, Stack을 사용해서 판단한다 닫는 괄호가 나왔을때, stack의 맨 위의 엘리먼트가 한쌍을 이루는지 판단 만약 닫는 괄호인 경우, stack이 비어있거나, 쌍이 맞지 않으면 틀린 문자열이 된다. 3. 코드 import java.util.*..
프로그래머스 - (Java) 프렌즈4블록
https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 1. 유형 시뮬레이션 2. 로직 1) 2*2부분 빈칸으로 바꾸기 2) 빈칸만큼 아래로 내리기 3) 위의 조건을 반복 이 문제에서 그나마 구현이 어려운 부분이 빈칸만큼 내리는 코드다. 3. 코드 import java.util.*; class Solution { static char table[][]; static boolean visited..
프로그래머스 - (Java) 방금 그곡
https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 1. 유형 문자열 2. 로직 musicinfos를 파싱해야한다 시작시간, 끝난시간, 곡이름, 악보 순서로 배열을 만든다 플레이 시간 만큼 악보 늘리기 m이 악보에 포함되는지 슬라이딩 윈도우로 판단 나중에 굳이 슬라이딩 윈도우 말고, String에 contains라이브러리가 있었음 정답을 리스트에 넣고 기준에 따라 정렬 3. 풀이 문자열 파싱을 끝낸후..
프로그래머스 - 베스트앨범
https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 1. 유형 해시, 정렬 2. 풀이 1) dictionary[장르] = 조회수 형태로 맵을 만듬 2) lists[장르] = [(조회수, 고유번호)] 형태로 맵을 만듬 3) dictionary를 조회수 기준 내림차순 정렬 4) lists를 조회수 기준 내림차순, 고유번호 오름차순으로 정렬. 단, 2개 까지만 조회 3. 코드 def solution(genres, p..
프로그래머스 - 가장 먼 노드
https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1. 유형 그래프 2. 풀이 1) 인접리스트 생성 2) BFS돌리면서 거리까지 저장. [노드, 이동한 거리] 형태로 큐에 저장 3) 가장 먼 노드의 갯수 카운트 3. 코드 from collections import deque def solution(n, edge): answer = 0 lists= [ [] for _ in range(n+1)] dists = [ 0 for _ in range(n+1)] for u,v in edge: ..
프로그래머스 - 기지국 설치
https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 1. 유형 구현 2. 풀이 1) station의 요소별로 왼쪽 끝과 오른쪽 끝을 구함 2) 그러면 위 처럼 빨간색의 범위를 아는게 가능 3) 기지국의 범위는 w*2+1이다. 이것이 빨간색에 몇개 설치되는지 구할수있음 3. 코드 def calc(mok, na): if mok>0 and na>0: return mok+1 elif mok>0 and..
프로그래머스 - 키패드 누르기
https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 1. 유형: 구현, 딕셔너리 2. 풀이: 1) 1 (0,0) 2 (0,1) 3 (0,2) 4 (1,0) 5 (1,1) 6 (1,2) 7 (2,0) 8 (2,1) 9 (2,2) * (3,0) 0 (3,1) # (3,2) 위 같은 형식으로 딕셔너리 만듬 2..
프로그래머스 - (python) 배달
https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 1. 유형 그래프 2. 알고리즘 다익스트라 3. 풀이 기본적인 다익스트라 구현이다. 1) 인접리스트 만들기 2) 다익스트라 포멧에 맞게 작성 코드. import heapq import sys def solution(N, roads, K): answer = 0 pq = [] list = [[] for _ in range(N+1) ] vis..
프로그래머스 - (Python)실패율
programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 1. 유형 구현 2. 자료구조 딕셔너리 3. 풀이 각 스테이지에 따른 실패율 구하기 1) {스테이지 : 실패한 횟수} 형식으로 딕셔너리 만들기 2) [실패율, 스테이지] 형식으로 리스트 만들기 3) 실패율 순으로 내림차순, 스테이지 오름차순 정렬 코드. def solution(N, stages): answer = [] dic = {} for stage in stages: if..
프로그래머스 - (Python, Java) 오픈채팅방
programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 1. 알고리즘 유형 Map 2. 자료구조 리스트, 딕셔너리 3. 풀이 Enter, Leave, Change에 따라 구분 1) [명령어, uid] 형식으로 리스트에 저장 uid에 따른 이름 저장 1) 딕셔너리에 {uid: 이름} 형식으로 저장 출력 기능 1) 리스트의 첫 단어(Enter, Leave)로 출력값 구분 2) 리스트의 두번째 단어로 이름 구분 풀이 def soluti..
프로그래머스 -(python) 전화번호 목록
programmers.co.kr/learn/courses/30/lessons/42577?language=python3 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 유형 - 해시 풀이 1 1 9 1 1 9 5 6 숫자가 '119' '11956'이 주어졌다고 했을때, - 내림차순 정렬 11965를 슬라이싱 한다. set 자료구조를 사용해서 11965, 1196, 119, 11, 1을 set에 넣는다 이제 다음 숫자인 119가 set에 포함되는지 아닌지를 알 수 있다. 따라서 다음 숫자가 set에 존재하면 ..
프로그래머스 - 영어 끝말잇기
programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 1. 유형 구현 2. 아이디어 HashSet 몫, 나머지 연산 3. 풀이 집중적으로 볼것은 규칙 4..
프로그래머스 - 최솟값 만들기
programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 접근법 - 정렬 풀이 첫번째 시도) 재귀로 모든 경우의 수를 전부 탐색해서 풀었지만 시간초과. 두번째 시도) 최종 누적함이 최소인 경우는, 최댓값과 최솟값을 더한 경우이다. 따라서 A는 오름차순 정렬, B는 내림차순 정렬을 통해 최소,최대를 더하는 식으로 풀이를 해주었다. 코드 재귀 - (시간초과) class Solution { static boolean..
프로그래머스 - 튜플프로그래머스 - 튜플
programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 1. 유형 튜플 2. 풀이 문자열 파싱 HashMap 횟수 순으로 정렬 - 문자열에 {} 와 콤마가 들어있어서 전처리를 해준다. - 맨 처음 튜플을 알기 위해서 각 요소에서 숫자가 얼마나 나오는지 확인해야한다. {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 예시에서 2가 4번, 1이 3번, 3이 2번,..
프로그래머스 - 소수 찾기(level2)
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 1. 유형 순열, 수학 2. 접근법 순열 소수 판단 011같은 수 예외처리나 중복체크 3. 풀이 - 종이조각을 붙여서 다양한 경우를 만들어야 한다. 이때, 순서도 상관이 있으므로 순열을 구한다. 일반적으로 길이가 고정된 순열이 아니다. 길이가 유동적인 순열이므로 이점이 다른 순열문제와 차별점이라 생각한다. 그러므로 조합+순열 느낌이 나는 문제였다. - 소수판단은..