씅의 기록하는 개발노트

문제출처

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;
    }
}

문제출처

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

문제풀이

Java에서 사용자 정의로 정렬을 진행할때 Comparator를 사용한다. 이 문제는 Comparator를 사용할 줄 아는지 묻는 문제이다. 파일명을 head, number, tail로 분리한뒤 정렬을 다음 순서에 맞게 진행하면 된다.

head를 기준으로 문자열 오름차순으로 먼저 정렬한다. 이 때 대소문자 구분을 하지 않기 때문에 본인은 소문자로 통일한뒤 진행했다. head가 같은경우 number로 정렬하고 number도 같다면 기존 files의 순서를 지키면 된다.

풀이 자체가 Comparator 인터페이스를 구현하고 있다. 정렬을 할때 Comparator와 Comparable을 사용하곤 하는데 자세한 내용은 https://swjeong.tistory.com/198?category=778818 이 글을 참조하면 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%ED%8C%8C%EC%9D%BC%EB%AA%85%20%EC%A0%95%EB%A0%AC.java

import java.util.*;
class Solution {
    public String[] solution(String[] files) {
        
        Arrays.sort(files, new Comparator<String>() {
           public int compare(String s1, String s2) {
               String head1 = s1.split("[0-9]")[0];
               String head2 = s2.split("[0-9]")[0];
               s1 = s1.replace(head1, "");
               s2 = s2.replace(head2, "");
               
               head1 = head1.toLowerCase();
               head2 = head2.toLowerCase();
               
               // compareTo(x, y) => [ -1 : x < y | 0 : x == y | 1 : x > y ]
               int headCompareValue = head1.compareTo(head2);
               if (headCompareValue == 0) {
                   
                  // head정렬 값이 같으므로 number로 정렬
                  String num1 = "";
                  for (char c : s1.toCharArray()) {
                      if (!(c >= '0' && c <= '9')) break;
                      num1 += c;
                  }
                  String num2 = "";
                  for (char c : s2.toCharArray()) {
                     if (!(c >= '0' && c <= '9')) break;
                     num2 += c;
                  }
                  return (Integer.parseInt(num1) - Integer.parseInt(num2));
               } else {
                   return headCompareValue;
               }
           }
        });
        
        return files;
    }
}

Comparable, Comparator 모두 자바에서 정렬을 할 때 사용하고 있습니다. 하지만 이 2가지는 명확한 차이가 존재합니다.

2가지 모두 정렬할 때 비교해 객체의 순서를 결정하는 역할을 합니다. 이 2가지 인터페이스를 사용하면 Collections.binary.Search, Collections.binarySearch, Collections.max, Collections.min, Collections.sort, Arrays.binarySearch, Arrays.sort같은 순서를 결정하는 메소드를 사용할 수 있습니다.

결론적으로 Comparable과 Comparator의 차이는 다음과 같습니다.

* Comparable - 기준을 설정하고 정렬. 즉, 특정한 기준 1가지를 가지고 정렬 Ex) 학점을 기준으로 오름차순 or 내림차순

* Comparator - Comparable과 다르게 요구사항에서 주어진 특정 기준을 가지고 정렬 Ex) 학점이 같다면 이름순으로 정렬

그럼 Comparable과 Comparator의 2가지 차이점을 알아보겠습니다.

- Comparable

Comparable은 compareTo 메서드를 오버라이드 합니다. 

Comparable을 구현한 클래스는 기본적으로 오름차순을 기준으로 정렬을 수행합니다. 또한 1가지 기준점을 가지고 그에 대해 정렬을 하고 싶을 때 사용합니다.

- Comparator

Comparator는 compare 메서드를 오버라이드 합니다.

Comparator를 구현한 클래스는 일반적인 정렬기준을 넘어 사용자 정의 조건을 규칙으로 정렬을 하고 싶을 때 사용합니다.

정리하면 Comparable은 기본적인 정렬위주일 때 사용하고 특정한 규칙을 사용해 정렬을 하고 싶을 때는 Comparator를 사용하면 됩니다.

문제출처

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

문제풀이

문제에서 주어진 조건대로 문자열 처리를 하고 구현하면 되는 문제다. 여기서 핵심은 #이 붙은 문자 처리 방법이라고 생각한다. 본인은 #이붙은 문자를 convertSound(String m) 메서드를 통해 소문자로 치환한뒤 구현했다. 또한 나중에 악보를 생성할때를 생각해서 곡의 재생시간을 구할때 단위를 분으로 통일했다.

이 문제는 오해의 소지가 있다고 생각한다. 지문에서 `(None)`을 리턴한다고 했는데 실제로는 `(None)`이 아니라 (None)을 리턴해줘야 하기 때문이다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B0%A9%EA%B8%88%EA%B7%B8%EA%B3%A1.java

