수정해야함 알고리즘 풀시간이 부족해

알바? 회사에서 몰래 푸는 문제라 더 재밌었던건 안비밀이다.

실버5 문제이다

문제링크

문제

입력

출력

예제 입력 1

5
....X
..XX.
.....
.XX..
X....

문제를 해석해보자 NXN인 방이 하나 있다

그렇다면 내가 입력한 값이 방의 넓이가 되는구나 그러면 방을 하나 만들자 라고 생각했다.

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

방 생성
char[][] place = new char[n][n];

방을 생성하였으니 이제 방 안에 입력값을 넣어보도록 하자

for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                place[i][j] = s.charAt(j);
            }
        }

이제 준비물은 완벽해 졌다

요즘 나는 바로 문제를 풀어볼려고 하지 않고 메모장에 한번 입력예제를 적어보았다.

코드를 써내려가기전에 어떻게하면 될지 고민해보는 시간을 줄여주는거 같다 .

또한 회사 쉬는시간에 짬짬히 풀기에 나름 생각해본 방법이기도 하다.

( 아이패드가 고장나서 그림을 못그리는것도 있다 )

여튼 한번 메모장에 넣고 생각을해보았다.

이런 형태가 있을것이다

내가 찾아야하는건 누울 공간이다 문제를 보면 눕기 가능한 범위는 '.' 이 점이 2개 이상이여야한다.

그렇다면 내가 찾아야할 것은 세로의 눕기 가능한 공간의 횟수 + 가로의 눕기 가능한 공간의 횟수이다.

메모장 생각정리

 int vertical = 0;
 int horizontal = 0;

총 잘 수 있는 공간이 될 녀석들이다.

이 녀석들은 세로 와 가로의 '.'의 갯수를 세어주는 녀석들이다

int width = 0;
int hight = 0;

자 이제 조건을 다시 생각해보자

똑바로 '.'이 2개 이상 / 가로 세로 누울수있다.

난 총 2개의 거름망을 생성해야겠다고 생각했다

1. '.'일때 width의 갯수 증가
2. 값이 x 거나 or j == n-1일 경우라고 생각했다 
n-1 인 이유는 j가 숫자 인덱스가 4까지 때문이다.
3. 누울 공간이 2개 이상일때

place[i][j] = s.charAt(j);

이녀석의 세로값을 구하려면

place[i][j] 을 들어가보면 된다.

이 후 첫번째 거름망을 하나 설치해주자

만약에 세로 값에 '.' 이 있다면 
width의 값을 증가시켜주자 

만약에 가로 값에 '.' 이 있다면
hight의 값을 증가시켜주자.

이제 코드를 한번 봐보자

        for (int i = 0; i < n; i++) {
            // 몇칸 갔는지 ( ex : '.'
            int width = 0;
            int hight = 0;

            for (int j = 0; j < n; j++) {
                // 세로값구하기
                if(place[i][j] == '.'){
                    width++;
                }

여기까지 보았다면 그림판으로 그림을 그려보겠다

이렇게 될것이다

2번째 거름망을 설치해보겠다

 if(place[i][j] == 'X'  || j==n-1){
       if(width >= 2){
           horizontal++;
         }
     width = 0;
}

or 조건에서 'X'녀석을 만나게되어 마지막 거름망으로 '.'갯수가 2보다 크거나 같으면

세로로 누을공간++ 이렇게 해준것이다.

j==n-1 
이 부분이 이해가 가지않는다면 

이 부분을 생각하면 된다.

이후 2번째 세로의 '.'갯수를 구해주기위해 width를 초기화 시켜주었다.

이제 세로가 끝났으니 가로도 똑같은 매커니즘으로 구하면된다

코드

import java.util.List;
import java.util.Scanner;

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

        // 장소 생성
        char[][] place = new char[n][n];

        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                place[i][j] = s.charAt(j);
            }
        }

        // 총 잘 장소가 몇개 인지
        int vertical = 0;
        int horizontal = 0;

        for (int i = 0; i < n; i++) {
            // 몇칸 갔는지 ( ex : '.'
            int width = 0;
            int hight = 0;

            for (int j = 0; j < n; j++) {
                // 세로값구하기
                if(place[i][j] == '.'){
                    width++;
                }

                if(place[i][j] == 'X'  || j==n-1){
                    if(width >= 2){
                        horizontal++;
                    }
                    width = 0;
                }

                // 가로값 구하기
                if(place[j][i] == '.'){
                    hight++;
                }

                if(place[j][i] == 'X' || j== n-1){
                    if(hight >=  2){
                        vertical++;
                    }
                    hight = 0;
                }

            }
        }

        System.out.println(horizontal + " " + vertical);

    }
}

