뚝딱뚝딱

스택 알고리즘에서 자주 다루는 () 괄호 문제.

전공 책만 봐도 기본으로 나오는 예제인 것 같다.

그래서 막힘없이 술술 풀릴정도라, 왜 LV2인지는 모르겠으나.. 안 접해본 사람이라면 고민은 해볼 수 있을정도!

본론으로 들어가자면..

스택 (Stack)

• 후입선출(LIFO) 방식의 자료구조.
• 즉, 나중에 들어간 것이 가장 먼저 나오는 구조이다.

이 스택을 어떻게 괄호 문제에 활용할 수 있을까?

괄호가 열리면, 반드시 짝이되는 닫는 괄호가 있어야 한다.

괄호가 열릴 때마다 저장해 두었다가 닫는 괄호를 만나면 하나씩 삭제해 나가면 된다.

만약 열린 괄호의 내역이 없는데, 닫힌 괄호를 만난다면 ? 열린괄호가 없었으므로 닫힌 괄호는 올수없고 이는 규칙을 위반한 사례이므로 false를 반환한다.

그럼 열린 괄호를 어떻게 저장할 수 있을까?

바로 스택을 활용한다.

문자열 타입의 빈 스택을 생성해두고, 인자로 받은 (,)로만 이루어진 문자열 s의 첫번째 문자부터 순회한다.

문자가 열린괄호 ( 이면 스택에 넣어둔다. 그리고 ) 괄호이면, 짝을 하나 찾은 것이므로 스택에서 가장 마지막에 들어간 ( 을 빼주면 된다 = pop으로 가장 마지막 요소가 삭제된다.

그런데 여기서 주의할 점은, 스택이 만약 비어있었다면, 이전에 열린괄호 (가 없었다는 뜻이기 때문에, 규칙을 위반한 것이다. 따라서 이런 경우에는 바로 false를 리턴하도록 한다.

s 문자열을 다 순회하였는데, 스택이 비어있지 않다면?

스택이 비어있지 않다는 건, 이전에 들어왔던 열린 괄호 개수만큼  짝이 될 닫힌 괄호가 없었다는 뜻과 같기 때문에, 이 경우에도 false를 리턴해야 한다.

따라서 결과가 true가 되려면, string 순회 후에 스택이 비어있어야 함을 알 수 있다.

위를 바탕으로 코드를 짜면 아래와 같다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack<String> st = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                st.push("(");
            }else{
                if(st.isEmpty()){
                    return false;
                }else{
                    st.pop();
                }
            }
        }
     
        if(!st.isEmpty()) answer = false;
        
        return answer;
    }
}

<자바 문법>

** Stack을 사용하려면 java.util.Stack을 import 해야함.

** 문자열의 특정 위치의 문자에 접근하려면, s.charAt(인덱스) 를 사용하여 접근해야함.

** 문자의 경우 ' ', 문자열의 경우 " " 임을 명심하자. 

해결한 방식을 사용하기 전 생각 했던 접근 방식은 다음과 같았다.

1. 맨 앞 수만 가지고 정렬 한다음, 가장 큰 수를 포함하는 숫자를 answer에 저장한다
-> 이렇게 할 경우 가장 큰수에 해당하는 숫자들에 대해서는 언제까지 비교할 것인가? 이게 문제

2. 숫자를 앞 글자부터 버킷에 넣어가는 식으로 비교한다.

-> 그 개수를 모르기 때문에 언제까지 비교? 어디에 넣을것인가? 마땅히 생각나는 자료구조가 없어서 실패

여러가지로 짱구를 돌려봤지만, 모두 복잡한 풀이가 이어질 것으로 예상되어서(2시간 붙잡음..) 힌트를 확인했다.

사실 문제에서는 힌트를 줬다.

"문자열로 출력하세요."

우리가 숫자 그 자체로 두고 비교를 하려니 해결되지 않았던 것이다.

지난 포스팅에서도, 문자 형태의 숫자를 sort하면 숫자 자체가 아닌, 숫자 자체가 사전식으로 큰지를 판단해서 정렬함을 배웠다.(이래서 복습이 중요하다!!!!!!)

