하다보면 늘겠지

📍 문제 설명 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 💡 접근 bfs 문제였는데 큐가 2가지 필요했다. 1. 빙산을 한번에 녹이기 위한 큐 2. 두 덩어리 이상으로 분리되어있는지 확인하기 위한 큐 👩‍💻 코드 import java.io.*; import java.util.*; public class Main { static int[] arr, dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; static in..

📍 문제 설명 https://www.acmicpc.net/status?user_id=chqdlstjd2&problem_id=16973&from_mine=1 채점 현황 www.acmicpc.net 💡 접근 전형적인 BFS 문제 다른 부분은 좌표 하나만 확인하는 것이 아닌 직사각형으로 확인해야 했던 문제 직사각형의 첫 시작 좌표들로 방문여부를 체크 👩‍💻 코드 import java.io.*; import java.util.*; public class Main { static int[] arr, dx = {-1,1,0,0}, dy = {0,0,-1,1}; static int[][] board; static boolean[][] visited; static int n, m, k, t, num, cnt, seco..

📍 문제 설명 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 💡 접근 q사이즈만큼 루프를 돌린다음 벽을 내려한다! 해당 조건이 없으면 한 칸을 이동할 때 마다 벽이 내려가게 됨 방문조건을 고려하려면 q사이즈 루프돌때마다 새로 방문 배열을 만들어줘야 했는데 딱히 고려안해도 메모리, 시간초과가 나지는 않았다. 👩‍💻 코드 import java.io.*; import java.util.*; public class Main { static..

📍 문제 설명 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 💡 접근 k = 1일 때 처음부터 움직일 수도 있지만 인접한 방향으로만 이동하다가 중간에 말처럼 이동할 수도 있기 때문에 그 부분 때문에 3차원 배열을 사용했음 며칠전 문제에서 해당하는 위치를 바로 리턴안해줬더니 시간초과가 뜨는 문제가 있어서 이번엔 지점 찾으면 바로 리턴해주는 식으로 접근했는데, 이번 문제에서는 100%에서 틀렸습니다.가 떴다. 이 문제에서는 2갈래..

📍 문제 설명 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 💡 접근 범위가 그렇게 크지 않아서 조합으로 풀 수 있겠다 싶었는데, 시간초과가 났다. 1번 ~ n번까지 각 숫자에 대해서 배열에 해당하는 값(인덱스)을 찾아야한다. idx번의 값과 배열의 idx 인덱스와의 값이 매칭되면 리스트에 넣어주면 된다. 👩‍💻 코드 import java.io.*; import java.util.*; public class Main { stati..

📍 문제 설명 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 💡 접근 배열이 아닌 Set을 이용해서 좌표 방문 여부를 체크해줬는데 계속 메모리 초과가 났었다. 위의 문제는 집을 모두 지었을 때의 체크를 루프 바깥에서 해줬기 때문이다. 그리고 바깥에서 체크를 해주면 루프 안에서 집이 하나 더 만들어질 수도 있기 때문에 오답이다. 타 블로그를 참고해서 새롭게 알게된 문법이 있다. out:while 문법을 쓰고 안에서..

📍 문제 설명 https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 💡 접근 그림을 보면 건물에서 인접한 6 방향의 벽의 숫자만큼 조명을 장식한다. 주의해야 할 점은 행이 짝수냐 홀수냐에 따라 인접한 6방향의 좌표가 다르기 때문에 짝수/홀수에 맞는 인접한 좌표를 따로 사용해야 한다. 그리고 범위를 벗어나는 경우도 벽으로 인정되어야 하기 때문에 행과 열 길이의 +2 만큼의 배열을 생성했다. 0,0 부터 시작해서 벽인 지점..

📍 문제 설명 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 💡 접근 회문이 아닌 경우에 왼쪽 문자를 무시하거나 오른쪽 문자를 무시하여 회문을 확인하는 절차가 필요하다 1. StringBuilder의 deleteChatAt 사용하는 방법 2. 팰린드롬 아닐경우 해당 양 옆의 문자를 제거하여 팰린드롬 재확인하는 방법 StringBuilder의 경우 shift 과정 때문에 메모리를 약 2배 더 잡아먹었다. 👩‍💻 코드 import java.io.*; import java.ut..

📍 문제 설명 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 💡 접근 문제 의도는 우선순위 큐 2개를 사용해서 풀라는 의도였지만 Treemap을 사용해서 더 편리하게 풀 수 있는 문제였다. firstKey(), lastKey()를 처음 사용해보았다. 👩‍💻 코드 import java.io.*; import java.util.*; public class Main { static boolean[] visited; static ArrayList..

📍 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 접근 풀면서 느꼈지만 당연하게 효율성에서 걸렸던 문제다. O(N*M)을 O(1)로 바꾸기 위해서 누적합 개념을 이용해야 했는데 2차원 배열로 확장된 케이스라 어느정도 고려할 부분이 있었지만 1차원 배열에서의 누적합 개념을 제대로 이해하고 있었으면 풀 수 있을 문제였을 것 같다. 누적합 유형도 간혹가다가 출제되는 것 같으니 어느정도 익혀놓는 것이 좋을 것 같다. 👩‍💻 코드 imp..