우선 풀기 전 문제를 이해를 해보도록하자

items라는 배열안에 각각 값들이 주어졌다.

순서대로 type , color , name 순이다 이후 다음 중 하나가 참일 경우 규칙과 일치하다고 한다.

ruleKey 가 type이면 ruleValue도 type 이다

다른 예로 들자면 ruleKey가 color면 ruleValue는 color의 값중 하나 예를들어 sliver 이런 식 일 것이다.

이 후 key값에 따른 value값으로 items 안에 어떤 인덱스가 value값을 포함하고 있는지 찾는 문제이다.

자 이제 입력 예시를 한번 보도록하자

List<List<String>> 형태로 들어가 있는 리스트 가 있다.

그림으로 표현하자면

이런 형태일 것이다 ( 악필 ㅈㅅ )

자 여기서 문제에 대해서 다시한번 떠올려보자

배열안에 들어가는 유형은 순서가 보장된다 절때 바뀌지않는다

그렇다면 key에 따라서 바뀌는 value값으로 배열에 있는 값을 비교해 탐색해주면 되지않을까 ?

라는 기가막힌 생각을 하게 된거다.

자 이제 코드를 써내려가 보도록하자.

int searchTpye = 0;

유형을 탐색해 줄 변수를 하나 만들어두자

이후

if(ruleKey.equals("color")){
            searchType = 1;
        }

        if(ruleKey.equals("name")){
            searchType = 2;
        }

각각 key에 따라 변수의 값을 재정의 해주자

key의 값에 따라서 value값이 바뀐다 
0은 기본 type , 1은 color , 2는 name 으로 바뀔것이다.

이후 우리의 정답이 될 변수를 하나 만들어주자
int answer = 0;

이후에 key값으로 인해 변화된 serachType 녀석으로 순회하며 ruleValue와 맞는 녀석이 나온다면 matches++ 시켜 답을 얻어가주자

 for (int i = 0; i < items.size(); j++) {
          if(items.get(i).get(searchType).equals(ruleValue)){
                matches++;
           }
       }

이 코드가 이해가 가지 않는다면 아래 그림으로 설명해 보겠다

대충 여태 설명한 걸 그림으로 표현하면 이렇게 될 것이다

이제 key값의 유형에따라서 searchData의 값이 바뀔것이다.

type이면 기본적으로 0 color면 1 name면 2로

왜 이렇게 만들수 있는 그이유는

바로 배열안에 주어진 유형의 순서가 절대 변하지 않기 때문이다.

이제 for문에서 searchData(searchTpye 이였네용 죄송 ㅎㅎ ㅋㅋ ㅈㅅ!! )값으로 배열을 탐색해 값이 있으면 값을 증가 시켜주면 된다.

문제링크 폰켓몬

문제 제목부터 너무 귀여웠다 폰켓몬이라니.. 과연 문제 난이도는 어떨까 ?

이게 무슨 말이지..?

내 뇌를 누군가 꿀밤먹인거 같은 느낌이였다.

이게 비기너 수준의 문제라구..? 하며 겁을 먹어버렸다.

그래도 풀어야지 .. 해야지.. 하며 다시 마음을 다잡고 천천히 문제를 읽어내려갔다.

