crablo

해당 문제를 보고 아래와 같이 코드를 짰다. 하지만 제출 시 시간초과로 계속 실패했다. 그래서 원인이 뭔지 블로그를 검색하다 나와 비슷하게 코드를 작성하신 분이 계셨다. https://everyday-develop-myself.tistory.com/96 시소 짝궁 - Kotlin https://school.programmers.co.kr/learn/courses/30/lessons/152996#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 everyday-develop-myself.tistory.com 이분과 나의 공통점은 문제를 시간복잡도 O(N²)로 풀었다는 것이다. 하지만 실패 이후에 " 브루트 포스를 ..

해당 문제를 보고 대각선을 그었을때, 전체 사각형의 갯수에서 없어지는 사각형의 갯수를 빼면 정답이 되었기때문에 그부분을 캐치하고 바로 문제를 풀었다. 먼저 전체 사각형의 갯수는 w*h 이다 그리고 " w+h - w와 h의 최대공약수 " 이렇게 해주면 대각선에 따라 자르면서 생기는 비정사각형의 수를 나타낼 수 있다. 결론적으로 코드는 아래와 같이 짰다.

이 문제는 주어진 격자 형태의 대기 공간에서 사람들이 적절한 거리에 앉아 있는지 확인하는 알고리즘을 구현하는 것이다. 먼저 5 x 5 격자 형태의 대기 공간이 있는데 각 셀은 다음과 같이 3가지 유형 중 하나일 수 있다. 'P' : 사람이 앉아 있는 곳 'O': 빈 자리 'X' : 파티션으로 구분된 자리 규칙은 다음과 같다. 1. 두 사람 사이에는 최소한 하나의 빈 자리가 있어야 한다. 이 규칙은 수평, 수직, 대각선 방향으로 적용된다. 2. 파티션('X')으로만 분리되어 있는 경우, 두 사람 사이의 거리가 어떤 경우에도 상관 없다. 나는 해당 문제를 해결하기위해 다음과 같은 과정을 생각했다. 1.각 대기 공간에 대해 반복하면서 사람들의 위치를 확인한다. 2. 각 사람의 위치에서 bfs(너비 우선 탐색)..

해당문제를 풀면서 노트에 그려보면서 문제를 이해했다. a와 b는 0,1,2,3,4... 이렇게 1씩 차이나는 수열이라고 생각한다면 주어진 k와 d를 이용해서 점을 찍어나가면 a*k => x축방향 b*k => y축방향 이때 d의 거리 반경 내에 있어야한다. 그래서 d = 4라고할때 위의 사진처럼 좌표를 4이내로 찍었다. 그랬더니, 결과적으로 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍었다. 그래서 코드상에서는 x축방향으로 0부터 d 범위까지 k 만큼 건너뛰면서 점을 찍는다고 생각했고, 마찬가지로 y도 0부터 d범위까지 k만큼 건너뛰면서 점을 찍는다고 생각했다. 다음과 같이 코드를 작성하였으나 시간초과로 실패하였다. 아무리 풀어도 ..

해당 문제는 DFS를 사용하여 그래프를 탐색하고 두 부분으로 분할하고 각 부분의 노드 수를 계산한다. 각 전송선을 하나씩 제거하고 파티션 크기를 다시 계산한다. 제거 후 파티션 크기 간의 최소 절대 차이를 확인하여 발견된 가장 작은 차이를 반환한다. ※DFS(depth-first search) : 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 나는 아래와 같은 로직으로 문제를 해결했다. 1. 그래프 표현: 처음에는 인접 목록이나 인접 행렬을 사용하여 그래프를 나타낸다. 이 표현을 사용하..

문제를 보고서 1차원 배열을 2차원배열로 바꿀 생각을 했다. 코드는 아래와 같이 작성했다. import java.util.LinkedList import java.util.Queue class Solution { private val dx = arrayOf(0, 1, 0, -1) private val dy = arrayOf(1, 0, -1, 0) // 미로의 각 칸에 적힌 숫자의 합을 계산하여 반환하는 함수 fun solution(maps: Array): IntArray { val r = maps.size val c = maps[0].length val visited = Array(r) { BooleanArray(c) } // 각 칸의 방문 여부를 저장하는 배열 val answer = mutableLis..

해당 문제를 읽고나서 queue1의 총요소합과 queue2의 총 요소의 합이 짝수가 아니라면 합을 동일하게 만들 수 없는 생각을 했다. 그래서 코드는 아래와 같이 작성했다. class Solution { fun solution(queue1: IntArray, queue2: IntArray): Int { //두 큐의 총 합을 계산 var sum1 = queue1.sum() var sum2 = queue2.sum() //두 큐의 합이 짝수가 나오지 않는다면 합을 동일하게 만들 수 없으므로 -1 반환 if((sum1+sum2)%2 != 0 ){ return -1 } //queue1과 queue2의 목표 합계 val targetSum = (sum1+sum2)/2 var count = 0 var idx1 = 0 ..

해당 문제는 특정한 합을 가지는 부분 연속 수열을 찾는 문제이다. 해결방법은 투포인터 알고리즘을 해결했다. 일반적인 로직은 아래와 같다. 1.시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다. 2. 현재 부분 합이 주어진 합 k와 같다면 카운트한다. 3. 현재 부분합이 k보다 작다면 end를 1증가시킨다. 4. 현재 부분합이 k보다 크거나 같다면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2~4번 과정을 반복한다. 나는 아래와 같이 코드를 작성했다. class Solution { fun solution(sequence: IntArray, k: Int): IntArray { var start = 0 // 시작 포인터를 초기화. var end = 0 // 끝 포인터를 초기화. var ..

해당문제를 풀때, 문장이 길지 않아서 쉽게 풀릴것으로 예상했지만, 내 예상이 맞질 않았다. 처음에는 간단히 주어진 number를 CharArray로 바꾸고 나눌생각만했는데, 문제를 풀다보니 k를 제거하는것이어서 다시 문제를 읽고 해결했다. number을 문자타입의 배열로 변환 후 해당 문자들을 하나씩 꺼내서 결과적으로 가장 큰 수를 만들어내면 되는것 같았다. 문제를 푼과정은 다음과 같았다. 1. number의 형을 배열로 변환한다. 2. 스택초기화: 문자형타입의 스택을 초기화해서 결과를 담으려고했다. 3. 숫자 순회: 코드가 입력 숫자의 각 자릿루를 반복하면서 각 숫자에 대해 스택의 맨 위 숫자가 현재 숫자보다 작고 아직 제거할 수 있는 횟수가 남아있는 경우, 스택에서 숫자를 제거한다. 4. 스택에 숫자..

해당 문제를 보자마자 설명보단 그림에 집중하게되었다. 해당 그림을 보면, 2차원 행렬을 사분면으로 나누고 각각의 작은 사각형에서 모두 값이 일치하면 해당값으로 묶어버리고 , 그 후 일치하는 사각형은 제외하고 나머지 작은 사각형을 또 사분할하여 일치하는 요소가 있는지 확인 후 각각의 사각형의 크기가 1x1이 될때까지 반복하는 작업을 하면 될것 같았다. 로직은 알지만.. 코드를 짜는게 어려웠다. 그래서 블로그에서 검색하였고, 대부분 dfs 로 해결하는것을 확인하였다. dfs 알고리즘은 거의 재귀호출과 for문을 이용한다고하여 그대로 적용했다. 함수는 compress(주어진 배열을 재귀적으로 압축하는 역할) 와 checkUniform(주어진 사분면이 모두 같은 값을 가지는지 확인) 두 함수를 사용했다. com..