지금의 기록이 미래의 자산이 된다.

A Steadily Growing Developer

[Algorithm] 프로그래밍 문제 접근법 - 빅 오 분석법

2023-03-18

devFancy

AlgorithmSkill
- 풀이 분석
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

풀이 분석
- 문제에 대한 답을 내놓고 나면 구현의 효율성에 대한 질문이 나오는 경우가 많다.
- 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교한다거나
- 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다.
- 그리고 메모리 또는 공간 사용에 관한 질문도 자주 나오는 편인데, 특히 재귀 호출을 사요할 경우 이런 질문이 많이 나온다.
- 빅 오 분석법(Big-O analysis)을 제대로 이해하고 있다면 면접관에게 좋은 인상을 남기는 데 크게 도움이 된다
- 빅 오 분석법은 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법이다.
- 알고리즘의 상대적인 효율성을 간단하게 따져보는 데는 유용하다.
빅 오 분석
- 음이 아닌 수가 저장된 배열에서 최대값을 구하는 간단한 함수를 구현하는 방법에는 최소 두 가지가 있다.
- 첫 번째 방법은 배열의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 방법이다.
- 코드로 구현하면 다음과 같다.
```
/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
int CompareToMax(int array[], int n) 
{
    int curMax, i;
    
    /* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
    if (n <= 0)
        return -1;
        
    /* 지금까지 확인한 값 중 최대값을 저장할 변수에 배열의 첫 번째 값 저장 */
    curMax = array[0];
    
    /* 모든 수를 최대값과 비교함 */
    for(i = 1; i < n; i++) {
        if(array[i] > curMax) {
            curMax = array[i];
        }
    }
    return curMax;
}
```
- 두 번째 방법은 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값이 최대값이 된다.
- 코드로 구현하면 다음과 같다.
```
/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
int CompareToAll(int array[], int n)
{
    int i, j;
    bool isMax;
    
    /* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
    if(n <= 0)
        return -1;
    
    for(i = n-1; i > 0; i--) {
        isMax = true;
        for(j = 0; j < n; j++) {
            /* 더 큰 값이 있는지 확인 */
            if(array[j] > array[i])
                isMax = false; /* array[i]가 최대값이 아님 */
        }
        /* isMax가 참이면 더 큰 값이 없는 것으로 array[i]가 최대값이다 */
        if(isMax) break;
    }
    
    return array[i];
}
```
- 이 두 함수는 모두 최대값을 제대로 반환한다.
- 그런데 어느 쪽이 더 효율적인지 알기 위해서는 빅 오 분석법을 활용하면 된다.
- 빅 오 분석법을 활용하면 서로 다른 알고리즘의 상대적인 성능을 예측하고 비교해볼 수 있다.
빅 오 분석법의 원리
- 빅 오 분석법에서는 입력 값의 크기(개수) 를 n개라고 가정한다.
- 문제에 따라 n이 연결 리스트의 노드 개수 또는 특정 자료형의 비트 수 또는 해시 테이블에 들어 있는 항목의 개수일 수 도 있는 등 다양한 값들을 입력 값의 크기 n으로 쓰일 수 있다.
- 이때 연산이라는 말은 일반적으로 입력된 값에 상수를 더하거나 새로운 입력 아이템을 만드거나 입력 값을 삭제하는 작업을 통틀어서 표현한 것이다.
- 빅 오 분석법에서는 이런 모든 연산을 동등하게 본다.
- CompareToMax와 CompareToAll에서는 모두 배열에 있는 값을 다른 값과 비교하는 작업을 연산이라고 생각할 수 있다.
CompareToMax : 배열의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 메서드
- CompareToMax에서는 각 배열 원소와 최대값을 한 번 씩 비교했으므로 총 n번의 확인 작업이 수행된다.
- 이런 상황을 O(n)이라고 표현하며 선형 시간 내에 수행된다고 말하기도 한다.
- 이 경우에는 알고리즘을 실행 시키는 데 걸리는 시간이 입력된 항목의 개수에 비례하여 선형적으로 증가한다.
- 빅 오 분석을 할 때는 n이 매우 큰 경우의 실행 시간인 점근적인 실행 시간만 따진다.
- 따라서 빅 오 분석을 할 때는 최고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 무시한다.
- 지금 다루고 있는 예에는 n이 최고차항이기 때문에 CompareToMax 함수는 O(n) 이 된다.
CompareToAll : 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값을 반환하는 메서드
- CompareToAll 메서드에서는 일단 최대 원소가 배열의 맨 뒤에 있다고 가정했다.
- 이런 경우에는 n개의 원소를 n개의 다른 원소하고 비교해야 한다.
- 따라서 nxn번 확인을 해야 하므로 이 알고리즘은 O(n^2) 알고리즘이다.
- 즉, 배열이 커짐에 따라서 CompareToAll에서의 비교 횟수가 CompareToMax의 비교 횟수보다 훨씬 커질 것임을 알 수 있다.
최선, 평균, 최악 케이스
- 여기에서 CompareToAll을 분석할 때 최대값이 맨 뒤에 있다고 가정했기 때문에 불공평한 것이라고 생각할 수 도 있다.
- 이런 문제 때문에 최선 케이스, 평균 케이스, 최악 케이스의 실행 시간을 따져봐야 하는 문제가 생긴다.
- 위의 CompareToAll을 분석할 때는 최악의 시나리오를 가정했다.
- 하지만 평균을 따져서 최대값이 가운데 있는 경우를 생각해보자.
- 최대값이 중간에 있다면 절반만 n번씩 확인하면 된다. 그러면 n(n/2)이므로 실행 시간은 O(n^2/2) 가 된다.
- 하지만 각 값을 실제로 확인하는 데 걸리는 시간은 코드에 의해 생성되는 기계어와 CPU에서 그러한 명령들을 수행하는 데 걸리는 시간에 의해 크게 좌우된다.
- 따라서 1/2이라는 숫자가 그리 큰 의미를 가진다고 볼 수 없다.
- 빅 오 분석법에서는 모든 상수 인자들을 빼 버리기 때문에 평균 케이스와 최악 케이스 모두 크게 다를 바가 없다.
- 여전히 O(n^2) 일 뿐이다.
- CompareToAll의 최선 케이스의 실행 시간은 최대값이 배열의 맨 앞에 있는 경우다.
- 이때는 최대값을 다른 모든 값들과 딱 한 번만 비교하면 되기 때문에 실행 시간은 O(n) 이 된다.
- CompareToMaax에서는 최선, 평균, 최악 케이스 모두 실행 시간이 같으므로 항상 O(n) 이다.
- 면접관에게 어떤 시나리오에 가장 중점을 둬야 할지 물어보는 것도 한 방법이다.
- 문제 자체에 이에 대한 언급이 들어 있는 경우도 있다.
빅 오 분석법을 적용하는 방법
- 일반적으로 빅 오 실행 시간 분석은 다음과 같은 방법으로 하면 된다.
1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2. 알고리즘에서 수행해야할 연산 횟수를 n의 식으로 표현한다.
3. 차수가 제일 높은 항만 남긴다.
4. 모든 상수 인수를 없앤다.
- 면접에서 다루는 알고리즘의 경우에는 입력 데이터의 크기에 의존하는 연산을 제대로 파악하면 빅 오 분석법이 그리 까다롭지는 않다.
어떤 알고리즘이 나을까?
- 가장 빠른 것은 O(1) 알고리즘으로, 보통 상수 실행 시간이라고 부른다.
- 알고리즘 성능은 대부분 입력 크기인 n에 따라 변한다.
- 성능이 가장 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열하면 다음과 같다.
  - O(log n) : 실행 시간이 입력 크기의 로그에 비례해서 늘어나는 알고리즘을 로그 알고리즘이라고 부른다.
  - O(n) : 실행 시간에 입력 크기에 비례하는 알고리즘을 선형 알고리즘이라고 부른다.
  - O(n log n) : 준선형 알고리즘이라 부르며 선형 알고리즘과 다항식 알고리즘의 중간쯤 된다.
  - O(n^2) : 입력 크기가 늘어나면 실행 시간이 빠르게 늘어나며, 다항식 알고리즘이라고 부른다.
  - O(2^n) : 다항식 알고리즘보다 실행 시간이 빠르게 늘어나며 지수 알고리즘이라고 부른다.
  - O(n!) : 가장 느린 알고리즘으로, n이 작아도 금방 거의 쓰기 힘든 수준으로 느려지며, 팩토리얼 알고리즘이라고 부른다.
