본문 바로가기

Algorithm221

[백준] 13701: 중복 제거 - JAVA https://www.acmicpc.net/problem/13701 풀이정수를 입력받으면서 부른적이 없는 정수만 출력하는 문제이다. set자료구조를 생각했지만 메모리 제한때문에 비트마스킹으로 풀어야한다. N의 범위는 2^25로 주어져있다. int범위는 32bit까지 담을 수 있기 때문에 32개의 숫자를 중복검사할 수 있다. 따라서, 2^25개의 수를 중복검사하려면 2^20크기의 배열을 만들어 배열의 원소 한 개가 32개의 숫자를 중복검사하도록 구현해야 한다. `int[] number = new int[1   메모리: 350208KB시간: 1388ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void.. 2024. 5. 18.
[프로그래머스] 양과 늑대 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다. 트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다. 이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다. 이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다. 리스트에서 노드를 제거할 때 Conc.. 2024. 5. 18.
[백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18.
[프로그래머스] 카드 짝 맞추기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이4 X 4 크기의 보드에 카드를 뒤집어 짝을 맞춰서 제거해야 한다. 카드 짝이 맞게 2개씩 위치를 저장해놓았다. 순열을 통해 제거할 카드 번호의 순서를 정해놓았다. 정해놓은 순서대로 제거해서 최소 이동을 계산하여 정답을 갱신했다.  메모리: 74.5MB시간: 1.17ms언어: Java 11import java.util.*;class Solution { static class Node { .. 2024. 5. 18.
[프로그래머스] 파괴되지 않은 건물 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이N X M 크기의 영역이 주어지고, 각 영역을 사각형 크기의 영역을 정해 일정 수를 더하고 빼주게 된다. 누적합을 이용하는 문제였다. (a, b) 부터 (c, d) 까지의 사각형에 5씩 더해주기 위해서는arr[a][b] += 5arr[a+1][b+1] += 5arr[a][b+1] -= 5arr[a+1][b] -= 5위처럼 더해주면 된다. 이렇게 수를 저장한 뒤 행마다 왼쪽에서 오른쪽으로 누적합해주.. 2024. 5. 18.
[백준] 24042: 횡단보도 - JAVA https://www.acmicpc.net/problem/24042 풀이1 ~ N 까지 영역이 있고 각 영역을 잇는 횡단보도를 통해 건널 수 있다. M개의 횡단보도가 켜지는 순서대로 주어진다. 즉, 첫번째 횡단보도는 0, M, 2M... 시간에 켜지고, 두번쨰 횡단보도는 1, M + 1, 2M + 1... 시간에 켜진다. 켜지는 시간을 가중치로하여 다익스트라 알고리즘을 수행하면 된다. 현재 시간보다 다음 건널 횡단보도에 적힌 시간이 작다면 더 커질때까지 M을 더해야 한다. `long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;` 위 식으로 계산할 수 있었다.  메모리: 222712KB시간: 1292ms언어: Java 11import.. 2024. 5. 18.
[백준] 16120: PPAP - JAVA https://www.acmicpc.net/problem/16120 풀이문자열을 앞에서부터 보면서 'PPAP'가 되면 'P'로 바꿔준다. 최종적으로 'P'가 되면 성공. P가 들어오면 cnt를 1 늘려준다. A가 들어올 때 cnt가 2보다 작다면 PPAP를 만들수 없으므로 실패. cnt가 2이상이고, 다음 글자가 P라면 PPAP를 만들 수 있으므로, cnt를 1 줄여준다(P가 2개 빠지고 새로운 P가 들어오기 때문).  메모리: 20080KB시간: 260ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new .. 2024. 5. 18.
[백준] 5464: 주차장 - JAVA https://www.acmicpc.net/problem/5464 풀이주자창의 칸별로 요금이 책정되어있고, 차량의 무게 \* 요금이 해당 차량의 무게가 된다. ParkingLot이라는 클래스를 만들었다. 주차장의 사이즈를 받아 배열을 선언하고, 메서드로 빈 칸이 있는지 보는 isEmpty(), 차량이 들어올 때 enter(), 차량이 나갈 때 요금정산까지 하는 out()메서드를 만들었다. 동작을 입력받으면서 주차장이 꽉 차서 못들어오는 차량의 대기열로 queue를 이용했다.  메모리: 14724KB시간: 160ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class ParkingLot { int[].. 2024. 5. 18.
[프로그래머스] 광고 삽입 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이시청자의 시청 시작, 종료 시각이 주어지고, 광고 지속 시간이 주어진다. 광고 지속 시간동안 누적 재생 시간이 가장 많은 구간을 골라야 한다. 누적합을 이용했다. 시청 시작시간에 +1 하고, 종료시간에 -1을 해놓고 누적합 배열을 끝까지 가면서 `preSum[i] += preSum[i - 1]` 해줬다. 누적합 배열을 완성한 후, 0 ~ 광고시간 까지를 첫 기준으로 삼아 1씩 늘려가면서 비교하며 .. 2024. 5. 18.
[백준] 1497: 기타콘서트 - JAVA https://www.acmicpc.net/problem/1497 풀이처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다. 따라서 boolean 이차원 배열을 만들어 체크했다. N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다. 비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.for (int i = 1; i 1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다.  메모리: 14548KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { .. 2024. 5. 18.

티스토리툴바