07 Sep 2018
HackerRank link
Bigger is Greater
풀이 핵심
입력의 바로 다음 큰 문자열을 잘 만들어 내는 것이 핵심.
Algorithm
- String 입력을 Integer로 변환 한다. (편의성을 위해)
- 바로 다음 수를 구한다.
다음수를 구하는 방법
ex) dabbcca
- 바뀌어야 되는 지점을 찾는다. (내림차순 순의 처음지점): dabbcca
- 바로 큰수와 교환 : dabbcca → daccba
- 바뀌어야 되는 지점이후 우측은 거꾸로 돌려준다. : dabccba → dabcabc
Source Code
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static boolean getNextNum(int[] n)
{
boolean debugPrint = false;
if(n.length == 1) return false;
// find position that will be changed
int i = n.length - 1;
if(debugPrint) System.out.print(i+"->");
while((i-1>=0) && (n[i-1] >= n[i]))
{
i--;
}
i--;
if(debugPrint) System.out.println(i);
if(i < 0) return false;
// find bigger number of n[i]
int j = n.length - 1;
while(n[i] >= n[j])
{
j--;
}
if(debugPrint) System.out.println(j);
int temp = n[i];
n[i] = n[j];
n[j] = temp;
j = n.length - 1;
i++;
while (i < j) {
temp = n[i];
n[i] = n[j];
n[j] = temp;
i++;
j--;
}
return true;
}
static String biggerIsGreater(String w) {
// Complete this function
int[] wi = new int[w.length()];
for(int i = 0 ; i < w.length() ; i++)
{
wi[i] = w.charAt(i) - 'a';
}
// next number
if(getNextNum(wi) == false) return "no answer";
else
{
char[] str = new char[wi.length];
for(int i = 0 ; i < wi.length ; i++)
{
str[i] = (char)((char)wi[i] + 'a');
}
return new String(str,0,str.length);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for(int a0 = 0; a0 < T; a0++){
String w = in.next();
String result = biggerIsGreater(w);
System.out.println(result);
}
in.close();
}
}
05 Sep 2018
HackerRank link
Organizing Containers of Balls
풀이 핵심
각 타입의 총 수와 각 컨테이너가 갖고 있는 ball의 총 수가 일치 해야 함.
ex)
type 0번의 총 갯수가 1, container 0의 총 갯수는 2
type 1번의 총 갯수가 3, container 1의 총 갯수는 2
container의 0에 type 0을 다 swap해서 넣는다고 할때,
type 0은 1개만 있어서 container 0에서 총 담아야 하는 갯수는 1개이다.
하지만, container 0은 총 2개를 담고 있으므로, 절대 type 0만 담을 수 없다.
Algorithm
- type 별 총 갯수를 구한다. (각 행의 합)
- container가 갖고 있는 수를 구한다. (각 열의 합)
- 한쪽으로 각 타입을 몰아 넣는다. (정렬한다)
- 타입의 총 수와 conatainer의 총수가 일치 하는지 확인.
Source Code
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static String organizingContainers(int[][] container) {
// Complete this function
boolean debugPrint = true;
long[] sumRow = new long[container.length];
long[] sumCol = new long[container[0].length];
// sum col
for(int i = 0 ; i < container.length ; i++)
{
for(int j = 0 ; j < container.length ; j++)
{
sumRow[i] += (long)container[i][j];
}
}
// sum row
for(int i = 0 ; i < container.length ; i++)
{
for(int j = 0 ; j < container.length ; j++)
{
sumCol[i] += (long)container[j][i];
}
}
Arrays.sort(sumRow);
Arrays.sort(sumCol);
for(int i = 0 ; i < sumRow.length ; i++)
{
if(sumRow[i] != sumCol[i]) return "Impossible";
}
return "Possible";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for(int a0 = 0; a0 < q; a0++){
int n = in.nextInt();
int[][] container = new int[n][n];
for(int container_i = 0; container_i < n; container_i++){
for(int container_j = 0; container_j < n; container_j++){
container[container_i][container_j] = in.nextInt();
}
}
String result = organizingContainers(container);
System.out.println(result);
}
in.close();
}
}