- n이 커지면 실행 시간 차이가 매우 두드러진다. ndl 10일 때 각 알고리즘의 실행 시간을 따져보자.
  - log 10 = 1
  - 10 = 10
  - 10 log 10 = 10
  - 10^2 = 100
  - 2^10 = 1,024
  - 10! = 3,628,800
- 준선형 알고리즘, 또는 그보다 더 빠른 알고리즘(로그 알고리즘)을 찾으면 애플리케이션 성능을 크게 향상시킬 수 있다.
메모리 용량 분석
- 성능을 따지는 데 실행 시간 분석 말고도 중요한 게 메모리 용량이다.
- 애플리케이션의 메모리 용량 또는 알고리즘의 메모리 용량은 앞에서 설명한 빅 오 분석법을 썼던 것과 유사하게 필요한 메모리 사용량을 입력 크기 n의 식으로 표현하는 접근법을 사용해야 한다.
- 입력 크기에 따라 필요한 연산 횟수 대신 각 항목에 대해 필요한 저장 공간을 따져보면 된다.
- 면접관이 구현 방법의 메모리 사용량을 물어보는 경우는 실제 자료구조가 어떻게 구현되는지 제대로 이해하는 가를 알고자 하는 것이다.
Read All
[Algorithm] 프로그래밍 문제 접근법 - 문제 해결

