재원블로그 재원블로그

이 문제는 맵을 이용한 구현 문제이다. 문제에 주어진 설명 그대로 구현하면 바로 시간 초과 없이 정답이 나온다. 왜냐하면 msg에 대해 루프를 돌리는데 사전에 없는 단어가 나올때의 그 문자부터 시작하므로 결국 O(N) 시간이 걸리고, msg의 최대 길이가 1,000 밖에 되지 않기 때문이다. 이 문제를 풀기 위해 다음과 같은 수도 코드를 작성하였다. temp += msg[index] 만약 dic[temp] == 0이라면// 사전에 없음 answer에 dic[prev] 추가 dic[temp] = pushIndex pushIndex++ index-- temp = "" prev = "" 0이 아니라면 // 사전에 있음 prev = temp; continue index++ 처음에는 while문 안에 for문이 ..

이 문제는 규칙성을 찾아 그대로 구현해서 푸는 문제이다. 일단 n의 최대 크기가 1,000만이므로 2차원 배열 자체를 만들 수 없다. 또한 n x n 배열을 1차원 배열로 만들어놓은 배열 또한 만들 수 없다. 그러므로 단순한 탐색 알고리즘으로는 불가능하고, 숫자에서 규칙을 찾아 문제를 풀어야 한다. 일단 right - left 가 최대 99,999 이므로 answer 배열의 최대 길이는 100,000이 될 것이다. 이 문제의 핵심은 left와 right로 주어진 숫자를 2차원 배열의 몇행 몇열인지를 한번에 찾아내는 것이다. 간단한 방법이 있었는데, 만약 숫자가 7이고, 4 x 4 배열이라고 가정하면 7 / 4 = 1, 7 % 4 = 3 으로 0번 인덱스부터 시작해서 1행 3열을 나타내는 수가 7이 되는 ..

이 문제는 수학 문제에 가깝게 풀었다. 일단 최대 n의 크기가 20인데, 20!은 2,432,902,008,176,640,000 라는 엄청난 수가 나오고, 당연히 단순 순회로는 이 문제를 풀 수 없다. 그러나 한가지 중요한 점은 20!이 long long 자료형에 담긴다는 사실이다. 즉, 팩토리얼을 이용한 어떤 수식을 사용할 수는 있다. 일단 n = 4 일때의 모든 순열을 구하고, 규칙을 찾아봤다. 1 2 3 4 - 0 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 - 6 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 - 12 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 - 18 4 1..

이 문제는 bfs를 이용해서 풀었다. 일단 입력 2차원 배열이 최대 100 * 100 이므로 bfs를 돌리기에 충분한 시간이었다. 기본적인 구현이므로 빠짐없이 구현만 하면 정답이 바로 나오는 쉬운 문제였다. #include #include #include #include #include using namespace std; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, -1, 0, 1}; bool visited[100][100]; int N; int M; bool inRange(int y, int x) { if (0

이 문제는 투 포인터를 이용해서 풀었다. 일단 이 문제의 입력 배열의 최대 크기가 100만이므로 O(n) 시간 이하의 알고리즘을 사용해야 한다. 그래서 투 포인터를 떠올렸고, 왼쪽에서 두 포인터가 모두 시작하는 방향으로 구현하였다. 정답으로 리턴해야하는 값이 부분 배열의 처음과 끝 인덱스인데, 끝 인덱스가 포함된 범위이므로 right++을 할 때 더 조심해야 한다. 그래서 right++을 하는 로직마다 size를 넘었는지 체크하는 부분을 집어넣었다. 또한 왼쪽에서 둘 다 시작하는 투 포인터는 반드시 두 포인터가 만났을 때는 right가 증가해야 두 포인터가 교차하여 발생하지 않게 된다. #include #include #include using namespace std; vector solution(ve..

이 문제는 진법 변환 문제이다. 나는 처음에 이 문제를 백트래킹을 이용해서 풀었으나, 효율성 검사에서 시간 초과가 나왔다. 아무리 최적화를 해도 시간 초과가 나온다. 그래서 검색을 해보니 단순 진법 문제였다. 이 문제에서 핵심은 3으로 나눈 나머지가 0일 때 4를 추가해주고, n을 1 빼줘야 값이 제대로 나온다는 것이다. 그 점만 파악하면 쉽게 풀 수 있었을 것 같다. #include #include #include using namespace std; string solution(int n) { string answer = ""; while (n > 0) { int rem = n % 3; n /= 3; if (rem == 0) { answer = '4' + answer; n--; } else if (r..

이 문제는 스택을 사용하는 문제이다. order의 최대 길이가 100만이므로 O(n) 시간 이하 알고리즘을 사용해야 한다. 문제를 잘 읽어보면 보조 컨베이어 벨트가 스택 구조라는 것을 알 수 있다. 처음에 알고리즘을 구상할 때는 box와 order를 한 루프 안에 전부 해결하려고 했으나, 이렇게 하면 로직이 매우 복잡해진다. 일단 box에 대해 모든 연산을 다 수행한 뒤, 스택에 남은 것을 처리하는게 훨씬 간편하게 구현할 수 있었다. 한가지 주의할 점은 box 반복문에서 st.top()이 현재 order와 같은 경우 box를 고려하지 않았는데 for문에 의해 더해지므로 box--을 해놔야 box는 그대로고 스택에서만 뺄 수 있다는 것이다. 이 부분만 생각할 수 있다면 구현은 어렵지 않은 문제였다. #in..

이 문제는 맵을 이용해서 풀었다. topping의 최대 길이는 100만이므로, O(n) 시간 이하의 알고리즘을 써야만 시간 안에 풀 수 있다. 절반을 자르는 로직은 왼쪽은 topping의 처음부터 half를 포함하는 범위까지로, 오른쪽은 half + 1부터 마지막까지로 정했다. topping을 순회하면서 절반을 자르고, 여기서 추가 반복문을 사용하지 않기 위해 map으로 해당 숫자의 count를 저장하고, left에서는 해당 값이 0일때 추가되면 leftCnt++을, right에서는 해당 값이 0이 되면 rightCnt--을 수행하여 정답을 도출했다. #include #include #include using namespace std; int solution(vector topping) { int ans..