알고리즘/프로그래머스

    프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기
    알고리즘/프로그래머스

    프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기

    [문제 바로가기] 1. 유형 트리, union-find 2. 풀이 2-1. 해설 처음 접근법은 2가지 묶음으로 나눠야 합니다. 그러기 위해서 저는 Union-find를 사용했습니다. 시뮬레이션을 돌려봅시다. 예제1번에서 처럼 4-7간선을 지워봅시다. 그리고 union-find를 돌리면, 아래 그림처럼 배열이 초기화 될거에요. 그럼 1의 개수와 7의 개수의 차이를 구하면 끝! 이것을 간선의 수 만큼 반복해서 최소값을 구해줍니다. 3. 코드 import java.util.*; class Solution { static int p[], MIN=987654321; public int solution(int n, int[][] wires) { int answer = -1; for(int i=0; i

    알고리즘/프로그래머스

    프로그래머스 위클리 챌린지 5주차 - 모음 사전

    https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 1. 유형 완전 탐색 2. 문제 접근 총경우의 수가 5^5 + 5^4 + 5^3 + 5^2 + 5입니다. 그래서 완전 탐색을 돌릴 수 있다고 판단 모든 경우의 수를 List에 넣고 word와 같은 값을 찾아줬습니다. 다른 풀이를 보니 규칙을 찾아서 간단하게 풀 수도 있는거 같습니다. 3. 코드 import java.u..

    프로그래머스 - 메뉴 리뉴얼
    알고리즘/프로그래머스

    프로그래머스 - 메뉴 리뉴얼

    https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 유형 브루트포스, 부분집합 문제분석 orders의 요소별로 모든 조합의 갯수를 구해줍니다. 1번 태스트케이스를 예시로 보면, ABCFG에서 course의 길이가 2, 3, 4니깐 각 길이에 맞는 조합을 모두 구해줍니다. 그리고 HashMap자료구조를 통해 {문자열: 갯수} 형태로 넣어줍니다. 코드를 보면 현재 인덱스를 선택하고, 인덱스+1로 재귀를 호출함으로써 중..

    알고리즘/프로그래머스

    [devmoon] 프로그래머스 - (Java) 소수 만들기

    https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 1. 유형 수학, 조합 2. 시뮬레이션 에라토스테네스의 체 소수판단 조합 배열에서 3개를 선택하면 그 합이 소수인지 판단하면 된다. 소수판단은 효율성을 생각해서 에라토스테네스의 체를 사용한다 3. 코드 class Solution { static boolean matrix[]; static int Nums[]; static int ans=0; ..

    [devmoon]프로그래머스 - (java)합승 택시 요금
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - (java)합승 택시 요금

    https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 1. 유형 플로이드-와샬, 최단거리 탐색 2. 시뮬레이션 노드의 개수 N이 최대 2..

    [devmoon]프로그래머스 - (Java) 섬 연결하기
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - (Java) 섬 연결하기

    https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 1. 유형 그리디 2. 시뮬레이션 이번 문제는 프림, 크루스칼을 사용하여 해결가능하다. 이전에 크루스칼을 사용했으니, 이번엔 프림을 사용한다. testcase에 대한 시뮬레이션 아래도 마찬가지로 0,1번 노드와 연결된 가장 작은 간선을 선택 최종값은 아래와 같이된다. 3. 코드 import java.util.*; class Solution { static PriorityQueue pq; static List list[]; public int solution(i..

    [devmoon]프로그래머스 - (Java)외벽 점검
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - (Java)외벽 점검

    https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 1. 유형 구현 2. 시뮬레이션 1. 한점을 선택 2. 가장 먼 곳을 탐색할 수 있는 사람부터 사용 3. 모든 weak를 탐색할 수 있을때까지 위를 반복 위 처럼 시뮬레이션을 돌리면, 가장 먼저 1을 선택 후, 2가지 경우의 수가 나온다. 9 선택하는 경우 -> 5만큼 탐색하면 모든 weak탐색가능 ->2명 필요 10 선택하는 경우 -> 5만큼 탐색해도 9번은 ..

    [devmoon]프로그래머스 - n진수 게임
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - n진수 게임

    https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 1. 유형 재귀, 구현 2. 시뮬레이션 0부터 수를 1씩 증가 수를 n진법으로 전환 튜브의 순서에 맞는 변환된 n진법수를 선택 위를 튜브가 t개 선택할 때까지, 반복 3. 코드 - 이진법 전환 코드 - 탐색코드 class Solution { public String solution(int n, int t, int m, int p) { String..

    [devmoon] 프로그래머스 - (Java)이진 변환 반복하기
    알고리즘/프로그래머스

    [devmoon] 프로그래머스 - (Java)이진 변환 반복하기

    https://programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 1. 유형 재귀 2. 시뮬레이션 그냥 요구 조건대로 구현하면 될듯 3. 코드 import java.util.*; class Solution { public int[] solution(String s) { int[] answer = {}; List list = new ArrayList(); int zeroCount=0; int turnCount=0; while(!"1".equals(s)){ list.clear(); for(char c : s.toCharArray()){ if(c=='1'){ list.add(c); }else zeroCo..

    [devmoon] 프로그래머스 - (java)점프와 순간 이동
    알고리즘/프로그래머스

    [devmoon] 프로그래머스 - (java)점프와 순간 이동

    https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 1. 유형 재귀, 수학 2. 시뮬레이션 2가지 접근법 동적프로그래밍 수학 우선 DP를 이용한 풀이는 불가능. N이 10억으로 시간초과가 발생 따라서, 재귀+수학으로 풀이 아래와 같이 나머지가 1인 경우의 수를 세어주면 된다. 재귀 사용 3. 코드 import java.util.*; public class Solution { public i..

    [devmoon]프로그래머스 - 방문 길이
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - 방문 길이

    https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 1. 유형 구현 2. 시뮬레이션 한 점은 방문하는 방향에 따라 여러가지 경우의 수가 나옴. 따라서 3차원 배열을 활용해서 방문체크 'U'일때, 2가지 경우의 길에 대해서 방문체크를 해야한다. 3. 코드 import java.util.*; class Solution { static int D[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; static int N=10; static public int solution(String dirs) { int answer = 0; char arr[] = dir..

    프로그래머스 - JadenCase 문자열
    알고리즘/프로그래머스

    프로그래머스 - JadenCase 문자열

    https://programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 1. 유형 문자열 2. 시뮬레이션 모두 소문자로 변환 문자열을 탐색하면서, 공백 + 소문자인 경우 대문자로 전환 3. 코드 import java.util.*; import java.util.regex.*; class Solution { public String solution(String s) { Str..

    프로그래머스 - 압축
    알고리즘/프로그래머스

    프로그래머스 - 압축

    https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 1. 유형 해시맵 2. 시뮬레이션 딕셔너리에 등록되지 않은 가장 긴 문자열 탐색 등록되지 않은 문자열은 딕셔너리에 등록 문자열 끝까지 위를 반복 3. 코드 import java.util.*; class Solution { static List ans = new ArrayList(); static Map map = new HashMap(); static int index =27; sta..

    프로그래머스 - 이중우선순위큐
    알고리즘/프로그래머스

    프로그래머스 - 이중우선순위큐

    https://programmers.co.kr/learn/courses/30/lessons/42628# 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 1. 유형 우선순위큐 2. 시뮬레이션 우선순위큐에 [인덱스, 값] 형태로 집어 넣는다. 아래 처럼 내림, 오름 차순으로 우선순위큐를 선언 D가 나올때마다, 방문배열에 체크한다 따라서 max, min큐에서 방문 배열이 false인 것이 정답이다. 3. 코드 import java.util.*; class Solution { public int[] solution(String[] operations) { int[] answer = {0, 0}; PriorityQueue min = new PriorityQueue(new Comparator(){..

    프로그래머스 - 보행자 천국
    알고리즘/프로그래머스

    프로그래머스 - 보행자 천국

    https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 1. 유형 DP 2. 시뮬레이션 로직 맵을 완전탐색 한다. 현재의 칸에서 상, 좌를 확인한다 이전 칸이 0 OR 2에 따라 분기한다. 위의 그림의 공식대로 Dp에 저장 위를 n-1,m-1 좌표까지 반복 3. 코드 class Solution { int MOD = 20170805; public int solution(int m, int n, int[][] c..

    프로그래머스 - 단어변환
    알고리즘/프로그래머스

    프로그래머스 - 단어변환

    https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 1. 유형 DFS 2. 시뮬레이션 로직 완전탐색으로 1자리만 다른 단어가 있는지 탐색 DFS 3. 코드 class Solution { static int N, INF= Integer.MAX_VALUE; static boolean visited[]; static String[] Words; public int soluti..

    프로그래머스 - 셔틀버스
    알고리즘/프로그래머스

    프로그래머스 - 셔틀버스

    https://programmers.co.kr/learn/courses/30/lessons/17678# 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 1. 유형 구현 2. 시뮬레이션 로직 timetable을 모두 "분"으로 전환 후, 오름차순 정렬 버스에 m명까지 태우기 만약 m명 미만이다. 현재 버스시간이 정답 m명이다. 마지막에 탄 사람의 시간-1이 정답 분 -> 시 3. 코드 import ja..

    프로그래머스 - (Java) 가장 긴 팰린드롬
    알고리즘/프로그래머스

    프로그래머스 - (Java) 가장 긴 팰린드롬

    https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 1. 유형 문자열 2. 시뮬레이션 로직 총 길이 설정 시작 위치를 설정 양 끝에서 중앙으로 이동하면서 문자가 같은지를 판단 3. 코드 class Solution{ public int solution(String s) { int answer = 1; success:for(int len=s.length(); le..

    프로그래머스 - (Java)여행경로
    알고리즘/프로그래머스

    프로그래머스 - (Java)여행경로

    https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 1. 유형 DFS 2. 시뮬레이션 로직 Map 형태로 자료구조 사용 DFS사용하여 완전 탐색 3. 코드 풀이1 import java.util.*; class Solution { static int N; static List ret; static public String[] solution(String[][] tickets) { ..

    프로그래머스 - (Java)자물쇠와 열쇠
    알고리즘/프로그래머스

    프로그래머스 - (Java)자물쇠와 열쇠

    https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 1. 유형 구현 2. 시뮬레이션 위처럼 전체 맵을 만들고 key를 이동하면서 lock에 대입해보면서 판단한다. 로직 key가 평행이동할 전체 맵을 완전탐색한다 key를 90도 돌려준다 key와 lock이 맞는지 확인한다 3. 코드 class Solution { public boolean solution(int[][] key, int[][] lock) { boolean answer = false; int keyl..

티스토리툴바