2023-03-17

devFancy

AlgorithmSkill
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

절차
- 코딩 문제에서 가장 중요한 것은 지원자의 코딩 실력이 어느 정도 되는지를 가늠하는 것이다.
- 면접관은 지원자가 작성한 코드와 지원자의 대답을 바탕으로 채용 추천 여부를 결정하기 때문에 면접에서 가장 중요한 것이 바로 코딩 문제라고 할 수 있다.
시나리오
- 코딩 문제는 면접관과 일대일로 진행하는 것이 일반적이다.
- 컴퓨터 혹은 종이와 펜을 주고 코드를 작성할 수도 있다.
- 보통은 함수나 메서드를 만드는 경우가 많지만 클래스를 정의하거나 연관된 코드 모듈을 만드는 경우도 가끔 있다.
문제
- 면접관이 물어보는 문제에는 특별한 요구 조건이 주어진다.
- 비교적 짧은 시간안에 풀어야 하므로 변별력을 위해 적당히 복잡한 문제가 출제된다.
- 따라서 실전에 직접 적용할 수 있는 코드를 만드는 문제가 나올 가능성은 희박하다.
- 대신 특별한 트릭이나 언어에서 자주 쓰이지 않는 기능들을 필요로 하는 것들이 많다.
- 가장 흔히 쓰이는 방법이나 이상적인 자료구조를 못 쓰게 하는 경우도 종종있다. 예를 들어 “비교 연산자를 전혀 사용하지 않고 두 정수가 같은지 판단하는 함수를 만드시오” 와 같은 문제가 나올 수도 있다.
- 만약 그런 제약 조건이 없을 때 문제를 풀 방법을 설명한 다음에 주어진 대로 문제를 풀도록 하자.
어떤 언어를 사용할 것인가
- 일반적인 프로그래밍 또는 개발 업무에 지원한다면 자바, 파이썬, 자바스크립트, C#, C++ 같은 주류 언어를 제대로 쓸 수 있는 정도면 충분하다.
- 면접을 하러 가기 전에 자신이 사용할 언어의 사용법 및 문법을 제대로 숙지해야만 한다.
소통이 핵심이다.
- 면접관 입장에서 지원자가 만든 코드 중에 직접 본인의 눈으로 확인해볼 수 있는 코드는 면접 시에 작성한 코드뿐이다.
- 따라서 면접 시에 최고의 코드를 만들 수 있어야 한다. 자신이 사용할 언어를 가다듬고 가능하면 가장 좋은 코드를 만들자.
- 프로그래밍 문제는 코딩 실력과 문제 해결 능력을 동시에 평가할 수 있도록 만들어진다.
- 면접관이 정말로 원하는 것은 지원자가 문제를 푸는 각 단계들을 어떻게 진행하는지를 보는 것이다.
- 이런 면접에서 문제를 풀 때는 지원자와 면접관이 계속해서 의견을 주고받게 되며, 문제를 풀다가 막히면 면접관이 힌트를 제시하면서 정답을 맞출 수 있도록 도와준다.
- 지원자가 힌트를 받은 다음에 자신의 능력으로 문제를 풀어나가는 동안 보여주는 사고력과 문제 해결력 또한 매우 중요하다.
- 각 단계를 차근차근히 밝아나가면서 각 단계를 해결하는 사고 과정을 정리해서 대답해야 한다.
- 중요한 것은 어떤 프로그래밍 퍼즐의 정답을 외워서 말하는 것이 아니라 그 밑에 깔려 있는 개념을 제대로 이해하고 있다는 것을 보여주는 것이기 때문이다.
- 문제를 푸는 과정에서 자신의 프로그래밍에 대한 지식 전반을 보여주기 위해 문제와 연관된 다른 내용을 언급하고 싶은 경우가 있다.
- 그런 기회가 있으면 저 이런 지식도 갖고 있어요와 같이 논리적인 사고 능력을 갖추고 있으면서도 컴퓨터에 대한 지식도 출중하고 의사소통에도 능하다는 것을 보여줘야 한다.
- 문제를 풀 때 항상 무슨 일을 하고 있는지 계속해서 설명하는 습관을 가지자.
문제 해결
- 문제를 풀때 우선 문제를 완벽하게 이해하는 것이 중요하다.
- 몇 가지 구체적인 예를 시도해보고, 문제 해결 과정을 알고리즘으로 일반화하고 제대로 된 알고리즘이 만들었다는 확신이 설때 그 내용을 분명하게 설명하자.
- 코드 작성은 가장 마지막에 할 일이다.
기본 단계
- 면접 문제를 해결하는 가장 좋은 방법은 쳬게적인 접근법이다.
[1] 문제를 확실히 이해한다.
- 문제를 이해하지 못하면 주저하지 말고 면접관에게 문제에 대한 질문을 해야 하며, 제대로 이해하기 전에 무작정 풀기 시작하는 일은 금물이다.
- 진짜 문제가 되는 부분을 찾아내서 그런 부분을 분명히 하기 위한 제대로 된 질문을 던지는 것이 정답으로 가는 데 있어서 핵심이 될 수 있다.
[2] 일단 문제를 이해하고 나면 간단한 예를 시도해본다.
- 이렇게 예를 시도하다 보면 문제를 어떻게 풀어야 할지 감을 잡을 수도 있고, 혹시라도 잘못 이해한 부분이 있을 경우 오류를 정정할 수도 있다.
- 예를 시도하는 것은 체계적이고 논리적인 사고 능력을 보여줄 수 있는 기회가 되기도 한다.
[3] 문제 풀이에 사용할 알고리즘과 자료구조에 초점을 맞춘다.
- 이 단계에서는 면접관과의 의사소통이 중요하다.
- 계속해서 면접관에게 지금 무엇을 하는지 얘기하자. 얘기를 하다 보면 면접의 핵심이라고 할 수 있는 자신의 능력을 보여주는 데도 도움이 되고, 면접관이 힌트를 줄 수도 있다.
- (1)문제에 대해서 오랫동안 생각해서 한 번에 제대로 된 코드를 짜는 사람과 (2)무턱대고 달려들어서 코딩하면서 계속 에러만 내고 내가 지금 뭘 하고 있는지 파악도 안 되는 사람 가운데 어떤 사람과 일하고 싶은 마음이 생길지 입장 바꿔 생각해보자.
- 당연히 전자 쪽이 더 나을 것이다.
[4] 알고리즘과 구현 방법을 알아내고 나면 면접관에게 풀이를 설명한다.
- 이렇게 하면 지원자가 코딩을 시작하기 전에 면접관이 풀이에 대해 어느 정도 평가해볼 수 있다.
- 면접관이 긍정 또는 부정적인 의견을 내거나, “안 되는 건 아닌 것 같은데, 분명 더 효율적인 풀이법이 있을 것 같네요” 같은 응답도 나올 수 있다.
- 어느 쪽이든, 코딩으로 넘어갈지 알고리즘을 다시 살펴봐야 할지에 대해 아주 중요한 정보를 얻을 수 있다는 것은 분명하다.
[5] 코딩을 할 때도 뭘 하고 있는지 설명한다.
- 예를 들어, “여기에서는 배열을 전부 0으로 초기화합니다” 같은 식으로 설명을 한다면, 면접관 입장에서 코드를 더 쉽게 따라 갈 수 있다.
풀이에 대한 코드를 작성하기 전에, 그리고 코드를 작성하는 도중에도 계속해서 설명을 하자. 끊임없이 떠들자.