일단 문제를 정리해보자면

착각할수 있는 문장이 있었다 이 문제는 선택할 수 있는 경우의 수가 아니라 선택할 수 있는 '포켓몬 종류의 수'가 최대일 때를 구하는 것이다

[3,3,3,2,2,2] 이 배열이 있을경우 안에 6마리의 폰켓몬이 있으므로

총 3마리의 폰켓몬을 골라야만 합니다.. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 포켓몬 한마리 2번폰켓몬 2마리를 고르거나 혹은 2번폰켓몬 2마리와 3번폰켓몬 1마리 이렇게 고를수 있습니다

입력받은 nums 배열에 원소값들이 존재하는데

이 배열에서 최대 num의 길이 / 2 만큼 원소를 선택 가능하다.

예를 들어서 만약 배열의 길이가 6이라고하면 총 3개를 선택 할 수 있는것이다.

하지만 원소를 선택할 경우 중복되는 원소는 선택하면 안된다.

예시를 보도록 하자

처음 예를 보면 [ 3, 1, 2 ,3 ] 을 입력받았다고 생각해보자

nums = [3,1,2,3] 에서는 nums 의 길이 / 2 즉 최대 2개만 선택이 가능하다

여기서 문제 조건에 중복된 원소는 고를 필요가 없으니 nums = [1,2,3] 에서 최대 2개를 고를 수 있다 즉 정답은 2가 되는것이다.

그렇다면 다른 예시를 봐보자 [3,3,3,2,2,2] 를 입력받았다고 해보자.

이어서 nums 의 길이 / 2 는 3 이다 이때 중복된 원소는 고를 필요는 없으니 [3,2] 에서 최대 3개만 고르면 되지만 중복 원소를 제거하면 원소가 2개밖에 없다 이럴경우 nums에 있는 것들을 모두 골라주면 정답이 된다고 생각했다.

결국 이때 중요한 키워드는 중복 제거 라는 키워드인거 같아 공부를 하기 시작했다.

내가 아는 HASHSET ..

일단 중복제거 해주는 녀석으로만 알고있었다.. 사실 자세하게 공부하진 않았다

그때 당시 공부했을땐 과정이 뭐 중요한가 ? 라고 생각했지만 요즘 들어서 개발을 공부할땐 과정과 왜? 라는게 참 중요하다고 생각한다.

HASHSET 이란?

일단 자바의 hashset은 set인터페이스에서 지원하는 구현 클래스 라고한다.

순서대로 입력되지 않고 일정하게 유지되지 않는게 특징이다

또한 null 값도 허용한다 그리고 가장 중요한 특징은 중복을 허용하지 않는다는 것이다.

그렇다면 중복은 어떻게 걸러냄?

hashset은 객체를 저장하기 전에 먼저 객체의 hashcode()메소드를 호출해 해시코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한뒤 같은 해시코드가 있따면 다시 equals()메소드로 두 객체를 비교하여 true값이 나온다면 동일한 객체로 판단하고 저장하지 않는다.

문자열을 hashset에 저장할 경우 같은 문자열을 갖는 string 객체는 동일한 객체로 간주되고 다른 문자열을 갖는 string 객체는 다른 객체로 간주되는데 그 이유는 string 클래스가 hashcode()와 equals() 메소드를 재정의 하여 같은 문자열일 경우 hashCode() 의 리턴값을 같게 equlas() 의 리턴값은 true 값이 나오도록 했기 때문이다.

어떻게 사용함 ??

hashset 의 변수를 선언하는 방법이다 .

HashSet<Integer> set = new HashSet<Integer>();
HashSet<String> set = new HashSet<String>();

이렇게 HashSet<데이터타입> 변수명 = new HashSet<데이터타입>(); 으로 선언해 주면 된다

값 추가

