Slow but steady wins the race

1. 문제

2. 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        HashMap<String,Integer> hm = new HashMap<>();
        String answer = "";
        
        for(String player : participant) 
            hm.put(player,hm.getOrDefault(player,0)+1);
        
        for(String player : completion) 
            hm.put(player,hm.get(player)-1);
        
        for(String key : hm.keySet())
            if(hm.get(key)!=0){
                answer = key;
                System.out.println(answer);
            }
        return answer;
    }
}

코드 긁고 싶은신 분들은 깃허브 참고

https://github.com/bosunKwak/Algorithm/blob/087df76cba0e8df56f8911237cda73c7f107eae0/hash/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0%EC%88%98.java

3. 풀이

자료구조 알고리즘 "해시"를 이용해서 풀면 훨씬 효율적인 코드를 짤 수 있다. 

해시에 관한 개념적인 설명은 다음 링크를 참고하면 된다. -> "작성중ㅎㅎ" 

처음엔 해시가 아니라, 다른 방식으로 구현했었다.

-> Arrays 메소드를 이용하여 participant, completion 각각 오름차순으로 정렬하여 앞 index부터 차례로 비교하고 다르거나 없는 경우에, 해당 participant를 출력하는 방법을 사용하였다. 

But, 이 문제의 본질(?)은 "해시"를 이용해야한다는 것! 

(1) HashMap 생성하기

HashMap<String,Integer> hm = new HashMap<>();

HashMap이란, Key-Value를 관리하는 클래스라고 할 수 있는데, <String, Integer>로 지정하면, Key는 String형, Value는 Integer형으로 정의한다는 뜻이다. 

(Key : Participant의 이름, Value : Count)로 사용

(2) HashMap에 Participant 추가 ( == 해싱(Hashing))

for(String player : participant) 
            hm.put(player,hm.getOrDefault(player,0)+1);

HashMap.put(Key,Value)함수는 HashMap에 Key와 Value를 한 쌍으로 입력하는 함수이고

HashMap.getOrDefault('a',0)함수는 'a'라는 Key에 해당하는 value가 존재하면 가져오고, 존재하지 않으면 0을 default로 지정하여 사용하겠다는 뜻의 함수이다. 

(3) HashMap에서 Complement 빼기 

for(String player : completion) 
            hm.put(player,hm.get(player)-1);

추가할 때와 동일하게 HashMap.put함수를 사용한다. 

HashMap에 존재한다면  Value가 1이상으로 표시되어있을 것이고 해당 Value를 1을 빼준다.  

(4) Value가 0이 아닌 Participant 찾아 출력

for(String key : hm.keySet())
            if(hm.get(key)!=0){
                answer = key;
                System.out.println(answer);
            }

HashMap을 돌면서 Value가 0이 아닌 Participant를 찾는다. 

HashMap.keySet()함수는 HashMap의 전체 Key의 배열을 반환하는 함수이고, 

HashMap.get(key)함수는 Key에 해당하는 Value를 반환하는 함수이다. 

4. 링크

https://programmers.co.kr/learn/courses/30/lessons/42576

1. 문제

문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다.

2. 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			
			for(int i=0;i<n;i++) {

				int num = sc.nextInt();
				String str = sc.next();

				for(int j=0;j<str.length();j++) {
					for(int k=0;k<num;k++) {
						System.out.print(str.charAt(j));
					}
				}
				System.out.println();			
			}		
			sc.close();		
	}

}

3. 풀이

처음엔 엄청 복잡하게 생각했었는데, 자바 메소드를 이용하면 별거 아닌 문제였다. 내 고민은 크게 두가지였다.

(1) "3 ABC" 와 같이 반복할 횟수와 문자열을 어떻게 입력받고 분리할지? 

(2) "ABC" 문자열의 각 원소"A","B","C"를 어떻게 뽑아낼까,, split을 이용해서 분리를 해야되나..?

