L.O.K

https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 n = > k진수로 바꾸었을때, 구분자 0으로 구분되는 소수P의 개수를 구하는 문제이다. 이를 3가지 단계로 나누어 보았다. 1. k진수로 바꾸라. 2. 구분자 0으로 분리하라. 3. 소수 여부를 확인하라. 주의) K진수 안의 십진수를 정수로 변환할 때, Integer 범위를 넘을 수 있으므로 Long 자료형을 사용한다. ◎ 코드 import java.util.*; import jav..

https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 신고에 대한 입력정보가 주어질 때, 신고자에게 가는 메일의 개수를 구하는 문제이다. 문제를 풀때, 두가지를 신경썼다. 1) 유저와 인덱스를 1대1로 매핑하기 위해, HashMap 자료구조를 사용하였다. 2) 신고 객체에서 신고대상의 신고자의 중복을 방지하기 위해, HashSet 자료구조를 사용하였다. ◎ 코드 import java.io.*; import java.util.*; //신고..

https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net ◎ 문제풀이 '비오름차순'(내림차순)으로 정렬된 점수 배열에서 새로운 점수의 랭크를 구하는 문제이다. '정렬'된 배열에서 새로운 점수의 위치를 '탐색'하는 문제이므로, 이분탐색법을 발상했다. ◎ 코드 package org.example.binarySearch; import java.io.*; import java.util.*; //BOJ1205 등수 구하기 public..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ◎ 문제해결 스택을 이용하면 쉽게 풀리는 문제이다. 스택을 처음에 발상했지만 시간복잡도에 걸릴 것이라 판단했었다. 그런데 다시 생각해보니 그렇지 않았다. 6 9 5 7 4 왼쪽부터 하나씩 포인터를 이동하면서 Stack의 Top과 비교한다. Top이 작으면 POP한다. 스택에 더이상 값이 없으면 0을 출력하고 Top에 자신보다 크거나 같은 수가 있으면 출력한다. 그리고 자신의 인덱스를 스택에 PUSH 한다. 스택에는 포인터 이전의 수가 모두 들어가 있지 않고 P..

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ◎ 문제풀이 문제 이해력과 구현력이 필요한 문제였다. 접근이 가능한 인접지역을 탐색하는 문제이므로 DFS와 BFS가 떠올랐다. DFS는 깊이우선탐색으로 깊이를 먼저 파다보면 접근하지 않아도 되는 경우의 수도 접근할 수 있다. DFS와 BFS 결국 모두 동일한 지역을 접근하므로 접근가능한 경우의 수를 줄이기 위해 BFS로 탐색한다. 그럼 며칠을 인구이동해야 인구이동이 필요없는지 구해보자. 인구차이가 20(L)보다 크거나 같고 90(R)보다 작거나 같아..

20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net ◎ 문제풀이 문자열 안의 부분문자열 중에서 특정 문자로 시작해서 끝나는 문자열 중 해당 문자가 K개 있는 경우의 최소길이와 최대길이를 구하는 문제이다. 문자열 안의 특정문자 K개를 찾아야 하므로 반복문이 중첩될 수 밖에 없는데, 문자열의 길이는 최대 10,000이다. 그러므로 시간초과가 발생하지 않도록, 가지치기를 할 필요가 있다. 1. 문자열 내 알파벳 별 개수 파악하기 알파벳 개수를 파악하여 K개보다 작으면 반복을 하지 않는다. 2. 문자열 탐색 문자열 앞..

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net ◎ 문제풀이 문제이해력과 구현력이 필요한 문제였다. 자료구조는 2개를 만들어 준다. 1) 컨베이어 벨트 ( int 배열 , 내구도 ) 2) 로봇위치 ( boolean 배열, 로봇 존재 여부 ) 문제에 주어진 단계에 따라 차근히 구현하면 된다. 1) 벨트 이동하기 벨트가 한 칸 움직일때마다, 우측으로 값을 복사한다. 맨끝은 가장 처음으로 복사한다. 벨트 자료구조를 우측으로 값을 복사하였다. 벨트 위에 있는 로봇도 함께 우측으로 이동한다. 2) ..

12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net ◎ 문제풀이 문제를 보고 DFS 알고리즘을 잘 떠올렸으나 시간초과가 발생하였다. Source를 Target으로 만들기 위해 DFS로 모든 경우를 탐색하였다. 문제를 풀면서도 시간초과를 예상하기는 했다. Source 끝에 A를 추가하거나 Source 끝에 B를 추가하거 뒤집어야 한다. Source와 Target의 길이 차이만큼 경우의 수는 2ⁿ 으로 늘어난다. Target의 최대길이가 50이므로 경우의 수는 2의 49승까지 ..

1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net ◎ 문제풀이 슬라이딩 윈도우 알고리즘을 알고 있으면 쉽게 풀리는 문제이다. ( 나는 모르고 있어서 해매었다.. ㄷ ) 문제의 목적은 aaa 연속, bbb 연속으로 만드는 것이다. a의 개수는 3개이다. 그럼 윈도우의 크기도 3이다. 3의 크기로 하나씩 비교하며 a로 바꾸어야 하는 b의 개수의 최솟값을 구하면 된다. a로 바꾸어야 하는 b는 1개이다. 그럼 오른쪽으로 한칸 슬라이딩 해보자. a로 바꾸어야 하는 b는 1개이다. 그럼 오른쪽으로 슬라이딩 해보자. a로 바..

15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net ◎ 문제풀이 문제를 보고 DP를 떠올렸으나 '순서만 다른 것은 같은 것으로 본다'는 조건이 어려웠다. 순서만 다른 정렬을 같게 만들려면 오름차순으로 정렬하면 된다. +1 로 끝난 식 뒤에는 +1만 올 수 있고 +2로 끝난 식 뒤에는 +1, +2만 올 수 있고 +3으로 끝난 식 뒤에는 +1, +2, +3만 올 수 있다. 예를 들어 dp[4][1] : 4를 만드는데 끝이 1인 경우의 수이다. dp[4][2..