소프티어9 [소프티어] 6248번 - 출퇴근길 [Java] https://softeer.ai/practice/6248 1. 아이디어 시작점에서 방문할 수 있는 점들은 DFS 알고리즘으로 간단하게 구할 수 있다. 이때 다른 점들에서 도착점을 갈 수 있는지 여부는 역방향 간선을 활용해서 도착점에서 역방향 간선으로 DFS 알고리즘을 적용하면 간단하게 구할 수 있다.2. 문제풀이 동환이의 집에서 출근길에 포함되는 점들은 동환이의 집에서 DFS 알고리즘으로 방문 가능한 정점을 찾고 다시 방문 가능한 점들이 회사에 갈 수 있는지 찾으면 구할 수 있다. 하지만 처음 동환이가 찾은 방문 가능한 정점의 수가 늘어날 수록 DFS 알고리즘을 반복적으로 적용해야해서 시간초과가 발생하게 된다. 이를 해결하기 위해 동환이의 집에서 출근길에 포함되는 점들을 DFS 알고리즘으로 찾은 후.. 2025. 2. 10. [소프티어] 6255번 - 플레이페어 암호 [Java] https://softeer.ai/practice/6255 1. 아이디어 문자열을 통한 구현 문제로 열심히 구현하면 간단하게 해결할 수 있다.2. 문제풀이 먼저 주어진 메시지로 문자를 두 글자씩 나누는 조건을 구현했는데 for문에서 인덱스를 i+=2로 두 칸씩 건너가는 방식으로 두 글자를 뽑아서 다르면 StringBuilder에 넣고 같으면 X가 아니면 X를 넣고 X면 Q를 넣도록 했다. 이때 X 또는 Q를 넣으면 두번째 글자가 X 또는 Q로 대체되는 것이므로 i--로 인덱스를 하나 줄이도록 했다. 또 이때 삽입한 문자의 수를 저장해서 이후 기존 메시지와 삽입한 문자 수의 합이 홀수면 뒤에 X를 추가로 넣는 조건을 구현했다. 주어진 키를 표로 변환하는 것은 변환 후 남은 칸은 다시 A부터 없는 알파벳을.. 2025. 2. 7. [소프티어] 6275번 - 로봇이 지나간 경로 [Java] https://softeer.ai/practice/6275 1. 아이디어 방문한 곳을 다시 방문하지 않으면서 좌우 회전과 바라보는 방향으로 두 칸 이동하는 로봇의 움직임은 폐곡선을 만들지 않으면서 한붓그리기가 가능한 경로로 움직이게 된다. 따라서 방문한 칸이면서 사방에 방문한 칸이 한칸 밖에 없는 지점 두 개가 가능한 출발지가 된다. 해당 출발지에서 DFS 알고리즘을 통해 위치와 방향을 들고 다니며 명령을 구하는 방식으로 구현했다.2. 문제풀이 입력을 받은 후 시작 위치와 방향을 먼저 찾았다. 맵을 순회하며 방문한 칸일 때 사방에 방문한 칸이 하나밖에 없는 곳이면 시작 위치와 방향을 구한 후 종료했고 이후 해당 정보로 DFS 탐색을 시작했다. DFS는 방문 후 다음 위치를 찾을 때 다음 위치와 현재 .. 2025. 2. 7. [소프티어] 6257번 - 통근버스 출발 순서 검증하기 [Java] https://softeer.ai/practice/6257 1. 아이디어 (a, b, c)가 스택 정렬이 불가능한 경우는 a, b, c에서 나올 수 있는 6가지 경우의 수 중 a c 인 경우 하나 뿐이다. N이 최대 5000까지여서 3중 for문을 활용한 간단한 구현은 시간 초과가 발생하는데 이를 해결하기 위해 다이나믹 프로그래밍을 활용해 O(N^2)으로 구현했다.2. 문제풀이 스택 정렬이 불가능한 조합을 찾기 위해 dp 테이블을 활용했다. dp 테이블에는 주어진 수 i, j에 대해 i보다 큰 j를 발견했을 때 j 이후로 등장하는 i보다 작은 수의 개수를 저장했다. 이를 위해 열 인덱스를 역순으로 순회하며 바로 이전 값을 채워준 후 i > j면 +1을 해주도록 했다.이후 다시 2중 for문을 순회하며.. 2025. 2. 7. [소프티어] 6251번 - 업무 처리 [Java] https://softeer.ai/practice/6251 1. 아이디어 각 직원에 대해 왼쪽 직원한테 받은 업무와 오른쪽 직원한테 받은 업무를 구분해야 한다. 이를 위해 두 개의 Queue를 갖는 노드 클래스를 활용했고 주어진 트리의 루트를 1로 설정한 후 비트마스킹을 활용했다. 업무의 전달은 부서장부터 말단 직원 순으로 진행된다는 점에 주의해야한다.2. 문제풀이 완전이진트리인데 말단 직원과 부서장까지의 올라가는 거리가 같으면 포화이진트리가 된다. 이를 통해 가장 왼쪽 말단 직원의 번호와 가장 오른쪽 말단 직원의 번호를 비트마스킹으로 구해서 변수로 저장했다. 이후 말단 직원에게 업무들을 부여했다. R일까지의 반복은 부서장 일처리 -> 중간 직원 일처리 -> 말단 직원 일처리 순서로 진행되며 역시 비트.. 2025. 2. 6. [소프티어] 6250번 - 성적 평가 [Java] https://softeer.ai/practice/6250 1. 아이디어 참가자의 각 대회에서 등수와 모든 대회의 점수의 합의 등수를 출력해야하는 문제다. 참가자 번호, 참가자 점수, 참가자 등수를 필드로 갖는 클래스와 정렬을 통해 해결했다.2. 문제풀이 주어진 입력값을 받은 후 이를 참가자의 3가지 정보를 갖는 노드 배열로 반환하는 init 메서드를 활용했다. 노드 배열은 입력으로 참가자 번호와 참가자 점수는 알 수 있으므로 참가자 점수로 정렬을 해서 참가자의 등수를 구했고 이를 다시 참가자 번호로 정렬해서 원래 순서를 유지하도록 했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { .. 2025. 2. 6. [소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java] https://softeer.ai/practice/6277 1. 아이디어 N개의 수를 K개의 그룹으로 나눈 후 각 그룹에서 1개씩 K개를 뽑아서 만들 수 있는 최소 직사각형의 크기를 구하는 문제이다. 조합과 백트래킹을 활용하면 해결할 수 있다.2. 문제풀이 해당 문제에 대한 조합을 구현하는게 가장 어려웠는데 K번째 인덱스까지 갖는 리스트 배열을 생성한 후 입력을 받았다. 각 그룹의 점들은 인덱스를 통해 리스트로 받을 수 있게 했다. 이후 조합에서 그룹을 선택하는 idx 파라미터와 특정 위치를 선택하는 selIdx를 활용해서 현재 그룹의 각 점을 순회하며 선택하면 다음 그룹에서 다음 점을 선택하도록 했다.이렇게 구현하면 완전탐색으로 구현할 수 있는데 시간초과가 발생하게 돼서 백트래킹을 해줘야한다. 백트래.. 2025. 2. 6. [소프티어] 6247번 - 자동차 테스트 [Java] https://softeer.ai/practice/6247 1. 아이디어 정렬과 이분탐색을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 연비 중 3개를 뽑았을 때 중앙값이 M이 나오는 서로 다른 경우의 수를 구하는 문제로 주어진 연비를 정렬했을 때, 주어진 M이 연비들에 존재하면 (M보다 작은 연비의 개수) * (M보다 큰 연비의 개수)가 서로 다른 경우의 수가 된다. 주어진 M이 연비들에 존재하지 않으면 0을 출력해야한다. 이를 위해 주어진 연비를 배열에 담아 정렬한 후 이분 탐색을 진행했고 이분 탐색의 결과가 -1로 존재하지 않는다는 값을 받으면 0을 출력하고 아니면 해당 곱을 출력하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public cl.. 2025. 2. 6. [소프티어] 6246번 - 순서대로 방문하기 [Java] https://softeer.ai/practice/6246 1. 아이디어 N의 크기가 매우 작은 문제로 DFS 알고리즘을 활용하면 해결할 수 있는데 이때 방문해야하는 순서를 지키면서 모두 방문을 해야한다. 이를 위해 주어진 맵과 같은 크기의 맵에 방문해야하는 위치에 방문 순서를 저장한 pathOrder 2차원 배열을 활용해서 DFS에서 다음에 방문할 장소가 방문해야하는 지점이 아니면 일반 DFS를 적용하고 방문해야하는 장소면 순서가 맞는지 고려하는 방식으로 해결했다.2. 문제풀이 모든 경로를 탐색하기 위해 방문 체크 후 방문 체크 해제를 하는 DFS를 적용했다. 사방탐색을 하며 맵 바깥이거나 벽이거나 방문한 곳이면 넘어갔는데 그러면 탐색할 수 있는 장소는 일반 장소거나 방문해야하는 장소 두가지가 남는다.. 2025. 2. 6. 이전 1 다음