[6] 필요하다면 질문을 한다.
- 레퍼런스에서 찾을 수 있을 법한 내용이라면 면접관한테 질문을 해도 큰 감점 사유가 되진 않는다.
- 예를 들어, “잘 기억이 안나서 그러는데요, 지역화된 날짜 시각을 출력할 때 어떤 형식 문자열을 쓰는지 알 수 있을까요?” 같은 질문은 별로 해가 되진 않는다.
[7] 코드를 완성하고 나면 바로 몇 가지 예를 시도해보고 맞는지 확인한다.
- 자기가 만든 코드가 적어도 자기가 시도해본 예에 대해서 제대로 작동한다는 것을 분명하게 보여줄 수 있다.
- 그리고 자신의 사고 과정 및 결과를 확인하고 버그를 찾아내고자 하는 업무 자세를 보여줄 수 있는 기회도 된다.
[8] 모든 오류 및 특수 상황, 특히 경계 조건을 확인한다.
- 프로그래밍을 하다 보면 오류나 특수 상황을 무시하는 경우가 종종 있다.
- 모두 작성할 시간 여유가 없다면 적어도 말로 오류 확인이 필요하다는 설명은 해줘야 한다.
- 오류 및 특수 상황을 제대로 커버하면 면접관에게도 좋은 인상을 남길 수 있고 문제를 올바르게 푸는 데도 도움이 된다.
문제를 풀다가 막히는 경우
- 문제를 풀다가 막히는 일은 흔이 일어나는 일이며, 이것 자체도 면접의 중요한 부분이라고 할 수 있다.
- 만약 문제를 풀다가 갑자기 막히게 됐을 때 포기하거나 좌절하는 것은 최악의 대응책이다.
- 계속해서 문제에 대한 관심을 가지고 문제를 풀려고 시도하는 모습을 보이자.
예를 다시 따져본다.
- 예를 다시 확인하면서 지금 하고 있는 것을 분석해보자. 시도했던 특정 예를 일반적인 경우로 확장시켜보자.
- 면접관에게 정답을 찾아내기 위한 끈기를 보여줄 수 있는 셈이기 때문에 크게 나쁠 것은 없다.
다른 자료구조를 시도해본다.
- 연결 리스트, 배열, 해시 테이블, 이진 검색 트리 같은 다양한 자료구조를 써보자.
- 올바른 자료구조를 사용하는 것만으로 문제 풀이가 훨씬 수월해지는 일도 흔하다.
언어에서 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해보자.
- 때때로 그런 기능을 활용하는 것이 문제 풀이의 핵심이 되는 경우도 있다.
면접에서 다루는 코딩 문제의 답은 대체로 짧은 편이다.

