P-coding

이번 글에서는 백준 26069번 문제를
hashSet를 활용해서 풀어보자

문제 핵심

• N : 사람들이 만난 기록 수
• 최대 길이 20의 문자열인 다른 문자열 A와 B가 공백과 함께 한줄에 주어진다.
• ChongChong 기록에서 1회 이상 주어짐
• ChongChong을 만난 사람은 무지개 댄스에 감염
  • ( ChongChong과 chongchong은 다른 이름 )

풀이 과정

ChongChong을 만난 순간 무지개 댄스를 추게 된다.

즉, 무지개 댄스를 한 명이라도 추고 있다면 모두 HashSet에 넣는다.

(Hash)Set에서는 중복값을 제외시켜 저장하기 때문에 모든 입력이 끝난 후  HashSet의 크기를 측정 한다. 

핵심 코드

1. 한 줄씩 읽어온다.

2. 두 사람 모두 댄스를 무지개 댄스를 추는지 확인

3. 한 명이라도 춘다면 HashSet에 삽입

        rainbowDanceHumans.add("ChongChong");
        for (int i = 0; i < N; i++) {
           stringTokenizer = new StringTokenizer(bufferedReader.readLine());
           String firstPerson = stringTokenizer.nextToken();
           String secondPerson = stringTokenizer.nextToken();

           if(rainbowDanceHumans.contains(firstPerson) || rainbowDanceHumans.contains(secondPerson)) {
               rainbowDanceHumans.add(firstPerson);
               rainbowDanceHumans.add(secondPerson);
           }
        }

Set에 특성만 활용한다면 아주 쉽게 풀 수 있는 문제이다.

(추가) 다들 환절기에 몸 조심 하시길 바랍니다.
두통에 2일 간 작성하지 못했네요..
백준 문제뿐만 아니라 Java class나 다양한 예제로 찾아 뵙겠습니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        int N = Integer.parseInt(bufferedReader.readLine());

        HashSet<String> rainbowDanceHumans = new HashSet<>();

        rainbowDanceHumans.add("ChongChong");
        for (int i = 0; i < N; i++) {
           stringTokenizer = new StringTokenizer(bufferedReader.readLine());
           String firstPerson = stringTokenizer.nextToken();
           String secondPerson = stringTokenizer.nextToken();

           if(rainbowDanceHumans.contains(firstPerson) || rainbowDanceHumans.contains(secondPerson)) {
               rainbowDanceHumans.add(firstPerson);
               rainbowDanceHumans.add(secondPerson);
           }
        }

        System.out.println(rainbowDanceHumans.size());

    }
}

이번글에서는 백준 25192번 문제를 통해 집합과 맵에 대해 알아보고자 한다.
원래는 집합과 맵에 대해 설명하고 문제를 포스팅하지만,
해시, 트리, 맵, 집합 자바에서는 함께 사용되기 때문에
추후에 포스팅 하려고 한다.

문제 핵심

• N : 채팅방 총 기록 수
• ENTER : 사람의 입장
• 나머지 : 유저의 닉네임
• 구하려는 값 : 곰곰티콘 사용횟수

풀이 과정

채팅 봇으로 ENTER이후 처음으로 나타난 닉네임은 인사하는 곰곰티콘이다.

즉, 동일한 닉네임이 두번 나타났다면 일반채팅으로 곰곰티콘이 아니다.

우리는 곰곰티콘을 사용하는 순간으로 ENTER 이후 나타나는 닉네임을 한 번씩 체크하면 된다.

즉, Set 클래스를 이용해서 중복없이 저장하여 그 크기를 통해 알 수 있다.

핵심 코드

1. 한 줄씩 읽어온다.

2. ENTER인 HashSet을 초기화

3. 존재하지 않는 경우에만 값을 넣고 카운트 증가

HashSet<String> nickNames = new HashSet<>();