public class HashSetTest {
    public static void main(String[] args)  {    
        // Integer
        HashSet<Integer> set = new HashSet<Integer>();    

        set.add(1);
        set.add(2);
        set.add(3);
        set.add(1);

        // String
        HashSet<String> set2 = new HashSet<String>();

        set2.add("a");
        set2.add("b");
        set2.add("c");
        set2.add("a");
    }
}

HashSet의 add(value) 메소드를 사용하여 값을 추가합니다 추가되는 값은 HashSet<데이터타입>의 맞는 데이터만 추가해줍니다

값 삭제

public class HashSetTest {
    public static void main(String[] args)  {    
        // Integer
        HashSet<Integer> set = new HashSet<Integer>();    
        set.remove(1);
        set.clear();

        // String
        HashSet<String> set2 = new HashSet<String>();
        set2.remove("a");
        set2.clear();
    }
}

HashSet의 remove(value) 메소드를 사용하면 원하는 value 값만 삭제가 된다.

크기 구하기.

public class HashSetTest {
    public static void main(String[] args)  {    
        // Integer
        HashSet<Integer> set = new HashSet<Integer>();    

        set.add(1);
        set.add(2);
        set.add(3);
        set.add(1);
        System.out.println("set의 크기 : " + set.size());

        // String
        HashSet<String> set2 = new HashSet<String>();

        set2.add("a");
        set2.add("b");
        set2.add("c");
        set2.add("a");
        System.out.println("set2의 크기 : " + set2.size());
    }
}

Size() 메소드 사용시 둘 다 결과가 3으로 출력이 됩니다

검색하기

public class HashSetTest {
    public static void main(String[] args)  {    
        // Integer
        HashSet<Integer> set = new HashSet<Integer>();    

        set.add(1);
        set.add(2);
        set.add(3);
        set.add(1);

        System.out.println("1은 있는가? : " + set.contains(1));

        // String
        HashSet<String> set2 = new HashSet<String>();

        set2.add("a");
        set2.add("b");
        set2.add("c");
        set2.add("a");

        System.out.println("a는 있는가? : " + set2.contains("a"));
    }
}

반환값으로는 boolean 값이 나온다

코드 반환값은 true로 나오게 됩니다.

사실 for문으로 만 풀고싶었다...

사실 고민하다가 HashSet으로 풀긴하였지만

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution {

    public int solution(int[] nums){
        int answer = nums.length / 2;
        HashSet<Integer> numHash = new HashSet<>();

        for (int num : nums) {
            numHash.add(num);
        }


        if(answer > numHash.size()){
            return numHash.size();
        }else {
            return answer;
        }

    }
}

for문으로만 풀고싶었다.

이유는 아직 알고리즘 초보이기도 하고 내장함수에만 의존하다보면 나중에 감도 잊을거같아서 for문으로도 풀어보았다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution {

    public int solution(int[] nums){
        int[] counts = new int[200001];
        int answer = 0;
        for(int i = 0; i < nums.length; i++) {
            if(counts[nums[i]] == 0) {
                answer++;
            }
            counts[nums[i]]++;
        }
        if(answer > nums.length / 2) {
            answer = nums.length / 2;
        }
        return answer;

    }
}

결론을 말해보자면 차근차근 읽고 이해하고 풀어보면 난이도 자체는 쉬운거 같다.

어렵지도않고 사실 이 문제는 코드를 짜는 실력보다 독해력을 요구하는 문제가 아니였을까 싶다..

앞으로는 문제가 길거나 어려워 보인다고해서 쫄지말고 차근차근 정리해나가 풀어보도록 하겠다.

사실 강의를 듣기전에 class ? 뭐임 ? 그냥 있으니깐 쓰지 뭐.. 이런 느낌으로 사용하였다 ..

그러다 보니 솔직히 어쩔때 써야할지도 모르겠고.. 왜 써야할지도 모르겠어서 많이 멘탈도 터지게되었다.

