본문 바로가기

대딩192

[프로그래머스 lv2] 조이스틱 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저, 조이스틱을 상하로 움직일 때 각 자리에서 필요한 이동 횟수를 쉽게 구할 수 있다. 조이스틱을 윗쪽으로 움직이는 방법과 아랫쪽으로 움직이는 방법 중에서 이동 횟수가 더 작은 방법을 선택하면 되기 때문에, 각각의 자리 name[i]에 대하여 min(name[i]-'A', 'Z'-name[i]+1) 을 더하면 된다. 문제는 조이스틱을 좌우로 움직이는 것인데, 결론부터 말하자면 연속된 'A' 구간을 찾고 해당 구간을 지나지 않는 이동 횟수 중에서 최솟값을 구하면 된다. 특정 인덱스 i에 대하여, i 이후로 'A'가 연속적으로 등장한 구간을 지난 포인트를 nexti라고 해보자. 이 때, A가 연속된 구간은 지나지 않아도 됨으로 다음 두가지 이동방법.. 2022. 8. 22.
[프로그래머스 lv2] [1차] 캐시 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 LRU(Least Recently Used) 는 정해진 캐시 사이즈가 다 찼을 때 가장 최근에 사용되지 않은 녀석(가장 옛날에 사용된 녀석)을 캐시에서 제거하고 새로운 녀석을 넣는 방법이다. 아래의 코드에서는 map을 이용하여 cache를 구현했는데, map의 key는 도시 이름, value는 가장 최근에 참조된 시간을 기록한다. cache에 이미 도시에 대한 정보가 들어있다면(cache hit), 총 실행시간에 1을 더하고 해당 도시의 최근 참조 시간을 변경한다. cache에 도시에 대한 정보가 없다면(cache miss) 총 실행시간에 5를 더한다. 이 때, cache가 꽉차있다면 가장 옛날에 참조된 도시(최근 참조 시간이 가장 작은 것)를 map.. 2022. 8. 22.
[프로그래머스 lv2] 두 큐 합 같게 만들기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 queue1과 queue2가 주어졌을 때, 각 원소의 합을 같게 만들기 위한 최소 이동(pop+insert) 횟수를 구하는 문제이다. 그리디적으로 생각해보면, queue1의 현재 원소합이 sum1이고 queue2의 현재 원소합이 sum2 일 때, 1) sum1 > sum2 이면 queue1의 원소를 queue2로 이동시키는 것이 유리하다. 2) sum1 < sum2 이면 queue2 원소를 queue1으로 이동시키는 것이 유리하다. 따라서, 반복적으로 두 큐의 원소 합을 비교하여 이를 같게 만드는데 유리한 방향으로 원소를 이동시켜나가면 된다. 이 때, 특정 횟수 이상으로 이동이 길어지면 두 큐의 합을 같게 만드는 것이 불가능하다는 이야기 이므로 반복문.. 2022. 8. 22.
[프로그래머스 lv2] 행렬 테두리 회전하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 (x1, y1)를 왼쪽 꼭짓점, (x2, y2)를 오른쪽 꼭짓점으로 하는 직사각형을 회전했을 때 회전하는 라인에 있는 최솟값을 모아 리턴하는 문제이다. 문제에서 주어진 대로 그대로 구현하면 AC를 받을 수 있다. 회전 방향에 0, 1, 2, 3의 인덱스를 부여하고, 각각의 방향에서 다음 블럭을 당겨오자. 아래의 코드에서는 0번 방향과 2번 방향일 때 h-1 만큼 당기고, 1번과 3번 방향일 때 w-1 만큼 당기도록 구현하였다. 블럭을 회전하며 가장 작은 숫자를 기록하고 이를 모은 벡터를 리턴하면 정답이다. 코드 #include #include #include #include #include #include #include #include #includ.. 2022. 8. 21.
[프로그래머스 lv2] 2개 이하로 다른 비트 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 자연수 x에 대하여 x보다 큰 수 중 2진수 비트가 1~2개만 다른 가장 작은 수를 구하는 문제이다. 규칙을 찾아보면, 1) 000...1000 과 같이 가장 마지막 자리가 0인 경우 이를 1로 바꾸면 된다. 2) 000...0111 과 같이 마지막 자리가 아닌 자리가 0인 경우, 가장 뒷자리 부터 0을 찾아 이를 1로 바꾸고 해당 자리의 다음자리를 0으로 바꾼다. 예를 들어, 000...0111 을 바꾸면 1011이 되고, 10진수 7에 대한 정답은 11이 된다. 10진수를 2진수 문자열로 바꾸어 연산할 수도 있지만, 비트 연산을 이용하여 간단히 구현할 수 있다. 가장 끝 0번 인덱스부터 각 자리를 추출하여 해당 자리가 0이면 이를 1로 바꾸고, 0.. 2022. 8. 20.
[프로그래머스 lv2] 가장 큰 정사각형 찾기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저, 완전 탐색 풀이를 적어보고 시간복잡도가 효율성을 통과할 수 있을지 확인해보자. 완전탐색으로 푼다면, 직사각형의 크기가 N x M 일 때 가능한 정사각형 한변의 길이 k에 대하여 모든 k*k를 확인해야 한다. 따라서 다음과 같이 5중 포문을 써야 하고 결국 TLE가 날 것임을 예상할 수 있다. for (int k = 1; k 2022. 8. 20.
[프로그래머스 lv2] n^2 배열 자르기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저 해당 문제가 완전 탐색이나 단순 구현으로 해결되는지 확인해야한다. 최대 입력 범위가 10^7 이기 때문에 반복문으로 배열의 행과 열을 채우면 TLE가 발생한다. 따라서 배열을 일렬로 나열했을 때의 인덱스를 보고 바로 배열의 값을 알아낼 수 있는 방법을 찾아야 한다. 일단, 배열의 x, y 좌표와 배열 값 사이의 관계를 생각해보면, (x, y)의 값은 max(x, y) + 1 이 된다. 예를 들어, (2, 3)의 값은 max(2, 3)+1 = 4 가 되고, (2, 0)의 값은 max(2, 0)+1 = 3 이 된다. 해당 규칙을 이용하면 각 배열을 모두 순회하지 않고도 특정 좌표의 값을 바로 알 수 있다. 다음으로, 배열을 일렬로 나열했을 때의.. 2022. 8. 19.
[프로그래머스 lv2] 2xn 타일링 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 2 x n 타일을 채우는 방법은 크게 두가지로 나눌 수 있다. 첫째, 2 x (n-1) 을 채우고 2 x 1 을 채우는 방법 둘째, 2 x (n-2)를 채우고, 1 x 2 를 가로로 두개 채우는 방법 따라서, dp[i] 를 2 x i 를 채우는 방법의 수라고 정의할 때, 점화식은 다음과 같다. dp[i] = dp[i-1] + dp[i-2] 이때, 문제에서 1000000007로 나눈 나머지를 구하라고 했으므로, 최종 점화식은 다음과 같다. dp[i] = (dp[i-1] + dp[i-2]) % 1000000007 dp 값을 구한 뒤 dp[n]을 리턴하면 정답이다. 코드 #include #include #include #include #include #in.. 2022. 8. 18.
[프로그래머스 lv2] 점프와 순간이동 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 0에서 n까지 이동할 수 있는 방법은 두가지이다. 첫째, 현재 위치에서 2배 위치로 이동하는 것(순간이동, 건전지 소모 X) 둘째, K 만큼 점프하는 것(점프, K만큼의 건전지 소모 O) 방향을 뒤집어 n에서 0까지 이동한다고 생각해보자. 현재의 위치가 짝수이면 무조건 n/2 위치로 순간 이동을 하는 것이 유리하다. 순간이동은 건전지 소모가 없기 떄문이다. 반면, 현재 위치가 홀수이면 n/2 위치로 순간 이동을 할 수 없으므로 무조건 건전지를 1 소모해야 한다. 따라서, 반복문 내에서 n이 홀수이면 n을 1줄이면서 건전지 소모량을 1 늘리고, 짝수이면 n을 2로 나누어주자. n이 0이 되었을 때 총 건전지 소모량을 리턴하면 정답이다. 코드 #inclu.. 2022. 8. 17.
[프로그래머스 lv2] 괄호 회전하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 주어진 문자열을 0번~ s.size()-1번 회전했을 때 올바른 괄호의 개수를 세는 문제이다. s의 입력 길이가 최대 1000이므로, 회전한 문자열 모두을 구해 올바른 괄호인지 확인하여도 TLE가 발생하지 않는다. s를 i번 회전했을 때의 문자열은, s를 i번째 인덱스에서 끊고 앞 부분을 모두 문자열의 뒤로 이동시킨 것과 같다. i번 회전한 문자열을 구한 뒤, 해당 문자열이 올바른 괄호인지 확인하자. 문자열이 올바른 괄호인지 확인하는 방법은 다음과 같다. 먼저, 여는 괄호가 등장했을 때는 스택에 넣는다. 닫힌 괄호가 나왔을 때, 스택의 가장 최근 원소가 짝이 맞는 여는 괄호인지 확인하여 스택에서 삭제한다. 만약, 스택의 가장 최근 원소가 짝이 맞는 열.. 2022. 8. 17.

티스토리툴바