1. 그러므로 먼저 배열을 string형태로 변환하는 과정이 필요하다.
2. 하지만 여기서 끝이 아니다. string의 정렬에서는 30,3 과 같은 경우 더 긴 쪽을 크다고 판단한다.
   이런 경우를 대비해서 sort함수의 정렬 기준을 바꾸어 주어야 한다.
   두 문자열을 받았을 때 문자열을 303으로 붙였을 때와 330으로 붙였을 때 어느 쪽이 더 큰가? 
   후자가 더 크다.
   따라서 그렇게 정렬해주면 자동으로 숫자가 큰쪽으로 정렬이 된다.
   이를 위해서 Arrays.sort함수 인자안에서 람다식을 이용해 기준을 설정해 주었다.
3. Arrays.sort(nums, (o1, o2)->(o2+o1).compareTo(o1+o2));
   두번째 인자가 람다식을 통해 기준을 설정해준 것인데, 인자로 받은 string o1, o2에 대해서 o2+o1 순으로 더했을 때의 값과 o1+o2순으로 더했을 때의 값을 비교한 결과가 양수이면 정렬을 결과가 큰 쪽으로 하겠다는 의미이다.
4. 위의 간단한 람다식을 통해 정렬을 했으면, 이제 정렬 결과에 대해 예외를 생각해야 한다.
   만약 숫자 배열에 0밖에 없었다면?
   당연히 결과는 0이어야 한다. 000....은 0이기 때문이다.
   따라서 이런경우에는 "0"을 바로 return 하도록 하였다.
5. 0이 아닌 경우에는 nums에 정렬된 대로 순서대로 string을 붙여서 출력하면 되는데, 이때 string에 + 형식 말고, StringBuilder 클래스를 사용하여 붙였다.
   answer라는 이름으로 해당 객체를 생성해 준 다음에 nums에 있는 값들을 차근차근 append하여 넣어준뒤, 마지막에 return할 때는 answer.toString()으로 반환해주었다.

💡 StringBuilder?

• Java에서 문자열을 효율적으로 생성 및 조작하기 위한 클래스이다.
• + 연산자를 이용해서 반복적으로 연산하는 것보다 append()함수를 통해 문자열을 연결하는 것이 성능을 높일 수 있다.
• 문자열을 연결하거나 수정하는 작업을 수행할 때 많은 문자열 객체가 생성되는 것을 방지하기 때문에, 성능이 향상되고 메모리 사용량을 줄일 수 있다.
• StringBuilder 클래스는 문자열을 연결하고 수정하는 역할을 하는 것이기 때문에, 연결 작업을 끝낸 후 문자열을 반환하려면 클래스 이름 자체가 아니라, 반환 함수인 toString()함수를 이용해서 반환해야 한다.

최종 코드는 다음과 같다.

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        
        String[] nums = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            nums[i] = Integer.toString(numbers[i]);
        }
        
        Arrays.sort(nums, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if(nums[0].equals("0")) return "0";
        
        StringBuilder answer = new StringBuilder();
        
        for(int i=0; i<nums.length; i++){
                answer.append(nums[i]);
        }
    
        
        //문자로 표현된 숫자의 경우.. 숫자가 더 크냐가 아니라, 사전식으로 어떤게 더 앞에 있냐를 따지니까.. 문자로 바꿔서 정렬하면 바로 해결됨.
        
        
        return answer.toString();
    }
}

<자바 문법>

**sort함수는 java.util.Arrays에 있다.

**문자열 비교는 .equals("")로 한다.

**int->string으로 변환하는 함수는 Integer.toString(변수)

💡 문제)
USED_GOODS_BOARD와 USED_GOODS_USER 테이블에서 완료된 중고 거래의 총금액이 70만 원 이상인 사람의 회원 ID, 닉네임, 총거래금액을 조회하는 SQL문을 작성해주세요. 결과는 총거래금액을 기준으로 오름차순 정렬해주세요.

1. 회원 ID, 닉네임, 총거래금액을 조회
   SELECT B.USER_ID, B.NICKNAME, SUM(A.PRICE) AS TOTAL_SALES
   문제에서 주어진 쿼리 결과대로 총거래금액의 출력 시 이름을 TOTAL_SALES로 바꾸어준다.
   
   