하지만 이번에 김영한 선생님의 강의가 출시되면서 이번 기회에 좀 제대로 개념을 가지고 가볼까 싶어서 강의를 들으며 정리해 보았다 .

문제: 학생 정보 출력 프로그램 만들기

당신은 두 명의 학생 정보를 출력하는 프로그램을 작성해야 한다. 각 학생은 이름, 나이, 성적을 가지고 있다.

요구 사항:
1. 첫 번째 학생의 이름은 "학생1", 나이는 15, 성적은 90입니다.
2. 두 번째 학생의 이름은 "학생2", 나이는 16, 성적은 80입니다.
3. 각 학생의 정보를 다음과 같은 형식으로 출력해야 합니다: "이름: [이름] 나이: [나이] 성적: [성적]"
4. 변수를 사용해서 학생 정보를 저장하고 변수를 사용해서 학생 정보를 출력해야 합니다.

이런 요구사항이 있다고 해보자

음 .. 첫 번째 두번째 .. 어쩌구 저쩌구 .. 딸깍 딸깍 ...

package class1;

public class ClassStart1 {
    public static void main(String[] args) {
        String student1Name = "학생1";
        int student1Age = 15;
        int student1Grade = 90;
        String student2Name = "학생2";
        int student2Age = 16;
        int student2Grade = 80;
        System.out.println("이름:" + student1Name + " 나이:" + student1Age + " 성
                적:" + student1Grade);
        System.out.println("이름:" + student2Name + " 나이:" + student2Age + " 성
                적:" + student2Grade);
    }
}

음 변수를 사용해서 만들어 보았다 ..

근데 갑자기 학생이 늘어나면 어떻게 하지 ??

오 배열을 사용해볼까 ??

딸깍 딸깍 ..

package class1;

public class ClassStart2 {
    public static void main(String[] args) {
        String[] studentNames = {"학생1", "학생2"};
        int[] studentAges = {15, 16};
        int[] studentGrades = {90, 80};
        for (int i = 0; i < studentNames.length; i++) {
            System.out.println("이름:" + studentNames[i] + " 나이:" +
                    studentAges[i] + " 성적:" + studentGrades[i]);
        }
    }
}

학생 추가 전

String[] studentNames = {"학생1", "학생2"};
int[] studentAges = {15, 16};
int[] studentGrades = {90, 80};

학생 추가 후

String[] studentNames = {"학생1", "학생2", "학생3", "학생4", "학생5"};
int[] studentAges = {15, 16, 17, 10, 16};
int[] studentGrades = {90, 80, 100, 80, 50};

그래서 뭐가 편해진거임 ..?

만약에 학생2가 도중에 큰 결심 을 하여 자퇴를 했다고 생각해보도록 하자

그 학생의 데이터를 제거하려면 각각의 배열마다 그 학생의 요소를 정확하게 찾아서 제거 해주어야 한다.

큰 결심 후

String[] studentNames = {"학생1", "학생3", "학생4", "학생5"};
int[] studentAges = {15, 17, 10, 16};
int[] studentGrades = {90, 100, 80, 50};

거기다가 한 학생의 데이터의 배열이 3개로 나누어져 있기에 배열을 각각 변경해야 한다. 그리고 한 학생의 데이터를 관리하기 위해 3개의 배열의 인덱스 순서를 항상 정확하게 맞추어야 한다...

이렇게 하면 특정 학생 (ex : 학생2 )의 데이터를 변경할 때 실수할 가능성이 매우 높다.

이 코드는 컴퓨터가 볼 때는 아무 문제가 없지만 사람이 관리하기에는 좋은 코드가 아니다.

정리

지금처럼 이름 , 나이 , 성적 을 각각 따로 나누어서 관리하는 것은 사람이 관리하기 좋은 방식이 아님.

사람이 관리하기 좋은 방식은 학생이라는 개념을 하나로 묶는것이다.

그리고 각각의 학생 별로 본인의 이름 , 나이 ,성적을 관리하는것인 것이다..!!!