본문 바로가기

알고리즘146

20230702 [Java] 문제풀이 20230702 [Java] 문제풀이 [프로그래머스] 덧칠하기 페인트 칠을 하는 것이고, 칠해야 하는 구역 section이 주어지고, 한번에 칠할 수 있는 길이 m이 주어진다 여기서, 페인트 칠은, 칠해야 하는 구역은 무조건 칠해야 하고, 이미 칠해진 곳에 덧칠할 수 있다 max 라는 변수를 만들어서, 페인트 칠을 할 수 있는 마지막 구역을 정해준다 max 안에 들어간 구역들은, 한번에 페인트 칠이 될 수 있는 공간이다 section[i] 2023. 7. 2.
[Java] 자료구조 - 트라이 [Java] 자료구조 - 트라이 트리 형태의 자료구조로 문자열을 저장, 삭제, 탐색을 빠르게 하기 위해 만들어졌다 비슷한 문자를 굳이 따로따로 저장할 필요가 없어진다 예) act 와 action을 따로 저장하는 것 보단, action을 저장하고, action 안에 있는 act를 사용할 수 있게 만드는 것이다 단어를 트리에 추가 3가지 상황이 있다 3 가지 상황 모두, 끝의 알파벳을 단어의 마지막인 것을 표시해야 한다 단어가 트리에 아예 없거나, 단어가 다른 하나의 단어에 포함 되어 있을 때 부분 적으로 같은 알파벳을 두 단어가 가지고 있을 때 단어를 트리에서 삭제 트라이 구현 트라이 노드 만들기 트라이 노드에는 현재 노드가 단어의 마지막 알파벳인지 아닌지, 표시할 수 있는 속성을 넣는다 그리고 현재 노드.. 2023. 6. 30.
20230629 [Java] 문제풀이 20230629 [Java] 문제풀이 공원 산책 직사각형 모양의 공원 배열과, 로봇 강아지가 수행해야 하는 명령어가 주어진다 직사각형 모양에는 X (장애물), S (시작점), O (강아지가 갈 수 있는 곳)이 있다 명령어는 "방향, 이동하는칸" 이 주어진다 E 2 : 동쪽으로 2칸 W 1 : 서쪽으로 1칸 N 4 : 북쪽으로 4칸 S 3 : 남쪽으로 3칸 만약 명령어가 주어지는데, 장애물에 부딛히거나, 공원 밖으로 나갈 경우, 명령어를 실행하지 않고, 다음 명령어로 넘어간다 코드는 매우 길지만 간단하다 시작점의 좌표를 찾기 시작점 기준으로 명령어를 하나씩 꺼내보기 만약 현재 좌표에서 명령어를 실행했을 때에 공원 안으로 들어오면, 4번으로 넘어간다 for문을 통해, X, 즉 장애물이 있는지 확인을 해본다 .. 2023. 6. 29.
[Java] 자료구조 - 우선순위 큐 [Java] 자료구조 - 우선순위 큐 우선순위 큐 Queue라고 할 수 있지만, 큐는 먼저 들어온 값이 먼저 나가는 것라고 하면, 우선순위 큐는, 우선순위가 높은 값부터 먼저 나가는 것이다 만약 우선순위가 동일하다면, 먼저 들어온 값이 먼저 나가는 FIFO (First In First Out)이 적용이 된다 우선순위의 Enqueue와 Dequeue는 최소 힙 또는 최대 힙과 같다 자바에서는 PriorityQueue 클래스를 사용하면 된다 Heap으로 작동하는 클래스다 오름차순 PriorityQueue 클래스를 만들고, 만들어진 객체에, 값들을 넣으면 된다 숫자는 기본적으로 오름차순으로 바로 정렬이 된다 문자열이면 숫자 => 소문자 => 대문자 => 한글 순으로 정렬이 된다 import java.util... 2023. 6. 29.
20230628 [Java] 문제풀이 20230628 [Java] 문제풀이 달리기 경주 players 배열은, 경주가 시작할 때에, 선수들이 배치된 순서다 callings는, 선수 이름이 불릴 때마다, 앞에 선수와 순위가 바뀌는 것이다 즉 선수 이름이 불리면, 앞에 선수를 추월한 것이다 처음에는 너무 배열로 하겠다는 생각만 해서, 시간 초과가 나왔다 추후에 map을 사용해서 앞의 선수의 이름, 그리고 등수를 찾으면서, 배열에서 선수의 자리를 바꿔주었더니, 시간 초과를 해결할 수 있었다 import java.util.*; class Solution { public String[] solution(String[] players, String[] callings) { HashMap map = new HashMap(); for (int i = 0;.. 2023. 6. 28.
20230627 [Java] 문제풀이 20230627 [Java] 문제풀이 [프로그래머스] 안전지대 행렬이 주어진다 1은 지뢰가 있는 곳 그리고 0은 지뢰가 없는 곳이다 지뢰 기준으로 8방면 (위, 아래, 좌, 우, 대각선) 모두 위험 지역이다 위험 지역이 아닌 곳의 개수를 찾으면 된다 1) 델타 탐색 (dr, dc) 를 통해 1을 발견하면 8방면을 2로 만들어 준다 2) 그렇게 위험 지역을 1과 2로 표시하고, 다시 2중 for문을 통해 안전 지역인 0을 세준다 class Solution { public int solution(int[][] board) { int answer = 0; int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1}; int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1}; for (in.. 2023. 6. 27.
20230626 [Java] 문제풀이 20230626 [Java] 문제풀이 [프로그래머스] 한 번만 등장한 문자 문자열이 주어진다 문자열 안에, 단어가 한번만 나오는 단어를, 사전 순으로 정렬해서 출력을 한다 ASCII 코드를 사용하여, 단어들을 숫자로 바꾸고 Collections.sort(); 를 이용해서 정렬을 하고 단어로 바꿔준다 import java.util.*; class Solution { public String solution(String s) { String answer = ""; ArrayList sortList = new ArrayList(); int tempVal; HashMap hashMap = new HashMap(); // 단어의 개수를 해쉬에 넣는다 for (int i = 0; i < s.length(); i++.. 2023. 6. 26.
[Java] 자료구조 - 그래프 [Java] 자료구조 - 그래프 그래프란? 정점 (Vertex, Node)와 간선 (Edge)로 이루어져 있다 트리, 이진트리도 그래프의 한 종류인다 그래프는 무방향 그래프와, 방향 그래프가 있다 무방향 그래프는 정점과 정점 사이에 방향이 없는 그래프이다 (즉 모든 정점들은 서로 왕복을 할 수 있다) 방향 그래프 같은 경우 정점에서 어느 정점으로 갈 수 있는 방향이 정해져 있다 (방향이 정해져 있으면, 그 방향 밖에 갈 수 없다) 정점 (Vertex) : 노드(Node)라고도 하고, 값 또는 데이터를 저장한다 간선 (Edge) : 정점을 연결하는 선이다 분지수 (차수, degree) : 무방향 그래프에서 하나의 정점과 연결되어 있는 간선의 수 내향 분지수 (진출 차수, in-degree) : 방향 그래프.. 2023. 6. 26.
20230625 Java 문제풀이 20230625 Java 문제풀이 전국 대회 선발 고사 학생 3명을 선발하는 문제이다 문제에서는 학생들의 등수가 담긴 배열과, 학생들의 참여 여부가 담긴 배열이 주어진다 두 개의 배열을 탐색하며, 선발 고사를 참여하는 학생들 중, 높은 등수를 가진 학생들을 고른다 높은 등수부터 10000 * (제일 높은 등수) + 100 * (2번째 높은 등수) + (3번째 높은 등수) 의 식을 구하는 것이다 import java.util.*; class Solution { public int solution(int[] rank, boolean[] attendance) { ArrayList list = new ArrayList (); // number는 등수를 말하는 것 // 즉 등수는 1씩 증가할 것이고, 참가하는 학.. 2023. 6. 25.

티스토리툴바