class Solution {

    // #이 붙은 음을 소문자로 치환
    private String convertSound(String m) {
        m = m.replaceAll("C#", "c");
        m = m.replaceAll("D#", "d");
        m = m.replaceAll("F#", "f");
        m = m.replaceAll("G#", "g");
        m = m.replaceAll("A#", "a");
        
        return m;
    }
    
    // 곡의 재생시간을 분으로 환산
    private int getRunningTime(String startInfo, String endInfo) {
        int runningTime = 0;
        int startHour = Integer.parseInt(startInfo.split(":")[0]);
        int startMinute = Integer.parseInt(startInfo.split(":")[1]);
        int endHour = Integer.parseInt(endInfo.split(":")[0]);
        int endMinute = Integer.parseInt(endInfo.split(":")[1]);
        
        return (endHour - startHour) * 60 + (endMinute - startMinute);
    }
    
    // 재생 시간만큼 재생해 악보를 만듬
    private String playMusic(String sound, int runningTime) {
        StringBuilder sb = new StringBuilder();
        int soundLength = sound.length();
        for (int i=0; i<runningTime; i++) {
            sb.append(sound.charAt(i % soundLength));
        }
        return sb.toString();
    }
    
    public String solution(String m, String[] musicinfos) {
        String answer = "(None)";
        m = convertSound(m);
        
        int maxRunningTime = 0;
        for (String info : musicinfos) {
            String[] musicInfo = info.split(",");
            int runningTime = getRunningTime(musicInfo[0], musicInfo[1]);
            String musicName = musicInfo[2];
            String sound = convertSound(musicInfo[3]);
            
            // 곡 정보를 재생해서 만든 악보
            String music = playMusic(sound, runningTime);
            
            // 정보를 통해 만든 악보가 기억한 악보와 다르다면 제외
            if (!music.contains(m)) continue;
            
            // 악보가 같은경우 재생시간이 긴 제목을 반환
            if (runningTime > maxRunningTime) {
                answer = musicName;
                maxRunningTime = runningTime;
            }
        }
        return answer;
    }
}

문제출처

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

문제풀이

재귀 함수를 이용해 숫자의 합을 구한뒤 소수 판별을 해주면 되는 간단한 문제

소스코드

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%86%8C%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

#include <vector>
#include <cmath>
using namespace std;
int ans = 0;
bool checkPrime(int number) {
    if (number == 1) return false;
    if (number == 2) return true;
    for (int i=2; i<=sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
void go(vector<int> nums, int startIdx, int depth, int sum) {
    if (depth == 3) {
        if (checkPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i=startIdx; i<nums.size(); i++) {
        go(nums, i+1, depth+1, sum+nums[i]);
    }
}
int solution(vector<int> nums) {
    go(nums, 0, 0, 0);
    
    return ans;
}

문제 출처

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

문제 풀이

dfs로 풀이했는데 전체 탐색을 중간에 멈추는 방법을 생각하지 못했다. 그래서 탐색할 수 있는 전체 경로가 출력되서 자꾸 테스트 케이스도 통과 못하는 경우가 발생했다.
생각한 해결책은 2차원 벡터를 만들어 기저조건일 때 2차원 벡터에 경로를 넣어주는 것이다. 이후 전체 탐색이 완료되면 정렬한뒤 가장 앞에 있는 경로를 return하면 된다.
dfs탐색은 보통 알고 있는 방법대로 진행했는데 탈출 조건이나 정답을 return하는게 더 어려웠던 문제.

소스 코드

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%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> visit;
vector<string> path;
vector<vector<string>> answer;
void getTravelPath(vector<vector<string>> &tickets, string from, int depth) {
	if (tickets.size() == depth) {
		answer.push_back(path);
		return;
	}

	for (int i=0; i<tickets.size(); i++) {
		if (visit[i] || from != tickets[i][0]) continue;
		visit[i] = 1;
		path.push_back(tickets[i][1]);
		getTravelPath(tickets, tickets[i][1], depth+1);
		path.pop_back();
		visit[i] = 0;
	}
}
vector<string> solution(vector<vector<string>> tickets) {
    visit.resize(tickets.size(), 0);
    path.push_back("ICN");
    getTravelPath(tickets, "ICN", 0);
    sort(answer.begin(), answer.end());
    return answer.front();
}

문제출처

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

문제풀이

규칙을 찾아내면 쉬운 문제. 규칙을 처음에 찾으려고 직접 종이를 접어가면서 풀이했다. 직접 종이를 접어가며 나오는 출력값을 적어가는 도중 0을 대칭으로 어떤 연산이 일어나는 걸 알아차렸다. 

즉 n이 3인경우 0 0 1 -> 0 0 1 0 0 1 1 으로 바뀌는데 0 0 1 뒤에 0을 붙이고 n이 2일때의 값을 뒤집어서 1이면 0, 0이면 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%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0.cpp

#include <string>
#include <vector>

using namespace std;
/*
* 규칙 
* n = 1 -> 0
* n = 2 -> 0 0 1
* n = 3 -> 0 0 1 0 0 1 1
* n = 4 -> 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1
* n = 2 -> 3이 될때 0 0 1과 0 1 1 을 보면 기존 0은 1로 1은 0으로 바뀌고 가운데 0이 끼는 것을 알 수 있음
* n = 3 -> 4가 될때도 기존 3인 값에 0이 추가 되고 역순으로 0은 1로 1은 0으로 바뀜
*/
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0);
    if (n == 1) return answer;
    for (int i=2; i<=n; i++) {
        vector<int> temp = answer;
        answer.push_back(0);
        for (int j=temp.size()-1; j>=0; j--) {
            if (temp[j] == 0) answer.push_back(1);
            else if (temp[j] == 1) answer.push_back(0);
        }
    }
    
    return answer;
}

문제 출처

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

문제 풀이

정렬한뒤 풀이하는게 핵심이다. A, B벡터 모두 가장 큰수부터 비교를 해 B가 더 크다면 승점 확보와 index를 감소시킨다.

A의 가장 큰수 vs B의 가장 큰수가 붙었을때 A가 더 크다면 B에서 이길 수 있는 수가 없으므로 A의 index를 하나 감소시켜 재 비교해주면 된다.

소스 코드

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%88%AB%EC%9E%90%20%EA%B2%8C%EC%9E%84.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIdx = A.size()-1;
    int bIdx = B.size()-1;
    while (1) {
        if (aIdx < 0) break;
        if (A[aIdx] < B[bIdx]) {
            bIdx--;
            answer++;
        }
        aIdx--;
    }
    
    return answer;
}