코드가 30줄을 넘기는 경우도 드문 편이고, 50줄을 넘기는 일은 거의 없다고 봐도 된다.

코드가 너무 길어지면 엉뚱한 방향으로 가고 있을 수도 있다.

Reference

프로그래밍 면접 이렇게 준비한다
Read All
[Programmers] SQL > Join 풀이 모음

2023-03-15

devFancy

Algorithm
구분
- 코딩테스트 연습 > SUM, MAX, MIN
조건에 맞는 도서와 저자 리스트 출력하기

조건에 맞는 도서와 저자 리스트 출력하기 - 문제 링크
```
SELECT 
    BOOK.BOOK_ID,
    AUTHOR.AUTHOR_NAME,
    DATE_FORMAT(BOOK.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
FROM 
    BOOK
INNER JOIN 
    AUTHOR
ON 
    BOOK.AUTHOR_ID = AUTHOR.AUTHOR_ID
WHERE
    BOOK.CATEGORY = '경제'
ORDER BY 
    BOOK.PUBLISHED_DATE ASC;
```
그룹별 조건에 맞는 식당 목록 출력하기

그룹별 조건에 맞는 식당 목록 출력하기 - 문제 링크
Read All

[Programmers] 92341. 주차 요금 계산

2023-03-12

devFancy

