서론 올해 초부터 어느정도 적당한 난이도 이상의 코딩테스트들에 응시하고 있는데, 항상 5번문제는 MST관련 문제가 나왔다. 조금만 변형되어도 풀기가 애매해질 정도로 얕은 정도로만 학습을 한 상태였기 때문에, 복기를 위해 관련된 것들을 학습하려고 한다. Union Find Disjoint Set(서로소 집합)을 관리하는 데 사용되는 알고리즘으로, 각 집합의 대표 요소를 통해 집합을 식별한다. 대표 요소를 해당 집합의 부모라고도 부르며, 루트로 표현된다. 일반적으로 작은 번호를 부모로 정하는데, 이는 트리의 높이를 최소화하여 연산의 효율성을 높일 수 있다. 여러 노드가 존재할 때, union과 find 연산을 수행한다. Union : 노드를 연결 Find : 특정 노드의 루트 노드를 찾음 예제 원소 A B ..
Solving Questions With Brainpower - LeetCode Can you solve this real interview question? Solving Questions With Brainpower - You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri]. The array describes the questions of an exam, where you have to process the qu leetcode.com 풀이 DFS를 이용해서, 해당 칸을 탐색할 수 있을 경우 탐색해서 모든 경우의수를 구한다음 최대값을 구하는 단순 DFS문제라고 생각했다. class ..
https://leetcode.com/problems/spiral-matrix-ii/ Spiral Matrix II - LeetCode Can you solve this real interview question? Spiral Matrix II - Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order. Example 1: [https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg] Input: n = 3 O leetcode.com 풀이 방향에 대한 변수와, 한 칸씩 체크해줄 변수를 지정해 준 뒤, 카운팅만 잘 해주면 되는 문제였..
https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 Stack을 활용 ( 정리 링크 ) Stack 후입선출(LIFO - Last In First Out)의 구조이다 ex) 음료수 진열대 사용하기 import java.util.Stack; Stack stack = new Stack(); // 값 추가하기 stack.push(1); stack.push(2); stack.push(3); // 맨 위에 있는 데이터(top)를 가져옴 mag1c.ti..
https://school.programmers.co.kr/learn/courses/30/lessons/140108 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 f - 첫 문자 나온 횟수 l - 뒤의 문자들이 나온 횟수 left - charAt돌릴 시작지점 right - 비교할 char public int solution(String s) { int answer = 1; int f=1; int l=0; int left = 0; int right = 1; while(right < s.length()) { if(f == l) { left = right..
https://school.programmers.co.kr/learn/courses/30/lessons/142086 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 단순 String 메서드 활용 class Solution { public int[] solution(String s) { int[] answer = new int[s.length()]; answer[0] = -1; for(int i=1; i
https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 p의 길이, 즉 최대 18자리숫자이기 때문에 int가 아닌 Long타입으로 풀이. public int solution(String t, String p) { int answer = 0; Long pInt = Long.parseLong(p); for(int i=0; i= tss) { answer++; } } return answer; }
https://school.programmers.co.kr/learn/courses/30/lessons/155652# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 풀이 마지막 1레벨이라 빨리 풀고 2레벨 풀고 오랜만에 3레벨도 해야지~ 하다가 1시간이나 잡아먹었다... public String solution(String s, String skip, int index) { String answer = ""; char[] chArr = s.toCharArray(); for(int i=0; i