반응형

전체 글 108

[JAVA] 백준 15970번 : 화살표 그리기(한국정보올림피아드/KOI 2018/초등부)

www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들� www.acmicpc.net 문제 각 점에서 색깔이 같은 가장 가까운 점과 연결한 화살표들의 길이 합을 구하는 문제이다. 해결 방안 색깔마다 점의 배열을 만들어서 정렬을 한 뒤 각 점에서 가장 가까운 선(왼쪽 혹은 오른쪽)을 구해서 더해주면 되겠다고 생각하였다. HashMap을 사용하여 점들의 색깔마다 ArrayList(점의 위치 배열)를 만들어주었다. 그 후 색깔마다 점의 위치 배열을 정렬해주고 각 점에서 가장 가까운 점까지의..

[JAVA] 백준 17609번 : 회문(한국정보올림피아드/KOI 2019 1차대회/초등부)

www.acmicpc.net/problem/17609 문제 회문인지, 유사 회문(한글자만 삭제하면 회문이 되는 경우)인지, 일반 문자열인지 확인하는 문제이다. 해결 방안 주어진 단어의 첫 부분은 증가시키고 끝 부분은 감소시키면서 비교해온다. 이 때 단어의 변화되는 첫 부분 문자와 끝 부분의 문자가 가운데에 올 때가지 같으면 회문(0)이다. 그렇지 않은 경우 첫 부분을 하나 증가시키거나 끝 부분을 하나 감소시켜서 한 글자를 삭제 시켜서 확인을 해보고 둘 중 하나의 경우라도 회문이면 유사회문(1)이고 둘다 안되면 일반 문자열(2)인 경우이다. 이를 코드로 나타내면 아래와 같다. 코드 import java.io.BufferedReader; import java.io.IOException; import java..

[JAVA] 백준 17608번 : 막대기(한국정보올림피아드/KOI 2019 1차대회/초등부)

www.acmicpc.net/problem/17608 문제 해결 방안 뒤에서부터 확인을 하므로 Stack을 이용하여 구현하였다. 기준 막대기높이(standard)보다 비교하는 막대기높이(current)가 크면 갯수를 하나씩 늘려주고 standard를 current로 바꿔준다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; // 막대기 public class Main { public static void main(String[] args) throws IOException { Stack stack = new Stack(); BufferedR..

[JAVA] 백준 17616번 : 등수 찾기(한국정보올림피아드/KOI 2019 2차대회/초등부)

www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어�� www.acmicpc.net 문제 그래프를 만들어야 되는 문제라고 생각은 했으나 어떻게 문제를 접근해야할지 몰라서 다른사람 풀이 참고함 참고 블로그: home-body.tistory.com/646 해결 방안 가능한 가장 높은 등수 U와 가능한 가장 낮은 등수 V를 구하는 문제이다. 크게 보자면 단방향 그래프로 lower_graph와 higher_graph 두개를 이용해서 ..

[JAVA] 백준 17615번 : 볼 모으기(한국정보올림피아드/KOI 2019 2차대회/초등부)

문제 그리디 문제이다. 해결 방안 처음에 R과 B의 갯수를 각각 세어서 rCnt, bCnt에 저장해준다. 그리디 문제로 볼을 이동하는 4가지 방법 중 최소 이동횟수를 구하면 된다. 1. R공을 모두 왼쪽으로 이동 문제의 그림1을 볼때 RRRRBBBB로 나열하기 위해서는 첫번째 R을 제외하고는 다 옮겨줘야 한다. 따라서 왼쪽에 R이 계속 있을경우 cnt를 세어준다음 Rcnt-cnt는 이동해야하는 R공의 갯수가 된다. ex) RBBBRBRRR인 경우 첫번째 R이 있으므로 cnt = 1이된다. 따라서 Rcnt(5)-cnt(1)=4가 되고 실제로 왼쪽으로 이동해야하는 R공의 갯수가 된다. 2. R공을 모두 오른쪽으로 이동 3. B공을 모두 왼쪽으로 이동 4. B공을 모두 오른쪽으로 이동 2,3,4번도 뒤에서부터..

[JAVA] 백준 17614번 : 369(한국정보올림피아드/KOI 2019 2차대회/초등부)

www.acmicpc.net/problem/17614 문제 369 규칙에 맞게 1~N까지 나왔을때 N까지 박수의 총 횟수를 출력하는 것이다. 해결 방안 1~N까지 완전 탐색을 해주며 각 수의 자릿수들이 3,6,9인경우 result 변수를 하나씩 증가해주었다. ex) 13 이면 박수 한번 33이면 박수 두번 가 되야 하므로 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 한국정보올림피아드 // KOI 2019 2차대회 초등부 // 369 public class Main { public static void main(String args[]) throws Exception { Bu..

[JAVA] 프로그래머스 : 키패드 누르기 (2020 카카오 인턴십)

programmers.co.kr/learn/courses/30/lessons/67256?language=java 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 그냥 구현 문제 입니다. 문제에 주어진 조건에 맞춰 풀면 되는 문제이다. 해결 방안 키패드의 위치를 x, y로 생각해주었다. 00~02 .. 30~32 1. 일단 문제의 조건4에서 2,5,8,0 숫자 키패드가 나온경우 두 엄지손가락의 현재 키..

[JAVA] 프로그래머스 : 폰켓몬 (찾아라 프로그래밍 마에스터)

programmers.co.kr/learn/courses/30/lessons/1845?language=java 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. � programmers.co.kr 해결 방안 고를 수 있는 폰켓몬 중 종류의 최댓값을 구하는 문제이다. 따라서 HashMap에 key값을 종류, value 값을 종류의 갯수로 넣고 pick해야하는 갯수보다 map size가 크면 종류의 갯수가 더 많은 것이므로 전체 다 다른 종류를 고를 수 있게 되서 answer = pick이 된다. pick해야하는 갯수보다 map size가 작..

[JAVA] 프로그래머스 : 숫자 게임 (Summer/Winter Coding(~2018))

programmers.co.kr/learn/courses/30/lessons/12987?language=java 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 해결 방안 문제에서 원하는 것은 B의 최대 승점이므로 A가 최소인 경우부터 차근차근 B가 높을 때의 갯수를 구해준다. A와 B 배열을 오름차순으로 정렬해준다. A 작은 수부터 B와 비교를 해주는데 이때 B의 배열을 하나씩 증가하면서 해준다. 이 때 B 배열의 index 시작 값은 A[i] < B[j] 보다 큰 경우가 됬을 때 idx ..

[JAVA] 프로그래머스 : 점프와 순간 이동 (Summer/Winter Coding(~2018))

programmers.co.kr/learn/courses/30/lessons/12980?language=java 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈� programmers.co.kr 해결 방안 처음에는 문제에서 제시된 해결 방안을 보고 탐색을 이용한 최소 값을 구하려고 하였으나 depth가 정해져 있지 않고 입력으로 주어진 n이 10억이 넘는 것을 보고 다른 방법을 생각해보게 되었다. n이 정해져 있고 최소 건전지 사용량도 정해져 있다고 생각하게 되었고 문제에서 주어진 5와 6을 이용해 가장 좋은 방법을 ..

반응형