문제 출처

programmers.co.kr/learn/courses/30/lessons/60059

문제 풀이

전체탐색과 2차원 배열을 다룰 수 있는지 묻는 문제 입니다.

자물쇠에 키를 대조할때 겹치면 안되나 키가 자물쇠의 범위를 벗어나도 된다는 것이 핵심입니다. 
즉 키의 (0,0) 부분이 map의 (0,0) ~ (n+m-1, n+m-1)까지 이동하며 탐색하면 됩니다.

아래 그림은 자물쇠와 키의 예시입니다.

map을 확장한뒤 map[n+2m-2][n+2m-2]의 정 중앙에 자물쇠를 두어 겹치게 한다면 전체탐색이 가능합니다.

즉 탐색을 좌측상단 열쇠위치에서 시작하고 마지막 탐색은 우측하단 열쇠 위치까지 진행하여 열쇠와 자물쇠가 적합한지 판단하는 문제입니다.

탐색한 뒤 키와 자물쇠가 중복되지 않은 것을 판별하기 위해 map에서 자물쇠 위치를 탐색할때 배열에 있는 값이 1이 아니면 false를 return합니다.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp

#include <string>
#include <vector>
using namespace std;

void rotateKey(vector<vector<int>> &key) {
    int keySize = key.size();
    vector<vector<int>> temp = key;
    for (int y=0; y<keySize; y++) {
        for (int x=0; x<keySize; x++) {
            key[y][x] = temp[keySize-x-1][y];
        }
    }
}

bool isUnlock(int sy, int sx, vector<vector<int>> key, vector<vector<int>> map) {
    int keySize = key.size();
    int mapSize = map.size();
    
    for (int y=sy; y<sy+keySize; y++) {
        for (int x=sx; x<sx+keySize; x++) {
            map[y][x] += key[y-sy][x-sx];
        }
    }

    for (int y=keySize-1; y<mapSize-keySize+1; y++) {
        for (int x=keySize-1; x<mapSize-keySize+1; x++) {
            if (map[y][x] == 1) continue;
            return false;
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keySize = key.size();  
    int lockSize = lock.size(); 
    int mapSize = lockSize + (keySize-1)*2; 

    // 작업할 map생성
    vector<vector<int>> map(mapSize, vector<int>(mapSize, 0));
    for (int y=0; y<lockSize; y++) {
        for (int x=0; x<lockSize; x++) {
            map[y+keySize-1][x+keySize-1] = lock[y][x];
        }
    }
    
    // 90도씩 4번 회전
    for (int i=0; i<4; i++) {
        // key를 전체 map에 대해 탐색
        for (int y=0; y<mapSize-keySize+1; y++) {
            for (int x=0; x<mapSize-keySize+1; x++) {
                if (isUnlock(y, x, key, map)) {
                    return true;
                }
            }
        }
        rotateKey(key);
    }
    
    return false;
}