재원블로그 재원블로그

이 문제는 프로그래머스 Level 2 문제이다. 이 문제는 구현이 어려운 편에 속하고, 백트래킹을 이용해 연산자 우선순위를 정하고, long long 자료형을 사용해야 한다는 사실을 캐치하면 풀 수 있다. 수식이 정해져 있고, 연산자 우선순위가 같은 경우가 없기 때문에 다이나믹 프로그래밍을 생각해내기 어려웠다. 연산자가 최대 3개이므로 우선순위 경우의 수는 최대 6이다. 따라서 O(N) 시간의 알고리즘으로도 1초 안에 풀 수 있다. 연산하는 것까지 구현을 잘 했지만, long long 자료형을 사용해야 한다는 점을 파악하지 못해 처음에 오답이 나왔다. 그러나 문제를 다시 읽고 바로 수정한 뒤 정답을 받을 수 있었다. #include #include #include #include using namespa..

이 문제는 프로그래머스 Level 2 문제이다. 문제에서 주어진 대로 그대로 구현하면 되는 문제이다. 한 가지 주의할 점은 균형 잡힌 두 개의 문자열로 나누는 부분인데, 처음으로 acc이 0이 되는 i 를 찾아 그 부분을 중점으로 둘로 나누면 된다. #include #include #include using namespace std; bool isCorrect(string str) { stack st; int strSize = str.size(); for (int i = 0; i < strSize; i++) { char c = str[i]; if (st.empty()) { if (c == '(') { st.push(c); } else { return false; } } else { if (c == '('..

이 문제는 구현, 시뮬레이션 문제이다. 문제 길이는 짧아보이지만 생각보다 어려운 문제였다. 이 문제에서 핵심은 물고기들, 상어, 물고기 냄새를 따로 저장하여 구현하는 것이다. 처음에 물고기들과 상어를 같이 넣어놓고 erase를 통해 빼면서 구현했는데, 테스트 케이스에서조차 2초 안에 답이 나오지 않는다. 이는 erase가 내부적으로 O(N) 시간이 걸리기 때문이었다. erase 함수는 되도록 그냥 사용하지 않아야겠다는 생각이 문제를 풀 수록 든다. 또한 빠뜨리기 쉬운 부분은 물고기의 방향을 찾을 때, 입력에서 주어지는 LEFT부터 시계 방향과 다르게 반시계 방향으로 탐색해야 한다. 이 부분을 까먹어 처음에 전혀 다른 방향으로 답이 나왔었다. 위 두 가지 이외에도 구현이 쉽지는 않지만, 삼성 기출 문제를 ..

이 문제는 스택을 이용해서 풀었다. 예전에 풀었다가 결국 못 풀었었는데, 이번에는 정답을 맞췄다. 스택을 pair에 대해 사용하였고, first는 문자, second는 다음 매칭되어야 할 인덱스를 저장했다. 구현은 비교적 쉽게 했는데, 계속 시간 초과가 났었다. 알고보니 이는 마지막에서 result = st.top().first + result 를 사용해서 reverse 함수 없이 바로 출력했었는데 이 방법이 O(N) 시간을 소요하게 된다고 한다. 매번 result에 O(N) 시간이 걸리므로 최악 O(N^2) 이 걸리게 되어 시간 초과가 발생하는 것이다. 그래서 result += st.top().first 를 사용하고 reverse 를 사용하면 총 O(N) 시간밖에 안 걸려 정답이 나오게 된다. #inc..

이 문제는 구현, 시뮬레이션 문제이다. 요구사항이 굉장히 까다로운데, 핵심적인 부분은 2차원 배열의 중앙부터 반시계 방향으로 배열을 읽는 방법을 구현하는 것과 구슬 폭발을 구현하는 것이다. 첫 번째는 나의 경우 nextPos 함수와 make 함수를 통해 구현하였다. nextPos는 현재 위치 기준으로 direction에 따라 다음 위치를 리턴하는 함수이고, make는 nextPos를 이용하여 전체 2차원 배열을 반시계 방향으로 순회하는 함수이다. 반시계 순회의 규칙성을 보면 중간에서 시작하여 1, 1, 2, 2, 3, 3, 4, 4, .... 의 양만큼 앞으로 가고, 방향은 왼, 아, 오, 위 순으로 동작한다. 이를 그대로 구현하면 쉽게 반시계 방향으로 읽을 수 있다. 두 번째는 구슬 폭발 구현인데, 이..

이 문제는 시뮬레이션 문제이고, bfs를 활용하여 풀었다. 이 문제에서 가장 어려운 부분은 첫 번째로 블록 그룹을 찾아내는 것이고, 두 번째는 중력 작용을 시키는 것이다. 첫 번째는 bfs를 이용하였는데, node라는 구조체를 만들어 필요한 정보들을 넣도록 하였고, 이를 bfs에서 리턴하도록 했다. 주의할 점은 격자에서 무지개 블록, 즉 0은 visited에 포함되면 안된다. 그러나 bfs 내부에서 0에 대한 visited를 처리하지 않으면 당연히 무한 루프에 걸리게 된다. 이를 해결하기 위해서 일단 bfs를 수행하고, bfs가 끝난 뒤 무지개 블록에 대해 visited가 true가 되어있는 걸 false로 바꿔주면 된다. 상하좌우가 중요하지 않다는 점도 중요한 포인트이다. 임의의 (y, x)에 대해 같..

이 문제는 bfs를 이용해서 풀었다. 이 문제에서 핵심은 택시가 손님들을 찾는 과정에서 최단거리이며, 만약 거리가 같은 경우 행 번호가 작은, 행 번호도 같다면 열 번호가 작은 손님을 찾는 것이다. 이를 위해 처음에는 bfs의 상하좌우 탐색 순서를 상좌우하 순서로 탐색하고 찾은 경우를 리턴했지만, 이는 정답이 나오지 않았다. 그래서 두 번째 방법으로 일단 bfs를 맵 전체에 대해 돌리고, 손님들의 startY, startX를 기준으로 오름차순 정렬한 배열에 대해 최단거리를 비교하며 손님을 뽑는 형식으로 바꿔 정답을 도출해낼 수 있었다. 이 부분만 잘 해결한다면 나머지는 쉽게 구현 가능한 문제였다. #include #include #include #include #include using namespace..

이 문제는 시뮬레이션 문제이다. 일단 main에 있는 for문이 1,000번 돌아가므로, for 문 안의 연산의 수가 약 100,000 이면 1초 안에 풀 수 있다. 물론 실제로는 입력 받기, 전처리 등이 for문 전에 있으므로 약 50,000번 정도의 알고리즘이면 안전하다고 생각했다. 이 문제는 냄새 배열과 상어 배열을 따로 만드는 것이 훨씬 구현을 간단히 할 수 있다. 또한 각 상어의 우선순위 방향을 입력받을 때 -1을 해서 받으면 더 용이하게 구현할 수 있다. 한 가지 주의할 점은 각 초마다 냄새를 -1을 해야하는데, 이를 먼저 하고 상어를 움직이면 상어 움직임이 정답과 다른 방향으로 가게 된다. 상어를 움직이고 난 뒤 냄새를 -1하고, 상어가 있는 위치의 냄새를 다시 초기화하면 정답이 나온다. /..