for (int i = 0; i < recordCount; i++) {

    String line = bufferedReader.readLine();

    if(line.equals("ENTER")) {
        nickNames.clear();
        continue;
    }

    if(!nickNames.contains(line)){
        nickNames.add(line);
        bearGreetCount++;
    }
}

다른 풀이

HashSet 클래스를 사용하며 Set이라는 클래스 의미를 생각하면 사실 위 코드는 Set 보다는 Hash를 이용하여 값을 빨리 찾아내는 방식이다. Set이라는 클래스도 모두 이용하려면 다음과 같다.

1. ENTER가 나온 경우에만 지금까지 넣었던 값 개수를 카운트 해주고 초기화 한다.

2. 이후 반복문이 종료된 이후에는 카운트 되지 않은 값들이 남아있기 때문에 추가로 카운트 한다.

HashSet<String> nickNames = new HashSet<>();

for (int i = 0; i < recordCount; i++) {

    String line = bufferedReader.readLine();

    if(line.equals("ENTER")) {
    	bearGreetCount += nickNames.size();
        nickNames.clear();
        continue;
    }

    nickNames.add(line);

}

bearGreetCount += nickNames.size();

이번 문제에서 사용한 HashSet 또한 다른 문제 풀이에 자주 사용되는 클래스이다.
Hash, Set, Map, Tree 등 다양한 구조를 이해하는 것이 좋다.
기본 구조로써 기본 개념을 숙지하고 넘어가자.

전체 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int recordCount = Integer.parseInt(bufferedReader.readLine());

        int bearGreetCount = 0;

        HashSet<String> nickNames = new HashSet<>();

        for (int i = 0; i < recordCount; i++) {

            String line = bufferedReader.readLine();

            if(line.equals("ENTER")) {
                nickNames.clear();
                continue;
            }


            if(!nickNames.contains(line)){
                nickNames.add(line);
                bearGreetCount++;
            }
        }

        System.out.println(bearGreetCount);
    }
}

이번 글에서는 백준 1037번 문제를 통해,
알고리즘 기본 문제 단골인 소수, 약수, 공배수 들 중 하나인 약수를 활용하여 문제를 풀어보자

문제 핵심

• 첫째 줄 : 약수의 개수
• 둘째 줄 : 약수들
• 구하려는 정수 : N
  • ( 풀이 과정에서는 구하려는 정수 N을 x라고 설명 )

풀이 과정

자연수 x을 구하려면 1과 x을 제외한 주어진 약수 중에서 선택해야 한다.

만약 이 때 조건과 같이 30의 약수를 차례대로 나열하면 [ 2, 3, 5, 6, 10, 15 ] 이다.

그렇다면 양쪽에서 순서대로 모두 짝지어서 곱한다면 x인 30을 구할 수 있다.

즉, 제일 큰 값과 작은 값을 구한 후 곱해주면 된다.

핵심 코드

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    if(num > max) {
        max = num;
    }
    if(num < min) {
        min = num;
    }
}

예외

9와 같은 약수는 1과 9는 제공되지 않기 때문에 3 숫자 하나만 주어진다.

이때 3의 제곱이 x가 되므로 첫째 줄이 1이라면 제곱해준다.

if(N == 1) {
    int num = Integer.parseInt(bufferedReader.readLine());
    stringBuilder.append(num * num);
}

단계적 풀이에서 브론즈 문제 수준으로
사실 비교적 아주 쉬운 문제이다.

이제는 마지막 브론즈 문제로 앞으로는 실버 상위부터 골드 문제가 다량으로 나올 예정이다.
지금까지 기초와 개념을 활용한다면 문제없이 풀 수 있을 것이다.

전체 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        if(N == 1) {
            int num = Integer.parseInt(bufferedReader.readLine());
            stringBuilder.append(num * num);
        } else {
            int max = 0;
            int min = Integer.MAX_VALUE;

            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(stringTokenizer.nextToken());
                if(num > max) {
                    max = num;
                }
                if(num < min) {
                    min = num;
                }
            }

            stringBuilder.append(max * min);
        }

        System.out.println(stringBuilder);

    }
}