본문 바로가기

SW Expert Academy

 (33)
[SWEA] 특이한 자석 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 4개의 자석의 정보를 저장하는 LinkedList 배열을 만들고 이를 사용해서 회전시키면 된다. LinkedList[] magnet은 각각의 4개의 자석 정보를 담는다. magnet[0]은 1번 자석, magnet[1]은 2번 자석, magnet[2]는 3번, magnet[3]은 4번의 정보를 저장한다. 회전 시킬 자석과 방향을 입력받아 각각 standardNum과 rotateDir에 저장한다. checkMagnets 메서드는 standardNum 자석을 회전시켰을 때, 다른 자석들이 회전하는지 확인해주는 메서드이다. standardNum을 기준으로 오른쪽 자석들이 회전해야 하는지 확인할 때는, 기준 자석의 2번 자성 정보와 확인할 자석의 6번..
[SWEA] 최장 증가 부분 수열 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 DP를 사용해 각 자리까지의 최장 증가 수열을 저장한다. nums는 입력받은 숫자 배열이고, dp는 각 자리까지의 최장 증가 수열을 저장하는 배열이다. dp[0]은 제일 앞에 있는 값이므로 1로 두고 시작한다. i = 1 부터 N - 1까지 접근해 각 자리의 최장 증가 수열을 구한다. 현재자리의 최장 증가 수열은 나의 앞에서 나보다 작은 애들 중의 최장 증가 수열 + 1이다. 예를 들어, nums가 1, 3, 2, 5, 4일 경우 dp[3]을 구하려면 인덱스 0부터 2까지 돌면서 나보다 작은 애들의 최장 증가 수열의 최댓값을 구한다. nums[0], nums[1], num[2] 모두 5보다 작으므로, 얘들의 dp값을 비교하여 최댓값을 가져온다...
[SWEA] 탈주범 검거 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS를 사용해 각 칸까지 이동하는데 걸리는 시간을 구한다. map[r][c]는 지하 터널의 상태를 저장하는 배열이고, time[r][c]는 (r, c)까지 이동하는데 걸리는 시간을 저장하는 배열이다. 이 배열들을 사용해 BFS를 구현하면 된다. map[r][c]가 터널 구조물이라면(1~7이라면) 타입에 맞게 인접한 nextX, nextY를 구해준다. isPossibleScope은 (nextX, nextY)가 이동할 수 있는 곳인지 확인하는 메서드이다. (nextX, nextY)가 범위를 벗어나거나, 이미 방문한 곳이거나, 이동할 수 없는 곳(구조물이 없는 경우. 즉, map[nextX][nextY] = 0)이라면 false를, 아니라면(이동할..
[SWEA] 보급로 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS를 사용해 풀었다. map[i][j]에는 각 칸의 복구 작업을 저장하고, minTime[i][j]는 각 칸까지의 최소 복구 작업 시간을 저장한다. Deque을 사용해서 BFS를 구현하면 된다. 가장 초기에는 시작점 (0, 0)을 덱에 넣는다. 덱이 빌 때까지 덱의 원소에 하나씩 접근한다. 현재 칸은 int[] cur이고, 인접한 칸(이동할 수 있는 칸)은 nextX, nextY라고 한다. minTime[cur[0]][cur[1]] + map[nextX][nextY]가 minTime[nextX][nextY]보다 작을 경우, 답이 될 수 있으므로, minTime[nextX][nextY]를 minTime[cur[0]][cur[1]] + map[..
[SWEA] 키 순서 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 * 백준의 키 순서 문제와 같다. heightInfo 배열을 사용해 부모와 자식의 관계를 나타내줬다. heightInfo[i][j]가 1이라면, i의 부모가 j라는 뜻으로, i보다 j가 키가 크다는 뜻이고, heightInfo[i][j]가 2라면, i의 자식이 j라는 뜻으로, i보다 j가 키가 작다는 뜻이다. 관계를 나타내준 후, 각각 i 값에 접근하여 BFS를 사용해서 문제를 풀면 된다. 먼저, 접근 가능한 부모를 모두 방문하고, 이후에 접근 가능한 자식을 모두 방문한다. 모두 방문했으면, visit 배열에서 방문하지 않은 값이 있는지 확인하고, 방문하지 않은 값이 있다면, 해당 사람의 키 순서를 알 수 없다는 뜻이므로 false를, 아니라면..
[SWEA] 창용 마을 무리의 개수 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 서로소 집합을 사용해 문제를 풀었다. a가 속한 집합의 대표자를 찾는 메서드 find와, 두 원소를 하나의 집합으로 합쳐주는 메서드 union를 사용해 문제를 풀면 된다. 코드 package swea; // 창용 마을 무리의 개수 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageInde..
[SWEA] Contact 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS (큐)를 사용해 문제를 풀었다. 인접 행렬 map을 사용해 그래프가 서로 연결되어 있는 상태를 나타낸다. visited 배열을 사용해 시작점부터 i까지 오는 데 걸리는 횟수를 저장한다. visited[i]가 0이라면, 아직 방문을 하지 않은 것으로 판단한다. BFS는 큐를 사용해 푸는 방법이므로, 제일 먼저 시작점 (시작 사람)의 번호를 넣어준다. while문을 통해 큐가 비어있지 않을 동안, 큐의 가장 앞의 값을 가져오고, 그 값과 연결된 값들이면서 아직 방문하지 않은 점을 다시 큐에 넣는다. 이 때, visited[to] 값은 visited[from] + 1로 설정한다. while문을 빠져나온 후, visited 배열을 확인하면서 가..
[SWEA] 스도쿠 검증 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 스도쿠가 유효한지 체크하는 변수 isOkay를 사용해 체크해준다. 먼저, 세로줄(행)이 유효한지 체크하고, isOkay가 false일 경우, 0을 출력하고 다음 테스트케이스로 넘긴다. isOkay가 true일 경우, 가로줄(열)이 유효한지 체크하고, isOkay가 false일 경우, 0을 출력하고 다음 테스트케이스로 넘긴다. isOkay가 true일 경우, 3 x 3을 체크한다. 3 x 3의 왼쪽 위 좌표를 사용해서, 해당 좌표부터 3 x 3 사각형을 체크하면 된다. 나는 중간 중간 isOkay를 확인하고 다음으로 넘겼는데, 그냥 마지막에서 체크해줘도 제대로 동작한다. 코드 package swea; // 스도쿠 검증 (https://swexpe..

티스토리툴바