2. USED_GOODS_BOARD와 USED_GOODS_USER 테이블에서
   테이블 두개가 연결되어야 함을 알 수 있다. 테이블을 보면 USER_ID에 대해서 중복된 것을 알 수 있다 (컬럼이름은 각 테이블에서 다르지만, 결국은 USER의 아이디를 가리키고 있음)
   따라서 두 테이블을 유저 아이디에 대한 조건으로 INNER JOIN시켜야 한다.
   그래야 각 상품 목록에 대해서 유저의 정보를 함께 출력하는 테이블을 얻을 수 있기 때문이다.
   FROM USED_GOODS_BOARD A JOIN USED_GOODS_USER B ON A.WRITER_ID=B.USER_ID
   
   
3. 완료된 중고 거래의
   위의 2번까지를 통해 각 상품에 대한 유저 정보까지 합친 테이블을 얻었으니, 이제 그 중에서도 완료된 거래에 대해서만 추려야 한다.
   그러러면 WHERE 절을 이용해서 STATUS가 DONE인 것만을 가져올 수 있다.
   WHERE A.STATUS="DONE"
   
   
4. 총금액이 70만 원 이상인 사람의
   위의 과정까지는 각 상품에 대해서 개별적으로 조회되기 때문에, 한 사람의 전체 거래 내역을 고려하기 위해서는 사람의 단위로 GROUP을 지어야 한다.
   따라서 GROUP BY 절을 통해 USER_ID 별로 그룹화 시킨다.
   그러면 거래가 완료된 상품의 거래 주인의 아이디, 이름, 총거래금액이 출력되는데, 이 중에서도 조건에서 총거래금액이 70만원 이상인 사람의 것만 출력하라고 되어 있다.
   그러므로 GROUP BY 절에 HAVING을 추가해서 그 그룹 중 총거래금액이 70만원이상인 것만 출력하도록 해준다.
   GROUP BY B.USER_ID HAVING TOTAL_SALES>=700000
   
   
5. 결과는 총거래금액을 기준으로 오름차순 정렬해주세요.
   (나는 이 단계를 빼먹고 채점 결과가 자꾸 틀렸다고 떠서 시간을 낭비했다. 꼭 정렬 조건을 확인하도록 하자)
   이제 조건에 만족하는 결과는 다 출력했다.
   마지막 조건인 정렬을 해준다.
   ORDER BY절을 통해 해줄 수 있다.
   ORDER BY TOTAL_SALES;

위 다섯 단계를 거치면서 하나하나씩 접근하면 매우 쉬운 문제이다!

조인, WHERE절, GROUP BY절, ORDER BY절이 다 쓰인 문제라서, 순서를 한번 정리하고 넘어가자

SELECT > FROM > JOIN-ON > WHERE > GROUP BY - HAVING > ORDER BY

FOOD_PRODUCT 테이블에서 가격이 제일 비싼 식품의 식품 ID, 식품 이름, 식품 코드, 식품분류, 식품 가격을 조회하는 SQL문을 작성해주세요.

WHERE문 안에서는 PRICE=MAX(PRICE) 이런식으로 접근할 수 없다. 따라서 MAX(PRICE)의 값을 가져오려면 서브쿼리를 이용해서 MAX(PRICE) 값을 가져올 수 있도록 해야한다.

SELECT MAX(PRICE) FROM FOOD_PRODUCT를 서브쿼리로 해서 MAX(PRICE)값을 가져오고 그 값이 PRICE와 같으면 해당 정보를 조회하도록 한다.

최종 코드는 아래와 같다.

SELECT * FROM FOOD_PRODUCT WHERE PRICE = (SELECT MAX(PRICE) FROM FOOD_PRODUCT);

= 대신에 IN을 써도 무방하다.

**

다른 사람들의 풀이를 보다가 PRICE에 대해 내림차순 정렬 후 LIMIT 1 을 사용해서 조회한 풀이를 발견하였다.

그런데, 내 생각에는, LIMIT 1을 할 시 , 동일하게 MAX PRICE를 갖는 레코드에 대해서는 하나의 레코드만 출력되는 예외가 발생할 수 있기 때문에, 서브쿼리를 이용한 풀이가 더 맞다고 본다. 

***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1)

이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.

