[이코테][Java] 문자열 뒤집기
·
PS/이코테
문제 설명다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S = 0001100 일 때,1. 전체를 뒤집으면 11100112. 4번째 문자부터 5번째 문자까지 뒤집으면 111111이 되어서 두 번 만에 모두 같은 숫자로 뒤집을 수 있다.하지만 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 0000000이 되어서 한 번 만에 모두 같은 숫자로 만들 수 있다.문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요. 입력조건첫째 줄에 0과 1로만 이루어진 ..
[이코테][Java] 곱하기 혹은 더하기
·
PS/이코테
문제 설명각 자리의 숫자(0 ~ 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 '×' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.  입력조건첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S(1 출력조건첫째 줄에 만들어질 수 있는 가장 큰 수를출력입출력 예시입력예시출력예시02984576567210    문제 풀이어떤 두 수에 대한 연산을 수행할 때, 두 수 중 하나라도 '0' 또는 '1'일 경우에 ..
[이코테][Java] 모험가 길드
·
PS/이코테
문제 설명한 마을에 모험가가 N명 있습니다.모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높을수록 위험 상황에서 대처 능력이 떨어집니다.모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정 그룹에 넣을 필요는 없다. 입력조건첫째 줄에 모험가의 수 N(1 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분출력조건여행을 떠날 수 있는 그룹 수의 최대값을 ..
[이코테 ]그리디(Greedy) 알고리즘
·
PS/이코테
그리디 알고리즘이란?현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘즉, 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.정렬 알고리즘과 짝을 이뤄서 출제되는 경우가 많다. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해볼 수 있다. 하지만 그리디 알고리즘을 모든 상황에 적용할 수 있는 것은 아니다.현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.그렇기 때문에 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 방법인지 검토해야 한다.  대표적인 그리디 알고리즘의 문제로 '거스름돈' 문제가 있다.예제 1) 거스름돈손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구한다..
[백준][Java] 18870번 : 좌표 압축
·
PS/백준
[문제 링크]https://www.acmicpc.net/problem/18870문제 설명수직 선 위의 N개 좌표에 대해서 좌표 압축을 적용해서 출력Xi 를 좌표 압축한 결과 X'i는 Xi > Xj를 만족하는 Xj 의 개수(Xj는 모두 서로 다른 좌표이다)입력: N(좌표개수), N개의 좌표(X1, X2, ..., XN)출력: 좌표압축을 적용한 결과(X'1, X'2, ..., X'N)ex1) 2  4  -10  4  -9 의 좌표값이 주어졌을 때, 좌표압축한 결과는 2 3  0  2  1  이다.         2 보다 작은 값은 -10  -9,          4 보다 작은 값은 -10  -9  2,         -10 보다 작은 값은 없고,        -9 보다 작은 값은 -10ex2) 1000  9..
[백준][Java] 11720번 : 숫자의 합
·
PS/백준
[문제 링크]https://www.acmicpc.net/problem/11720문제 설명공백없이 쓰여진 N개의 숫자를 모두 합해서 출력입력 : N(숫자의 개수), N개의 숫자출력 : 숫자 N개의 합   문제 풀이N개의 숫자를 하나의 문자열로 입력받은 후, charAt() 함수를 사용하여 한 문자씩 가져와서 합을 구한다. 이 때, charAt() 함수로 반환된 값은 char형이기 때문에 해당 문자의 아스키코드 값을 반환한다.따라서 - '0' or -48을 해주어야 한다.(1) Scanner 사용import java.util.Scanner;public class Main1 { public static void main(String[] args) { Scanner sc = new Scanne..