개발하는 고라니

코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr [문자열, Stack] Stack 자료구조를 간단하게 배열로 만들어 사용하였다. 컬렉션에 비해 가볍고 사용법도 어렵지 않으므로 개인적으로 좋다고 생각한다. 주어진 문자열 s를 char[]로 변환하고, 한 문자씩 스택에 넣는다. 단, 넣기 전에 이미 스택에 들어간 맨 위의 문자와 비교를하고, 같다면 push를 하지않고 스택에 있는 것을 하나 빼고(pop), 같지 않다면 push한다. 짝지어 제거하기를 완료할 수 있는지에 관한 조건은 stack의 top..

2020 Kakao Blind Recruitment 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr [문자열] 백준에 길들여지고, 카카오의 효율성 문제에 길들여진 나머지, 문자를 쪼개어 비교하는 것은 생각하지도 않았었다. 이는 간단하지만 시간이 상당히 오래 걸리는 작업이기 때문이다. 그래서 굳이 돌고돌아 조금더 어려운 방법이지만 빠른 방법이 뭐가 있을까 하다가 배열 스택을 생각해냈고, 이를 적용해 풀어보다가 도저히 아닌 거 같아 몇몇 게시글을 찾아보니 문자열을 쪼개 비교하는 것이 아닌가. 그래서 작성한..

코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr [3진수] 10진수를 3진수로 바꾸는 것인데, 3을 모두 4로 바꾸면 된다. 효율성을 체크하는 문제이므로 String을 사용하여 "+"를 쓰면 통과하지 못할 듯 하다. 그러므로 StringBuilder를 써서 문자를 붙여주도록 하자. 18(3) = 18 / 1 = 18 % 3 = 0 -> 3 15 / 3 = 5 % 3 = 2 9 / 9 = 1 % 3 = 1 # Code class Solution { public String solution(int n) { StringBuilder sb = new StringBuilder(); int div = 1; while(true){ int mok = n / div; if(mok == 0) bre..

코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [Floyd-Warshall] 플로이드 와샬 알고리즘을 수행해서, i번 사람이 j번 사람에게 직접/간접적으로 도달할 수 있는지 체크한 다음, i번 사람이 자기 자신을 제외한 모든 사람에게 도달할 수 있으면 순위를 확실히 알 수 있다. 문제에서 주어진 조건은 간선이 단방향이라는 것을 알려준다. 따라서 주어진 입력을 적절히 이용하여 직접적인 A와 B의 관계를 boolean[ ][ ]에 표현하고 플로이드 와샬을 수행하면, A가 C에게 도달 할 수 있는지 여부를 알 수 있다. 표를 보며 이해하면 더 쉽게 와닿을 수 있을 것이다. 주어진 입력으로 boolean[][] 배열을 지..

코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr [Dijkstra] 1번 정점에서 모든 정점까지의 최단 거리를 구해 dist[ ]에 저장 후, 1번 정점부터 n번 정점까지 dist[i]를 돌면서 dist[i]가 max인 곳의 정점 개수를 카운팅 한다. # Code import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; class Solution { static class Edge{ int tg, d; public Edge(int target, i..

코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers.co.kr Comparable 인터페이스를 구현한 Word라는 클래스를 만들었다. Comparable을 구현한 이유는 Collections.sort() 메서드를 사용하기 위해서이다. 보통 String이나 int같은 타입은 대소관계가 명확하지만, 이 문제같은 경우 주어진 문자열의 n번째 문자의 대소를 비교해야하기 때문에 일반적인 정렬로는 불가능하다. 따라서 Comparable을 구현하여 정렬의 기준을 커스터..

코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr [Kruskal 알고리즘] 입력으로 들어오는 land[ ][ ]의 각 원소에 인덱스를 부여했다. 이차원 배열에서 인덱스를 부여하는 방법은 (i * N) + j 이다. 이렇게 하면 0부터 N-1 * N-1까지 원소에 대해 인덱스를 부여할 수 있다. 이는 곧 정점을 정의할 수 있다는 것이므로 크루스칼 알고리즘을 수행하기에 더욱 수월해진다. 우선 이중 for문을 돌며 land의 각 원소에 대해 상..

코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr [Minimum Spanning Tree(MST), Kruskal 사용] 시작 정점, 도착 정점, 가중치 이렇게 3개의 멤버변수를 갖는 클래스 Edge를 선언하고 sort()를 이용하기 위해 Comparable 인터페이스를 구현한다. static class Edge implements Comparable{ int h, tg, d; public Edge(int home, int target, int dist){ h=home; tg=target; d=dist; } @Override public int compareTo(Edge o) { return d-o.d; }..