씅의 기록하는 개발노트

문제출처

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

문제풀이

이 문제도 역시 중복을 검사하는 문제다. 중복을 검사하길래 바로 set자료구조를 떠올려서 풀었다. 사실 set 자료구조보다 사람순서와 언제 틀렸는지 구하는 규칙을 찾아내는게 주요 목적이다. 중복검사는 set이 아니여도 충분히 가능하기 때문이다.

전에 말했던 마지막글자와 첫글자가 다르거나 중복된경우 순서를 저장하고 retrun하면 되기 때문에 같은 if문에 묶어 처리했다.

같은 level2문제여도 카카오 level2가 더 어렵게 느껴진다 ㅠ 생각할 것도 많고... 이 문제는 level1정도로 생각된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%98%81%EC%96%B4%20%EB%81%9D%EB%A7%90%EC%9E%87%EA%B8%B0.java

import java.util.*;
class Solution {
    // n명 
    // i % n 값에 +1 한게 사람순서
    // i / n 값에 +1 한게 차례
    // 끝글자랑 다음의 처음글자 확인
    public int[] solution(int n, String[] words) {
        int[] answer = {0, 0};
        Set<String> historySet = new HashSet<>();
        historySet.add(words[0]);
        char prevCharacter = words[0].charAt(words[0].length() - 1);
        
        for (int i=1; i<words.length; i++) {
            historySet.add(words[i]);
            if (!words[i].startsWith(Character.toString(prevCharacter)) || historySet.size() != i+1) {
                answer[0] = (i%n)+1;
                answer[1] = (i/n)+1;
                break;
            }
            prevCharacter = words[i].charAt(words[i].length() - 1);
        }
        return answer;
    }
}

문제출처

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

문제풀이

이런 문제는 계속 예제를 만들고 시뮬레이션을 돌리며 규칙을 찾아야 하는거 같다. 시간도 많이 잡아먹고 어렵게 느껴진다 ㅠ

문제에서 주어진대로 위치 0에서 n까지 가는 구조로 하다보니 규칙을 찾기 어려웠다. 그래서 n에서 0으로 가는 구조로 다시 생각해봤다. 문제를 풀때 핵심 키워드로 작용한 내용은 순간이동에 대한 조건이다. (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동

즉, 순간이동을 하면 짝수가 된다는 점에서 짝수와 홀수간 규칙이 있지 않을까 의심해봤다. 짝수인 경우 순간이동을 하고 홀수인 경우 1칸만 점프하면 배터리 사용량을 최소화 할 수 있다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A0%90%ED%94%84%EC%99%80%20%EC%88%9C%EA%B0%84%EC%9D%B4%EB%8F%99.java

import java.util.*;
/**
* k칸 앞으로 점프 || 현재까지 온거리 * 2
* k칸 점프시 건전지 사용
* n만큼 떨어져 있는 곳으로 이동할 때 건전지 사용량을 최소로하는 값 return
* top - down 방식으로 풀이
*/
public class Solution {
    public int solution(int n) {
        int ans=0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                ans++;
                n -= 1;
            }
        }
        return ans;
    }
}

문제를 다 풀고 다른사람 풀이를 찾아보는 중에 생각지도 못한 방법이 있었다. 비트를 사용하는 방법인데 자세한 설명은 아래 블로그를 참조하면 된다.

public int solution(int n) {
	return Integer.bitCount(n);
}

출처 : https://taesan94.tistory.com/142

문제출처

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

문제풀이

단순하게 구현을 할 수도 있지만 Set자료구조를 사용하면 더 빠르고 쉽게 풀수 있는 문제다. nums배열의 크기가 n인경우 선택할 수 있는 폰켓몬의 수는 n/2마리인데 n/2마리를 선택할 때 폰켓몬의 종류를 출력하는 문제다.

폰켓몬의 종류의 수만 알면 되기 때문에 몇번째 폰켓몬이 선택되었는지는 중요하지 않다. 즉 중복되지 않은 자료만 유효하다. 그래서 Set자료구조를 생각하게 되었다.

선택한 폰켓몬의 최대값은 n/2이고 최소값은 1이다. 즉, Set에 모든 폰켓몬의 자료를 넣어 중복을 없앤뒤 Set의 크기가 n/2보다 크면 n/2를 아니면 Set의 크기를 반환해주면 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%ED%8F%B0%EC%BC%93%EB%AA%AC.java

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> phoneketmonSet = new HashSet<>();
        int pickSize = nums.length / 2;
        for (int num : nums) {
            phoneketmonSet.add(num);
        }
        
        return pickSize > phoneketmonSet.size() 
                    ? phoneketmonSet.size() : pickSize;
    }
}