Algorithm

성능 요약
구분
Answer Code1(2023.03.12)
- 문제 풀이 - Answer Code1

문제 링크

성능 요약

메모리: 73.8 MB, 시간: 0.44 ms

구분

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

Answer Code1(2023.03.12)

/*
    기본 시간 : 180분
    기본 요금 : 5000(원)
    단위 시간 : 10(분)
    단위 요금 : 600(원)
 */
/*
    fees[0] = 기본 시간(분)
    fees[1] = 기본 요금(원)
    fees[2] = 단위 시간(분)
    fees[3] = 단위 요금(원)
 */
/*
    `records`의 각 원소는 "시각 차량번호 내역" 형식의 문자열(공백으로 구분)
    시각은 `HH:MM` 형식의 길이가 5인 문자열
    차량번호는 자동차를 구분하기 위한, `0` ~ `9`로 구성된 길이 4인 문자열
    내역은 `IN` 또는 `OUT`의 길이가 2 또는 3인 문자열
    `records`의 원소들은 시각을 기준으로 오름차순으로 정렬됨
    `records`는 하루 동안의 입/출차된 기록만 담고 있음. 
    마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않음.
 */

import java.util.*;

class Solution {
  public int[] solution(int[] fees, String[] records) {

    int std_time = fees[0];
    int std_pay = fees[1];
    int per_time = fees[2];
    int per_pay = fees[3];

    //key: 차량번호, value: 입장 시간
    Map<Integer, Integer> map = new HashMap<>();
    //key: 차량번호, value: 주차 요금
    Map<Integer, Integer> result = new TreeMap<>();
    // 주차기록 처리하기
    for (String data : records) {
      String[] temp = data.split(" ");
      int time = cal_time(temp[0]);
      int car_num = Integer.parseInt(temp[1]);
      String state = temp[2];
      if (state.equals("OUT")) {
        int start = map.get(car_num);
        int use_time = time - start;
        if (result.containsKey(car_num)) {
          int a = result.get(car_num);
          use_time += a;
        }
        result.put(car_num, use_time);
        map.remove(car_num);
        continue;
      }
      map.put(car_num, time);
    }

    // 아직 안나간 차량 처리
    for (int num : map.keySet()) {
      Integer d = map.get(num);
      d = d == null ? 0 : d;

      int start = d.intValue();
      int use_time = 1439 - start;

      Integer e = result.get(num);
      e = e == null ? 0 : e;

      int total = e.intValue();

      result.put(num, total + use_time);
    }

    // 출력하기
    int[] answer = new int[result.size()];
    int i = 0;
    for (int data : result.keySet()) {
      int time = result.get(data);

      if (time <= std_time) {
        time = std_pay;
      } else {
        time = std_pay + (int) Math.ceil((double) (time - std_time) / per_time) * per_pay;
      }
      answer[i] = time;
      i++;
    }

    return answer;
  }