이것 저것 방법을 찾아보니 해결방법은 별거 아니었다

(1) 각각 따로 입력받으면 된다. 한 줄씩 입력받지 않고 scanner.nextInt()와 scanner.next()를 이용해서 따로 입력받으면 된다. 한 줄! 이라는 생각을 버리면 된다.

대신 유의할 점은 nextLine()으로 입력받으면 안된다! 입력과정에서 엔터값을 입력받을 때까지 공백을 포함해서 한줄을 읽어버린다.

처음에 생각한 방식은 nextLine()을 이용해서 split(" ")을 통해 나눌 생각이었지만, 더 편한 방법이 있기에 취소

(2) charAt을 이용해서 문자 뽑기

String변수.charAt(index)를 이용하면 index에 해당하는 문자를 뽑을 수 있다

4. 링크

https://www.acmicpc.net/problem/2675

1. 문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

2. 전체 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();
		byte[] byte_S = S.getBytes(); 

		for(int j=97;j<=122;j++) {
			int cnt=0;
			for(int i=0;i<byte_S.length;i++) {
				if(j==byte_S[i]) {
					if(cnt==0) System.out.print(i+" ");
					cnt++;
				}
			}
			if(cnt==0)	System.out.print("-1 ");
		}
		
		sc.close();
	}

}

3. 풀이

byte[] byte_S = S.getBytes(); 

입력받은 문자열 S를 byte배열로 바꿔주는 이유는 해당 문자의 ASCII코드 값을 불러오기 위함이다.

문자열의 각 문자들의 ASCII코드 값을 byte_S 배열에 저장한다. 

for(int j=97;j<=122;j++) {
			int cnt=0;
			for(int i=0;i<byte_S.length;i++) {
				if(j==byte_S[i]) {
					if(cnt==0) System.out.print(i+" ");
					cnt++;
				}
			}
			if(cnt==0)	System.out.print("-1 ");
		}

97부터 122는 a부터 z까지의 ASCII 코드값이다. 

<안쪽 반복문>

문자열의 길이는 모르므로, byte_S.length (byte_S배열의 길이)만큼 반복문을 돌린다. 아스키 코드값과 byte_S[i]값이 일치하면, cnt를 1씩 증가하도록 한다.

cnt를 1씩 증가시키기 전에 cnt==0이면 출력하게끔 하면, 문자열의 첫번째로 나오는 경우에만 출력된다. 

예를 들면 hello 의 경우, l은 두번 나오지만, 첫번째 l을 만나면 먼저 해당 값을 출력하고, cnt를 1증가 시켜 다음 l을 만났을 경우에는 출력이 되지 않도록 한다. 

<바깥 반복문>

cnt의 값이 0인 경우, -1을 출력하도록 한다. (문자열에 포함되지 않는 문자들)

4. 링크

www.acmicpc.net/problem/10809

x와 y의 값이 있다고 할 때, x와 y값을 서로 바꾸는 과정은 아래와 같다.

1. x값을 tmp에 보관

2. y값을 x에 대입

3. tmp에 보관한 값(처음 x값)을 y에 대입

배열요소를 이용하면 x와 y대신 arr[x] arr[y]라 쓸 뿐 과정은 동일하다.

tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;

이렇게 두 요소를 교환하는 것은 꽤 자주 나오는 유형이기 때문에, swap이라는 메소드로 구현하는 것이 좋다.

