코딩 테스트/프로그래머스
프로그래머스 - 행렬 테두리 회전하기 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/77485?language=java 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 직사각형 전체를 map으로 두고 순서대로 변경해가면되는 구현문제 퀴리가 0, 0 위치를 1, 1로 시작하기 때문에 map의 가로 세로를 +1씩하여 생성 x축,y축으로 이동해야하는 거리를 구함(xMove, yMove) 시계방향으로 회전 // 프로그래머스 행렬 테두리 회전하기 문제 class Solution { static int[][]..
프로그래머스 - 헤비 유저가 소유한 장소 (SQL)
programmers.co.kr/learn/courses/30/lessons/77487 코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr 총 3가지 방식으로 풀어 보았습니다. 1. 집계함수 COUNT + PARTITION BY 실행계획을 보면 메인 쿼리와 서브 쿼리 둘다 인덱스를 타지 않고 풀스캔을 하고 둘다에서 filesort가 발생한다. 3가지 방법 중 성능이 가장 별로일거라고 생각이 든다. SELECT PL.ID, PL.NAME, PL.HOST_ID FROM..
프로그래머스 - 점프와 순간 이동 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 개념만 떠올리면 간단하게 해결할 수 있는 문제 특정지점에 도달하기 까지 이상적인 경우는 그 지점의 절반 위치에서 순간이동을 하는 것이다. 순간이동으로 도착하지 못하는 경우만 건전지를 사용하면 된다. 문제의 예시인 5를 보면 5의 절반은 2.5로 나누어 떨어지지 않기 때문에 4에서 건전지를 1만큼 사용해서 이동 4의 절반은 2로 나누어 떨어지기 때문에 2..
프로그래머스 - 스티커 모으기(2) 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 이문제는 첫번째 스티커부터 뜯는 경우와 두번째 스티커부터 뜯는 경우의 dp를 이용해서 해결할 수 있습니다. 점화식은 DP[N] = MAX(DP[N-1], STICKER[N] +DP[N-2]); dpOne은 첫번째 스티커부터 뜯기 때문에 dpOne[0], dpOne[1]은 첫번째 스티커를 뜯는 경우가 됩니다. dpTwo은 첫번째 스티커부터 뜯기 때문에 dpTwo..
프로그래머스 - 모두 0으로 만들기 (자바)
programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 이문제는 위상정렬을 이용해서 풀수 있습니다. 우선 모든 가중치의 합이 0이 안되면 불가능함으로 -1을 리턴 edges를 순회하면 graph에 양방향으로 간선을 연결해주고 간선에 연결된 두개의 노드를 +1해주면서 각 노드의 진입차수를 셋팅합니다. 큐를 만들어서 진입차수가 1인 노드들을 넣어줍니다. 진입차수가 1이라는 의미는 연결된 노드가 하나라는 의미로 모든 ..
프로그래머스 - 괄호 회전하기 문제
programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 스택을 통해서 풀이를 진행하였습니다. 간단하게 설명하자면 문자가 (, {, [ 이면 stack에 추가 하고 아니면 앞서 stack 에 넣은 값이 반대방향의 괄호가 아니라면 return false; 맞으면 넣은 값을 pop함 마지막에 stack이 비어야 return true 이유는 (, {, [ 가 더 많이 존재하면 stack에 값이 남아 있게 되기 때문에 쌍이 딱 맞다면 스택의 길이는 0이 된다. import java.util.*; class Solution { public int solution(String s) { int answer = 0; Str..
프로그래머스 - 짝지어 제거하기 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 스택을 이용하면 O(N) 시간복잡도로 풀수있어서 효율성까지 통과할 수 있는 문제 스택을 써야지라는 생각을 해내는게 이 문제의 핵심이다. 비어 있거나 스택 맨 위 값과 같지 않은 경우는 추가 비어 있지 않고 스택 맨 위 값과 같은 경우는 맨 위 값을 pop baabaa를 처리할때 stack의 상태를 보면 [b] -> [b a] -> [b] -> [] -> [a] -..
프로그래머스 - 방문 길이 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/49994?language=java 코딩테스트 연습 - 방문 길이 programmers.co.kr 문제 해결 포인트는 A지점 -> B지점이면 B -> A가 이미 가본길이라는 것이다. 그래서 A -> B로 처음 갈때 count + 1을하고 A->B와 B->A 두 경우를 방문처리한다. 이를 위해서 visited[][][][] 와 같은 boolean 배열을 사용하였다. 배열에 음수를 사용할수 없으니 전체 좌표를 0부터 10까지를 잡고 시작점을 5,5로 잡았다. class Position { private int x; private int y; public Position(int x, int y) { this.x = x; this.y ..