  public int cal_time(String time) {
    String[] temp = time.split(":");
    int hour = Integer.parseInt(temp[0]) * 60;
    int min = Integer.parseInt(temp[1]);
    return hour + min;
  }
}

문제 풀이 - Answer Code1

문제 풀이에 도움을 주신 류창님께 감사의 말씀 전합니다.

출력 결과 : 차량 번호가 적은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 한다.

목표 : 차량 기록을 모두 처리한 이후에 각 차량마다 주차요금을 구하는 문제 (차량 번호를 기준으로 오름차순한다)

[1] 기본 시간, 기본 요금, 단위 시간, 단위 요금을 보기 쉽게 분리하였다.
- 그런 다음, 2개의 Map을 준비했다.
- 차량 번호를 오름차순으로 정렬해야하기 때문에 TreeMap으로 설정했다.

Read All

[Programmers] 138476. 귤 고르기

2023-03-08

devFancy

Algorithm

성능 요약
구분
Answer Code1(2023.03.08)
문제 풀이 - Answer Code1
Reference

문제 링크

성능 요약

메모리: 98.7 MB, 시간: 46.69 ms

구분

코딩테스트 연습 > 구현

Answer Code1(2023.03.08)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Collections;

class Solution {
    
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        
        // 크기별로 몇 개 있는지 map에 저장함
        for (int tan : tangerine) {
            map.put(tan, map.getOrDefault(tan, 0)+1);
        }

        // 개수(value)가 많은 순으로 정렬
        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list, Collections.reverseOrder());

        // 개수가 많은 순부터 사용
        for (Integer a : list) {
            if(k < 1) 
                return answer;
            k -= a;
            answer++;
        }

        return answer;
    }
}

문제 풀이 - Answer Code1

귤의 크기(key)와 개수(value)를 Map에 저정한 다음, 개수가 많은 순부터 사용하여 k개를 채우면 되는 문제였다.
HashMap()의 getOrDefault(key, defaultValue)는 지정된 key의 값(객체)을 반환한다. key가 없으면 지정된 defaultValue로 지정된 객체를 반환한다.

Reference

귤 고르기 - 풀이

Read All

23/57

지금의 기록이 미래의 자산이 된다.

[Algorithm] 프로그래밍 문제 접근법 - 빅 오 분석법

풀이 분석

빅 오 분석

빅 오 분석법의 원리

최선, 평균, 최악 케이스

빅 오 분석법을 적용하는 방법

어떤 알고리즘이 나을까?

메모리 용량 분석

[Algorithm] 프로그래밍 문제 접근법 - 문제 해결

절차

시나리오

문제

어떤 언어를 사용할 것인가

소통이 핵심이다.

문제 해결

기본 단계

문제를 풀다가 막히는 경우

Reference

[Programmers] SQL > Join 풀이 모음

구분

조건에 맞는 도서와 저자 리스트 출력하기

그룹별 조건에 맞는 식당 목록 출력하기

[Programmers] 92341. 주차 요금 계산

성능 요약

구분

Answer Code1(2023.03.12)

문제 풀이 - Answer Code1

[Programmers] 138476. 귤 고르기

성능 요약

구분

Answer Code1(2023.03.08)

문제 풀이 - Answer Code1

Reference