본문 바로가기

알고리즘 문제/Programmerse42

[Programmers] 행렬 테두리 회전하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/77485 1부터 차례대로 세팅된 rows x columns 크기의 배열(let, array)을 먼저 만든다. 이제 행렬을 직접회전하면서 최소값을 저장한다. x1 < x2, y1 < y2 이므로 배열크기를 벗어날 걱정없이 시작 이전 변수(let, before)은 array[x1+1][y1]으로 세팅한다. 회전은 위 순서대로 회전시킨다. 먼저 행을 x1으로 고정시킨 뒤 탐색하는 배열에 before값을 넣고 갱신되기 이전값으로 before 변수를 갱신한다. 다음은 열을 y2로 고정시킨 뒤 탐색하면서 배열값을 갱신시킨다. 이 때, 중복해서 값을 갱신시키면 안되므로 (x1, y2)는 갱신대상에서 제거시켜야 한다... 2021. 5. 31.
[Programmers] 로또의 최고 순위와 최저 순위 문제 : https://programmers.co.kr/learn/courses/30/lessons/77484 lottos 문자열에서 0인 개수를 wrongCnt 변수에 저장하고 0이 아닌 수들 중 로또번호에 포함되는 수의 개수를 matchCnt 변수에 저장한다. 최고등수가 되는 경우는 알수없는 번호(0인 수들)들이 모두 로또 당첨번호인 경우이다. 즉, matchCnt + wrongCnt 가 당첨번호의 개수인 등수를 구하면 된다. 최저등수가 되는 경우는 알수없는 번호들이 모두 로또 당첨번호가 아닌 경우이다. 즉, matchCnt가 당첨번호의 개수인 등수를 구하면 된다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Dev-matc.. 2021. 5. 31.
[programmers][월간 코드 챌린지 시즌2] 2개 이하로 다른 비트 문제 : https://programmers.co.kr/learn/courses/30/lessons/77885 xxxx0 -> xxxx1 만약 마지막 비트가 위와 같이 0 이라면 마지막 비트만 1로 바꾸면 정답을 구할 수 있다. 마지막 비트가 0인경우는 짝수인 수이므로 numbers[i]가 짝수인 경우 + 1이 정답이된다. 문제는 마지막 비트가 1인 홀수인 경우이다. 1000111 를 예로 들어보자. 홀수인경우는 0인 비트 중 최하위 비트를 찾는다. 위 경우엔 8에 해당하는 오른쪽에서 4번째 비트가 이에 속한다. 정답이 되는 비트는 1001011 이다. 즉, 0인 비트중 최하위비트는 1로 바꾸고 그 다음 비트는 0으로 바꿔주면 정답을 구할 수 있다. numbers[i]보다는 커야하고(조건 1) 최대 2개.. 2021. 5. 15.
[programmers][월간 코드 챌린지 시즌2] 약수의 개수와 덧셈 문제 : https://programmers.co.kr/learn/courses/30/lessons/77884 left, right가 최대 1000개므로 그냥 1부터 right까지 수들을 탐색하면서 탐색 중인 수가 left ~ right 의 약수인지 2중 for문을 돌려가며 판단한다. 약수의 수를 저장해야 하므로 right-left+1 크기의 배열도 필요하다. 탐색이 모두 끝나면 left~right들의 약수 개수가 짝수면 더하고 홀수면 뺀 결과를 반환한다. 시간복잡도는 O(right * (right-left+1)). 더 좋은 방법이 있을거 같아서 고민하다가 공식 풀이에 들어가서 지니어스한 방법을 알게되었다. 중요 아이디어는 약수가 홀수개란 뜻은 25와 같이 제곱수라는 뜻이다. 따라서 left ~ righ.. 2021. 5. 15.
[programmers][월간 코드 챌린지 시즌2] 모두 0으로 만들기 문제 : programmers.co.kr/learn/courses/30/lessons/76503# 연결된 두 점의 한 쪽은 +1, 다른 한 쪽은 -1을 하면 플마제로이기 때문에 결국 모든 노드의 가중치들의 합은 유지된다. 따라서 모든 노드들의 가중치 합이 0가 되지 않는다면 -1을 반환한다. 모든 노드들의 가중치 합이 0이 아니라면 가중치를 0으로 만드는 것은 가능하다. 임의의 노드를 루트노드라 가정하고 해당 노드로 다른 모든 노드들의 가중치를 루트노드로 이동시켜보자. [그림 1]은 가중치 0을 가진 노드를 루트노드라 가정하여 다른 노드들의 가중치를 순수하게 옮긴다고 가정했을 때의 이동횟수이다. 예를 들어 3 노드의 가중치를 0 노드로 옮길 때 -1 노드를 거치지만 단순히 거쳐가는 노드로만 사용된다. 총.. 2021. 4. 17.
[programmers][월간 코드 챌린지 시즌2] 괄호 회전하기 문제 : programmers.co.kr/learn/courses/30/lessons/76502 문자열 길이는 1,000으로 그다지 길지않다. 가능한 모든 문자열을 구해서 각 문자열들이 올바른 괄호문자열인지 판단 후 올바른 괄호문자열의 수를 센다. 올바른 괄호문자열은 문자열을 앞에서부터 탐색하면서 열린괄호라면 스택에 넣는다. 만약 닫는 문자열이 나왔다면 stack이 비어있지 않고 stack의 top에 있는 괄호와 올바른짝이라면 올바른 괄호짝이므로 stack을 pop해주고 다음 문자를 탐색해나간다. 만약 닫는 문자열이 나왔는데 stack이 비어있거나 (ex, ] ) 올바른 괄호짝이 아니라면 (ex, ((] ) 올바른 괄호문자열이 될 수 없다. 모든 문자열을 탐색했을 때 스택이 비어있다면 올바른 괄호 문자열.. 2021. 4. 17.