public static void swap(int[] arr,int idx1, int inx2){
	int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

드모르간 법칙이란??

'각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래 조건과 동일하다'

코드를 예로 들어 표현하면,

(num<10||num>99)

위와 같은 제어식이 있다고 하자, 이 식은 "!"(※ 논리 부정 연산자)를 이용하여 아래와 같이 표현할 수 있다.

!(num>=10&&num<=99)

두 식이 의미하는 바는 동일하다.. 이를 드모르간 법칙이라 한다.

참고로, 위 제어식은 단축평가(short circuit evaluation)이라고도 한다.

단축평가란,

논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 결정되는 경우, 오른쪽 피연산자의 평가를 수행하지 않는 것이다. 

&&의 경우,

T && T = T

T && F = F

F && T = F

F && F = F

왼쪽 피연산자가 False가 나왔을 경우, 해당 제어식의 결과는 False이므로, short circuit evaluation이다.

||의 경우,

T || T = T

T || F = T

F || T = T

F || F = F

왼쪽 피연산자가 True가 나왔을 경우, 해당 제어식의 결과는 True이므로, short circuit evaluation이다.

3개의 정수 값 중 최댓값을 구하는 프로그램

코드를 먼저 보여주자면

import java.util.Scanner;
public class Max3 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.print("a: "); int a = sc.nextInt();
        System.out.print("b: "); int b = sc.nextInt();
        System.out.print("c: "); int c = sc.nextInt();

        int max = a;
        if(b>max) max=b;
        if(c>max)  max=c;

        System.out.println("max : "+max);
        sc.close();
    }
}

정수 a,b,c를 입력받고, 최댓값(max)을 찾아낸다. 알고리즘(과정)은 다음과 같다. 

1. max 변수에 a값을 대입한다.

2. b값이 max값보다 클 경우, max값에 b값을 대입한다.

3. c값이 max값보다 클 경우, max값에 c값을 대입한다.

이렇게 여러 process(문장)들이 순차적으로 진행되는 구조를 순차적 구조(concatenation structure)라 한다. 

a=5, b=8, c=3 이라고 가정해보자. 위 코드를 실행시켜보면

1. max =5

2. (b>max)? true이므로 max = 8

3. (c>max)? false이므로 max = 8

참고로, 코드를 짤 때는 위와 같이 main 클래스 안에 해당 알고리즘을 구현하는 것보다 아래와 같이 하나의 메소드(method)를 새로 만들어 구현하는 것이 좋다.

public class Max3 {
    static int max(int a,int b, int c){
        int max = a;
        if(b>max) max=b;
        if(c>max)  max=c;

        return max;
    }
    public static void main(String[] args){
        
        System.out.println("max(5,8,3)="+max(5,8,3));
    }
}

3개뿐만아니라 4개,5개,,, 모두 동일한 방식으로 적용할 수 있다.

해당 정수들을 배열로 입력받았다면??

어려울 것 없다. 똑같이 하면된다. 

배열의 첫번째 요소를 max변수에 대입한 후에, 두번째요소, 세번째요소, 등과 비교하면서 큰 값을 max에 대입하면 된다.

import java.util.Scanner;
public class MaxOfArray {
    static int maxOfArray(int []a){
        int max = a[0];
        for(int i=0;i<a.length;i++){
            if(a[i]>max)    max=a[i];
        }

        return max;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.println("max="+maxOfArray(arr));
    }
}

1. 문제

N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.

2. 코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String num = sc.next();
		int sum=0;
		for(int i=0;i<N;i++) {
			sum+=num.charAt(i)-48;
			
		}
		System.out.println(sum);
		sc.close();
	}

}

3. 풀이

공백없이 숫자N개를 입력받는다? => 문자열로 입력받는다? 이런 생각의 흐름을 거쳤다

막상 문자열로 입력을 받고 보니, 문자열에서 하나씩 뽑아 숫자를 출력해야하는데 charAt은 해당문자의 아스키코드값을 반환하기 때문에 48을 빼주거나 '0'을 빼줘야 한다.

num에 123이 저장되어 있다는 가정하에 num.charAt(0)을 출력하면 1이 아닌, 49가 출력된다. 따라서 48을 빼주는 것이다. 48은 '0'의 아스키코드 값이기 때문에 48대신 '0'을 빼도 무방하다.

4. 링크

www.acmicpc.net/problem/11720