💡 ''해시 알고리즘''??

해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.

HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.

HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.

HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.

 java / HashMap 사용 

1. 먼저 HashMap을 Map<>을 통해서 생성하자.

• HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
• Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.

import java.util.HashMap;
import java.util.Map;

• HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
• 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
• 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.

Map<String, Integer> map = new HashMap<>();

2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.

for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }

• 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
• map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.

3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.

for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }

• 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
• 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
• 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
• string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
• 참고로 문자열의 길이를 반환할 때는 .length()이다! 

이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.

전체코드는 아래와 같다.

//해시로 풀이
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
                    //substring은 start index부터 end index까지
                    //java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열                        길이는 length() 
            }
        }
        
        
        return answer;
    }
}

***해시알고리즘을 사용한 java 코드가 궁금하다면 아래 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] java / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (2)

이 문제는 처음에 c++로는 2중 for문을 돌면서, 배열에서 첫번째 전화번호를 기준으로 시작하여, 다른 전화번호들 중 기준이 되는 전화번호보다 길이가 작으면 continue로 건너 뛰고, 그렇지 않으면, substr을 사용해 기준 전화번호 길이만큼 잘라서 비교한 후, 문자열이 동일하면 false를 반환하는 방식으로 접근했다.

이렇게 하면 테스트 케이스는 다 맞지만, 효율성에서 떨어지게 된다. 당연히 무식하게 2중 for문으로 일일이 확인하기 때문에 복잡도가 O(n^2)일 수 밖에 없다.

문제의 카테고리에서 주어진 방식대로 해시 알고리즘을 사용해서 풀면 효율성 문제를 해결할 수 있지만, 사실 해시 알고리즘을 어떻게 사용하는지 몰랐기 때문에, 다른 사람의 코드를 보고 참고하여 먼저 정렬을 이용해 더 쉽게 풀이하였다.

  c++ / sort 함수와 1중 for문으로 풀기 

string 타입의 배열 phone_book을 <algorithm> 헤더에 있는 기본 정렬 함수인 sort()를 통해 정렬한다.

숫자로 표현된 문자열의 경우 사전식으로, 각 문자열의 첫번째 값부터 비교한다. 

첫번째 값들이 다 동일하면 두번째 값을 비교한다.

즉 숫자 그 자체가 큰지가 아니라, 앞에 문자열부터 각 숫자가 작은 것 부터 정렬하는 방식이다

예) "12" "14" "112" 가 있으면, 112, 12, 14 순으로 정렬 된다.

첫번째 1은 모두 같고, 두번째 값이 1,2,4순이기 때문이다.

따라서 이렇게 정렬을 먼저 해 놓으면, 자연스럽게 접두사가 될 확률이 높은 문자열이 앞에 위치하게 되고, 해당 접두사를 가지는 문자열은 무조건 그 문자열의 다음에 정렬될 것이기 때문에, 이 방법은 1중 for문으로도 인접한 문자열에 대해 한번씩만 비교하면 된다. 

해당 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){
        string s = phone_book[i+1].substr(0, phone_book[i].size());
        if(phone_book[i]==s) {
            answer = false;
            break;
        }
    }
  
    return answer;
}

• sort함수에 배열의 첫번째 요소와, 배열의 마지막 요소를 인자로 넣어주면, 자동으로 정렬된다.
• 1중 for문을 통하여 string 문자열 s에는 현재 접근하는 phone_book의 전화번호 바로 다음에 위치한 전화번호를, 접두사 길이 만큼 잘라 (substr을 사용) 저장한다. 이때 c++에서는 substr(시작 인덱스, 자르고 싶은 만큼의 문자열 크기) 이므로 이에 유의한다. 
• 그래서 현재 접두사 후보의 값과 s가 일치한다면 false를 반환하도록 answer에 설정해준다.

사실상 해시 알고리즘으로 푸는 의도의 문제이긴 하지만, 실제 코테에서는 이 방법을 꼭 사용하라는 명시가 없기 때문에, 위와 같이 효율적인 코드가 생각이 난다면 당연히 사용해도 좋다.

그러나 해시 알고리즘을 이번 기회에 알고 넘어 가기 위해 java를 이용해서 한번 더 풀어보았다.

2탄에서 이어서...