개발옹

문제 링크

문제 설명

고객의 약관 동의를 얻어서 수집된 1 ~ n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다.

예를 들어, A라는 약관의 유효기간이 12달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 

당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다.

모든 달은 28일까지 있다고 가정합니다.

오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privates가 매개변수로 주어집니다. 이때 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냅니다.
• 1 ≤ terms의 길이 ≤ 20
  • terms의 원소는 "약관 종류 유효기간" 형태의 약관 종류와 유효기간을 공백 하나로 구분한 문자열입니다.
  • 약관 종류는 A~Z중 알파벳 대문자 하나이며, terms 배열에서 약관 종류는 중복되지 않습니다.
  • 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다.
• 1 ≤ privacies의 길이 ≤ 100
  • privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냅니다.
  • privacies의 원소는 "날짜 약관 종류" 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열입니다.
  • 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어집니다.
  • privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어집니다.
• today와 privacies에 등장하는 날짜의 YYYY는 연도, MM은 월, DD는 일을 나타내며 점(.) 하나로 구분되어 있습니다.
  • 2000 ≤ YYYY ≤ 2022
  • 1 ≤ MM ≤ 12
  • MM이 한 자릿수인 경우 앞에 0이 붙습니다.
  • 1 ≤ DD ≤ 28
  • DD가 한 자릿수인 경우 앞에 0이 붙습니다.
• 파기해야 할 개인정보가 하나 이상 존재하는 입력만 주어집니다.

입출력 예

문제 풀이

[구현방식 생각]

약관 종류별 유효기간을 개인정보 수집 일자에서 계산해서 오늘 일자와 비교한다.

개인정보 수집일자 + 약관 유효기간 > 오늘 : 보관 가능한 개인정보

개인정보 수집일자 + 약관 유효기간 < 오늘 : 파기해야 할 개인정보

수집된 개인정보 중 파기해야 할 개인정보를 반환해야 하므로,

수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies를 순회하면서 각 정보의 보관 가능 여부를 판단하는 걸로 구현했다.

[고려사항]

privacies의 최대 길이는 100이므로 한 원소씩 확인해도 시간 초과하지 않을 것이다.

그리고 파기해야 할 개인정보는 무조건 하나 이상 존재하므로 result가 null인 경우는 없기 때문에 null 예외처리는 제외해도 된다.

또한 약관 종류로 주어진 약관만 privacies에 주어지므로 이에 대한 예외처리도 하지 않아도 된다.

그리고 파기될 약관 개수가 몇 개인지 모르기 때문에 정답 배열은 리스트로(ArrayList)로 초기화한다.

약관 종류는 String이기 때문에 유효기간 정보를 담을 자료구조는 Map으로 한다.

[풀이 과정]

1. 오늘 일자(today), 약관 종류 배열(terms) 구현 용도에 맞게 세팅
   • 오늘 일자는 온점(.)을 구분자로 연, 월, 일로 변수에 저장
   • 약관 종류를 Key, 유효기간을 Value로 해서 Map에 저장
2. privacies 순회하면서 약관 유효기간 계산
   • 날짜와 약관 종류를 공백을 구분자로 분리하여 저장
   • Map에서 해당하는 약관 종류의 유효기간 가져와서 달(month)에 더함
     • 계산한 달이 12월을 넘어가는 경우 연도에 1 더하고 달에 12 빼기
   • 계산한 유효 일자랑 현재 일자 비교
     • 파기되지 않는 경우(=보관 가능한 경우)를 체크
     • 위 조건에 해당하지 않는 경우, 정답 리스트에 추가
3. int[]을 반환해야하므로 List 순회해서 answer 배열에 담아서 반환

[구현시 고려한 사항]

문자열을 구분할때 split()을 사용할지, StringTokenizer를 사용할지 고민했는데,

자바 공식 문서를 확인해보니 StringTokenizer는 레거시 클래스로, 호환성을 위해 사용되고 있기때문에  spilt 함수를 사용할 것을 권장하고 있다.

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

그래서 날짜를 년,월,일로 구분할때나 약관 정보를 가져올때 split() 함수를 사용했다.

💡 spilt() 주의사항

split()은 정규표현식으로 문자열을 구분하기 때문에 온점(.)을 구분자로 구분하려고 한다면 온점 앞에 역슬래시(\)를 붙여줘야한다. 

이때 Java에서 역슬래시를 표현하기 위해서는 앞에 역슬래시(\)를 붙여줘야한다. (\\)

즉, split("\\.")으로 사용해야 온점을 구분자로 문자열을 분리할 수 있다.

* 정규표현식에서 온점(.)은 임의의 한 문자를 뜻하기 때문에 온점(.)만 구분자로 넣는 경우 (즉,  split(".")), 그냥 빈 배열이 반환된다.

코드

import java.util.*;
class Solution {
	public static int[] solution(String today, String[] terms, String[] privacies) {
        // 오늘 일자 Y,M,D로 분리
        String[] todayInfo = today.split("\\.");
        int todayY = Integer.parseInt(todayInfo[0]);
        int todayM = Integer.parseInt(todayInfo[1]);
        int todayD = Integer.parseInt(todayInfo[2]);

        // 약관 종류
        Map<String, Integer> termsMap = new HashMap<>();
        for (String el : terms) {
            String[] temp = el.split(" ");
            termsMap.put(temp[0], Integer.parseInt(temp[1]));
        }

        // privacies 순회하면서 약관 유효기간 계산
        List<Integer> list = new ArrayList<>();
        int collectionY, collectionM, collectionD;
        for (int i=0; i<privacies.length; i++) {
            String[] privacyInfo = privacies[i].split(" ");
            String[] collectionDate = privacyInfo[0].split("\\.");
            collectionY = Integer.parseInt(collectionDate[0]);
            collectionM = Integer.parseInt(collectionDate[1]);
            collectionD = Integer.parseInt(collectionDate[2]);

            String typeOfTerms = privacyInfo[1];

            collectionM += termsMap.get(typeOfTerms);
            while (collectionM > 12) { // 계산한 달이 12월을 넘어가는 경우 연도에 1추가
                collectionM -= 12;
                collectionY += 1;
            }

            // 계산한 유효 일자랑 현재 일자 비교 (파기되지 않는 경우(=보관 가능한 경우)를 체크)
            if (collectionY > todayY) {
                continue;
            } else if (collectionY == todayY) {
                if (collectionM > todayM) {
                    continue;
                } else if (collectionM == todayM) {
                    if (collectionD > todayD) continue;
                }
            }
           list.add(i+1);
        }

        int[] answer = new int[list.size()];
        int idx = 0;
        for (int index : list) {
            answer[idx++] = index;
        }
        return answer;
    }
}

문제 링크

문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
  • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
• 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
• 누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다. 
• 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.
  • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다. 
  • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항

• fees의 길이 = 4 
  • fees[0] = 기본 시간(분) | 1 ≤ fees[0] ≤ 1,439
  • fees[1] = 기본 요금(원) | 0 ≤ fees[1] ≤ 100,000
  • fees[2] = 단위 시간(분) | 1 ≤ fees[2] ≤ 1,439
  • fees[3] = 단위 요금(원) | 1 ≤ fees[3] ≤ 10,000
• 1 ≤ records의 길이 ≤ 1,000
  • records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
  • 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
  • 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
    • HH:MM은 00:00부터 23:59까지 주어집니다. 
    • 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
  • 차량번호는 자동차를 구분하기 위한, `0'~'9'로 구성된 길이 4인 문자열입니다. 
  • 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다. 
  • records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다. 
  • records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
  • 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다. 
  • 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다. 
  • 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
    • 주차장에 없는 차량이 출차되는 경우 
    • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우

입출력 예

문제 풀이

시각을 기준으로 오름차순 정렬되어있는 records를 차량번호을 기준으로 오름차순 정렬해서 사용 요금을 반환해야한다.

그래서 먼저 records를 차량번호를 Key값, 그 외 정보를 Value로 담아서 저장해서 계산해야겠다고 생각하여 구현했다.

[정의한 클래스 및 함수 설명]

[ParkingInfo 클래스]

• 차량번호별 주차 정보를 관리할 클래스
• 멤버 변수: 차량번호(carNum), 입차시간(inTime), 총 누적시간(totalTime)
  • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에, 입차시간과 출차시간을 쌍으로 묶어 저장할 필요는 없다고 판단하였다.
  • 입/출차 기록에서 출차인 경우, 총 누적시간(totalTime)을 계산하여 갱신하는 방식으로 구현했다.
• setTotalTime(doble totalTime)
  • 해당 차량의 총 누적시간을 갱신 
    • this.totalTime += totalTime
  • '주차장에 없는 차량이 출차되는 경우'나 '주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우'는 없기 때문에 총 누적시간 계산/갱신시 저장되어있던 입차시간(inTime)은 초기화한다.
    • this.inTime = "";
• implements Comparable<ParkingInfo> : @Override compareTo(ParkingInfo o)
  • 차량번호를 기준으로 정렬하기 위해 Comparable 인터페이스를 implements한다.
• @Override equals(), hashCode()
  • 차량번호를 기준으로 객체 비교
  • 객체의 멤버 변수인 차량번호(carNum)가 같다면, 같은 객체로 판단해야하기때문에 equals()와 hashCode()를 오버라이딩했다.

[calculateTime(String in, String out)]

public static double calculateTime(String in, String out) {
    double inH = Integer.parseInt(in.substring(0,2));
    double inM = Integer.parseInt(in.substring(2));
    double outH = Integer.parseInt(out.substring(0,2));
    double outM = Integer.parseInt(out.substring(2));

    return (outH * 60 + outM) - (inH * 60 + inM);
}

• 주차장 사용 시간 계산 메소드
• 이후 주차 요금 계산시 단위 시간 당 총 누적시간을 계산해야되어서 올림 연산이 필요하기 때문에 double로 선언
• 입/출차 시간의 시, 분을 나눠서, 시간에 *60해서 분으로 치환하여 계산한다.
  • 사용시간 = (출차 시 * 60 + 출차 분) - (입차 시 * 60 + 입차 분)

[풀이 과정]

1. records 순회하면서 Map, ParkingInfo 로 세팅
   • Map<String, ParkingInfo>
   • 입/출차 내역은 "시각 차량번호 내역" 형식의 문자열
     • 시각: "HH:MM"형식이므로 ":"를 공백으로 치환
       
       • 이후 누적시간 계산시 형변환하여 계산하기 위함
       • 올림 함수인 Math.ceil 을 정수형으로 계산시, 정수로 계산되기 때문에 원하는 값을 얻지 못할 수 있다.
         • 정수10/정수4를 올림함수를 이용하면 기대하던 3.0이 아니라 2.0이 반환된다.
         • 따라서 올림 값을 제대로 받으려면 실수형을 계산해야한다.
   • Map의 Key값인 차량번호가 이미 있는 경우
     • 내역이 입차(IN)인 경우, 저장된 ParkingInfo 객체에 inTime을 갱신
     • 내역이 출차(OUT)인 경우, 저장된 ParkingInfo 객체의 inTime을 가져와서 출차시간으로 총 누적시간 계산하고 갱신
       • calculateTime(String in, String out)
       • setTotalTime(double totalTime)
   • MaP의 Key값인 차량번호가 없는 경우(=입/출차기록이 없는 경우)
     • Key로 cardNum과 Value에 ParkingInfo를 세팅해서 Map에 추가한다.
     • OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 된다.
2. records 확인 및 List에 값 할당 / 정렬
   • Map에 저장된 차량 번호를 순회하면서
     • 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
       • 이때, 출차 시간은 23시 59분
     • 정렬을 위해 ParkingInfo를 리스트에 저장
       • infoList.sort(ParkingInfo::compareTo);
       • 정렬은 ParkingInfo에 오버라이딩 한 비교(compareTo)를 기준으로 한다.
3. 주차 요금 계산
   • fees 요소를 기본 시간, 기본 요금, 단위 시간, 단위 요금을 할당
   • 정렬을 한 list를 순회하면서 계산한 주차 요금을 int[] answer에 저장
     • 총 누적시간이 기본 시간이상이라면 요금 계산
       • 기본 요금 + 올림((총 누적시간 - 기본시간) / 단위 시간) * 단위 요금
     • 총 누적시간이 기본 시간을 넘지 않는다면 기본 요금을 저장
   • list에 이미 차량번호 순으로 정렬해두었기 때문에 answer 배열에 차량번호 순으로 주차 요금을 저장할 수 있다.

[구현시 고려(고민)한 사항]

records를 ParkingInfo로 저장할 때, 자바 클래스 중 List, Map 중 Map 으로 선택했다. 

입차/출차 내역이 있는지 확인해야 했기에 해당 Key값이 있는지 확인할 수 있는 구조가 필요했다.

•  Key 값을 차량번호로 두고 containsKey로 판단했다.

코드

import java.util.*;
class Solution {
	public static int[] solution(int[] fees, String[] records) {
        /**
         * 1. records 세팅
         *      - 이미 저장되어있는 차량번호 체크를 위해 map으로 선언
         */
        Map<String, ParkingInfo> map = new HashMap<>();
        for (String record : records) {
            StringTokenizer st = new StringTokenizer(record, " ");
            String time = st.nextToken().replace(":", "");
            String carNum = st.nextToken();
            String type =  st.nextToken();

            double inH, inM, outH, outM;
            if (map.containsKey(carNum)) {
                ParkingInfo carParkingInfo = map.get(carNum);
                if (type.equals("IN")) {
                    carParkingInfo.setInTime(time);
                } else { // type == "OUT"
                    // 이전에 저장되어있는 입차시간 가져와서 계산
                    String inTime = carParkingInfo.getInTime();
                    carParkingInfo.setTotalTime(calculateTime(inTime, time));
                }
            } else {
                // OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 됨
                map.put(carNum, new ParkingInfo(carNum, time));
            }
        }

        /**
         * 2. records 확인
         *      - 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
         *      - ParkingInfo를 리스트에 저장 : 정렬을 위함
         */
        List<ParkingInfo> infoList = new ArrayList<>();
        for (ParkingInfo mapInfo : map.values()) {
            String infoInTime = mapInfo.getInTime();
            if (!infoInTime.isBlank()) {
                mapInfo.setTotalTime(calculateTime(infoInTime, "2359"));
            }
            infoList.add(mapInfo);
        }
        infoList.sort(ParkingInfo::compareTo);

        /**
         * 3. 주차 요금 계산
         */
        double basicTime = fees[0];
        int basicPrice = fees[1];
        double unitTime = fees[2];
        int pricePerTime = fees[3];

        int[] answer = new int[map.size()];
        int idx = 0;
        for (ParkingInfo info : infoList) {
            int calPrice = basicPrice;
            if (info.getTotalTime() >= basicTime) {
                calPrice += Math.ceil((info.getTotalTime() - basicTime)/unitTime) * pricePerTime;
            }
            answer[idx++] = calPrice;
        }

        return answer;
    }

    public static double calculateTime(String in, String out) {
        double inH = Integer.parseInt(in.substring(0,2));
        double inM = Integer.parseInt(in.substring(2));
        double outH = Integer.parseInt(out.substring(0,2));
        double outM = Integer.parseInt(out.substring(2));

        return (outH * 60 + outM) - (inH * 60 + inM);
    }

    public static class ParkingInfo implements Comparable<ParkingInfo>{
        String carNum; // 차량번호

        String inTime; // 입차시간 (주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에)
        double totalTime; // 총 누적시간

        public ParkingInfo(String carNum, String inTime) {
            this.carNum = carNum;
            this.inTime = inTime;
            this.totalTime = 0;
        }

        public void setInTime(String inTime) {
            this.inTime = inTime;
        }

        public String getInTime() {
            return inTime;
        }

        public void setTotalTime(double totalTime) {
            this.inTime = ""; // 입차시간 초기화 (출차시간 입력되는 경우에만 totalTime Setting)
            this.totalTime += totalTime;
        }

        public double getTotalTime() {
            return totalTime;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ParkingInfo other = (ParkingInfo) o;
            return other.carNum == carNum;
        }

        @Override
        public int hashCode() {
            return Objects.hash(carNum);
        }

        @Override
        public int compareTo(ParkingInfo o) {
            int intCarNum = Integer.parseInt(this.carNum);
            int intOtherCarNum = Integer.parseInt(o.carNum);
            return intCarNum - intOtherCarNum;
        }
    }
}

참고 포스팅

문제 링크

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k 입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000 
  • 1 ≤ sequence의 원소 ≤ 1,000 
  • sequence는 비내림차순으로 정렬되어 있습니다. 
• 5 ≤ k ≤ 1,000,000,000 
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

입출력 예

문제 풀이

[고려사항]

sequence는 최대 1,000,000(100만)개이니까 시간 복잡도를 고려해서 구현해야한다.

O(N^2)이 되면 1,000,000,000,000가 되어서 시간 초과로 실패할 것이기 때문이다.

[처음 생각으로만 한 풀이방법]

[실제 구현한 알고리즘 / 구현방법]

이 문제는 특정 조건을 만족하는 부분 구간을 구하는 문제이므로 투 포인터(Two Pointer) 알고리즘을 이용해서 풀면 된다.

투 포인터(Two Pointer) 알고리즘은 일반적으로 배열이 정렬되어 있을 때 사용하는 알고리즘이다.

투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적이고, 한 번의 반복으로 모든 요소를 처리할 수 있다.

배열을 순회하면서 누적합을 앞에서부터 구하면 되니까

start pointer를 0번에 두고 end pointer의 인덱스를 이동시키면서 누적 합을 구한다.

누적 합이 k 를 초과하면 start pointer를 이동시켜서 start ~ end pointer의 합을 구한다.

이때 마지막으로 저장된 누적 합에서 sequence[start pointer]를 빼주면 현재의 start ~ end pointer의 합이 된다.

예를 들어, [1,2,3,4,5]라면 1부터 4까지 누적하면 합이 10이므로 k를 넘어선다.

이때 start pointer를 2로 옮기면 2부터 4까지의 합인데, 이 합은 10에서 1을 뺀 9이다.

그렇게 진행하다가 누적합이 k와 같아지면 해당 start pointer와 end pointer를 반환한다.

start, end pointer를 앞쪽 인덱스부터 시작하면 가장 짧은 길이 + 가장 작은 인덱스 값을 만족시키는 인덱스를 반환할 수 있다.

[풀이 과정]

1. 첫번째 인덱스부터 start pointer와 end pointer가 마지막 인덱스를 가리킬때까지, 아래 과정을 반복하여 정답 후보를 구한다.
   1. 누적 합이 k인 경우(sum==k), 정답 후보에 해당 인덱스를 저장한다.(start pointer, end pointer)
   2. 누적 합이 k보다 작고(sum<k), end pointer가 마지막 인덱스가 아니라면, end pointer를 한 칸 이동하고, 누적 합을 계산한다.
   3. 누적 합이 k보다 크거나(sum>k), end pointer가 마지막 인덱스라면, 현재 start pointer의 값을 누적 합에서 빼주고 start pointer를 한 칸 이동한다. 
2. 정답 후보 중 1) 길이가 짧고, 2) 인덱스가 가장 작은 부분 수열 인덱스를 반환한다.

[구현시 고려한 사항]

최종 답을 list에서 SubSequence 클래스의 left, right를 각각 가져와서 int배열로 반환을 할지 고민했는데, 

• 즉, return new int[]{answerList.get(0).left, answerList.get(0).right};

SubSequence 클래스에 (left, right)를 int 배열로 반환하는 함수(getSequence)를 생성해서 반환하는 걸로 구현했다.

함수를 생성하는게 가독성이 좋고, 

• return answerList.get(0).getSequence();

생성한 SubSequence 클래스의 요소를 조합해서 반환하는 것이므로 SubSequence 클래스에 함수를 생성하는 것이 이 클래스의 목적성도 좀 더 명확하다고 생각했기 때문이다.

코드

public class Solution {
    public static int[] solution(int[] sequence, int k) {
        int startPointer = 0;
        int endPointer = 0;
        List<SubSequence> answerList = new ArrayList<>(); // 정답 후보 저장할 리스트

        int sum = sequence[startPointer];
        int length = sequence.length;
        while (true) { // end pointer가 마지막 인덱스를 탐색할 때까지
            if (sum == k) answerList.add(new SubSequence(startPointer, endPointer, endPointer-startPointer+1));

            if (startPointer == length - 1 && endPointer == length - 1) break;

            if (sum < k && endPointer < length - 1) { // 누적 합이 k보다 작다면
                endPointer++; // end pointer 한칸 이동
                sum += sequence[endPointer]; // 누적 합 계산
            } else { // 누적 합이 k보다 크거나 end pointer가 마지막 인덱스라면
                sum -= sequence[startPointer]; // 움직인 start pointer에서 end pointer까지의 누적합은 움직이기 전 start pointer를 뺀 값
                startPointer++; // start pointer 이동
            }
        }
        // 정답 후보에서 1) 길이가 짧고 2) 인덱스가 작은 부분 수열 인덱스를 반환
        answerList.sort(SubSequence::compareTo);

        return answerList.get(0).getSequence();
    }

    public static class SubSequence implements Comparable<SubSequence> {
        int left, right, size;
        public SubSequence(int left, int right, int size) {
            this.left = left;
            this.right = right;
            this.size = size;
        }

        public int[] getSequence() {
            return new int[]{this.left, this.right};
        }

        @Override
        public int compareTo(SubSequence o) {
            if (this.size == o.size) return this.left - o.left;
            else return this.size - o.size;
    }
}

문제 링크

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 

"()()" 또는 "(())()" 는 올바른 괄호입니다. 

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수 
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

첫번째 문제 풀이

* 혼자 풀어본 후 다른 코드를 보고나서 개선된 문제풀이를 하나 더 작성했다.

괄호 문자열(s)를 한 문자씩 확인하면서 다음 문자랑 괄호 조합이 되는지 확인해야한다.

괄호를 Stack에 쌓으면서 이전 문자와 다음 문자의 조합이 괄호가 되는지 알 수 있다.

원본 문자열의 문자를 저장할 Stack과 괄호 조합이 안되는 경우 저장할 Stack을 두 개 선언하여 구현했다.

[고려사항]

괄호 문자열(s)는 최대 100,000(10만)개 이하이므로 문자열 조작에 대한 시간 복잡도를 고려해야한다.

시간을 최소화할 수 있는 방법으로 Stack을 생각했다.

Stack의 삽입, 삭제, isEmpty, peek 연산은 모두 O(1)의 시간 복잡도를 가지고, 필요한 연산은 저 4가지면 되기 때문이다.

그래서 내가 구현한 방식에서는

    1) Stack에 문자열을 문자로 변환하여 삽입 : O(N)

    2) Stack을 순회하면서 Stack 연산 : O(N)이라서

전체 시간 복잡도는 O(N)이 된다.

[풀이 과정]

1. 문자열을 문자(char)로 변환해서 원본 Stack에 할당한다. 
   • String에서 char로 형변환을 하기 위해 charAt()을 이용한다.
2. 괄호 완성이 안되는 경우, 원본 Stack의 char값을 저장할 Stack을 선언
3. 아래 과정을 원본 Stack이 빌 때 까지 반복한다.
4. 원본 Stack에서 pop()한 값을, 저장 Stack에 값이 있는 경우에 괄호 완성이 되는지 확인한다.
   • 괄호가 완성되면 저장 Stack에서 해당 값을 pop(); ➔ 괄호 삭제
   • 괄호가 완성되지 않으면 저장 Stack에 해당 값을 push();
5. 반복문이 끝난 후, 저장 Stack에 값이 남아있다면 올바른 괄호가 아니다.
   • 괄호가 완성되어서 값이 pop(), 즉 삭제되었다면 저장 Stack은 비어있어야한다.

첫번째 코드

import java.util.*;
class Solution {
	public boolean solution(String s) {
        Stack<Character> stackInitial = new Stack<>(); // 문자열을 문자로 분할해서 넣을 Stack
        for (int i=0; i<s.length(); i++) {
            stackInitial.push(s.charAt(i));
        }

        char c;
        Stack<Character> stackStorage = new Stack<>(); // 괄호 완성이 안되는 경우 초기 Stack의 char 값을 저장할 Stack
        while (!stackInitial.isEmpty()) {
            c = stackInitial.pop();
            if (!stackStorage.isEmpty()) {
                char charStorage = stackStorage.peek();
                if (c == '(' && charStorage == ')') { // 괄호 완성하면 다음 문자로 넘어감
                    stackStorage.pop();
                    continue;
                }
            }
            stackStorage.push(c);
        }

        // 남은 문자열이 있으면 실패
        if (!stackStorage.isEmpty()) return false;
        else return true;
    }
}

두번째 문제 풀이

다른 사람들의 풀이를 보니까, 완성되지 않은 괄호를 굳이 Stack에 넣지 않고 열린 괄호와 닫힌 괄호의 개수로 확인하는 방법도 있다.

열린 괄호인 경우엔 변수를 증가시키고, 닫힌 괄호인 경우엔 변수를 감소시키면서 연산하고,

마지막에 변수가 0인 경우에만 올바른 괄호라고 판단하면 된다.

실행 시간을 비교해보면 Stack을 이용한 첫번째 코드보다 훨씬 개선된 것을 확인할 수 있었다.

 두번째 코드

class Solution {
    boolean solution(String s) {
        
        int cnt = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') { // 열린 괄호일때
                cnt++;
            } else {
                if (cnt == 0) return false; // 닫힌 괄호일때 cnt가 0이면 열린 괄호가 없는것이므로 올바른 괄호 아님
                else cnt--;
            };
        }
        if (cnt == 0) return true;
        else return false;
        
    }
}

문제 링크

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

문제 풀이

우선 카펫의 전체 너비는 갈색 격자와 노란 격자를 합한 값이 되고, 그건 가로*세로와 같다.

전체 너비(total) = brown + yello = 가로 * 세로

그리고 카펫의 테두리의 1줄은 갈색으로 칠해져 있다고 했으므로, 

노란 격자의 양 옆과 위, 아래로 갈색 격자가 1개씩 있어야 하기때문에 아래와 같은 식이 성립한다.

노란 격자(yellow) = (가로 - 2) * (세로 - 2)

두 식을 통해 갈색 격자는 아래와 같은 식을 만족한다.

갈색 격자(brown) = 총 너비(total) - yello

결국, 노란 격자와 갈색 격자의 식을 모두 만족하는 가로, 세로 조합을 구하면 되는 문제!

[알고리즘, 구현방법]

이 문제는 가로*세로 조합에 대한 탐색이 필요하므로, 완전 탐색으로 풀었다.

[풀이 과정]

1. 가로*세로 조합 탐색 (가로가 큰 기준)
2. 총 너비를 가로로 나누었을때, 나머지가 생기지 않는 경우, 즉 나누어 떨어지는 경우만 탐색
   • 각 조합마다 가로와 세로가 yellow, brown 식에 대입했을때 모두 true인 경우가 정답
3. 정답이 나올때까지 반복

[구현시 고려한 사항]

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길기때문에 조합을 탐색할때 가로가 큰 경우부터 확인한다.

 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total = brown + yellow;

        // 가로 길이 <= 세로 길이 이므로, 가로 길이가 큰 것 부터 탐색
        for (int width=total; width>0; width--) {
            if (total % width != 0) continue; // 나누어 떨어지지 않는 경우 넘어가기

            int height = total / width;
            int y = (width-2) * (height-2);
            if (brown == total - y && yellow == y) {
                answer[0] = width;
                answer[1] = height;
                break;
            }
        }
        return answer;
    }
}

문제 링크

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 

   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5 

   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12] 

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 

   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13 

   가진 음식의 스코빌 지수 = [13, 9, 10, 12] 

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

문제 풀이

[고려사항]

scoville 배열을 오름차순으로 정렬해서 1번째 원소가 K 이상일때까지 음식을 섞어서 횟수를 구한다.

- 새로운 음식의 스코빌 지수를 만들때마다 scovillle 배열은 오름차순으로 정렬되어야 한다. 

- scoville의 길이는 최대 1,000,000(100만), K는 최대 1,000,000,000(10억)이므로 시간복잡도를 고려해야한다.

[알고리즘, 구현방법]

이 문제는 array나 ArrayList로 구현하면 효율성 검증을 통과하지 못한다.  

그래서 최솟값을 빠르게 찾을 수 있는 완전 이진트리 형태의 구조를 가지는 Heap으로 구현해야한다.

처음에는 Heap의 삽입, 삭제 연산을 array로 구현해서 제출했는데 시간초과로 실패했다.

*이후에 찾아보니까 이 문제를 Heap으로 직접 구현해서 푸는걸 시도한 사람들도 실패했다고 한다.

그래서 Java에서 Heap구조를 가진 PriorityQueue(우선순위 큐)로 구현했다. 

[풀이 과정]

1. 우선순위 큐를 오름차순으로 생성하여 scovile 값 삽입
2. Queue의 1,2번째 원소를 가져와서 계산 
   • 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
3. 계산한 값을 Queue에 삽입하고 섞은 횟수 증가
4. 2,3번 과정을 Queue의 첫번째 원소가 K보다 같거나 클때까지 반복
   • 이때, Queue의 사이즈가 2미만이면 스코빌 지수를 K이상으로 만들수 없다는 뜻이므로 -1 return

[구현시 고려한 사항]

PriorityQueue 함수 호출시 실패하는 경우 Exception을 던지는 함수가 아닌, null이나 false를 반환하는 함수로 구현했다.

• offer() vs add()
• poll() vs remove()
• element() vs peek()

정답 코드

import java.util.*;
class Solution {
    // PriorityQueue 사용하여 Heap (Min-Heap) 으로 구현
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int val : scoville) {
            queue.offer(val);
        }

        // 스코빌 지수 계산
        int first, second, mix;
        int count = 0; // 섞은 횟수
        // 루트 값이 K와 같거나 크면 종료
        while (queue.peek() < K) {
            if (queue.size() < 2) {
                return -1;
            } else {
                // 연산할 값 가져오기
                first = queue.poll();
                second = queue.poll();

                // 섞은 음식의 스코빌 지수를 삽입
                mix = first + (second * 2);
                queue.offer(mix);
                count++;
            }
        }
        return count;
    }
}

문제 링크

문제 설명

카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.

이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

1번 목표가 우선이며, 2번 목표가 그 다음입니다. 

이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.

• n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.

카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

• 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
• 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다.

이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ users의 길이 = n ≤ 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
  • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
• 1 ≤ emoticons의 길이 = m ≤ 7
  • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  • 100 ≤ emoticons의 원소 ≤ 1,000,000
  • emoticons의 원소는 100의 배수입니다.

입출력 예

문제 풀이

할인율(10%, 20%, 30%, 40%) 조합을 구해서 사용자(users)별로 모든 이모티콘의 구매 여부를 확인해서 계산해야한다.

모든 경우의 수를 확인해야하기 때문에 완전탐색으로 구현했다.

할인율은 4가지로 고정되어있고, 이모티콘은 최대 7개, 사용자는 최대 100명이므로 완전탐색으로 구현할 경우,

시간복잡도 Worst Case가 O(100*4^7)로, 약 160만 정도가 나오므로 완전탐색으로 구현할 수 있다고 생각했다.

[풀이 과정]

1. DFS로 모든 할인율 조합을 구하고
2. 모든 이모티콘에 적용할 할인율 조합이 결정되면
3. 사용자별로 이모티콘 할인율이 적용된 가격에 대한 구매 여부를 판단하여 (users 정보를 완전탐색)
4. 이모티콘 플러스 가입 여부와 매출액을 갱신
5. 모든 user의 탐색이 끝나면 해당 조합에 대한 최대값 여부를 확인하여 저장

코드

class Solution {
    static int[] percent = {10, 20, 30, 40}; // 할인율 배열
    static int maxSubscribeCnt = 0; // 최대 이모티콘 플러스 가입자 수
    static int maxProfit = 0; // 최대 이모티콘 매출액
    
    public int[] solution(int[][] users, int[] emoticons) {
        findMaxValue(0, emoticons.length, new int[emoticons.length], users, emoticons);
        return new int[]{maxSubscribeCnt, maxProfit};
    }

    public void findMaxValue(int index, int emotionsLength, int[] discounts, int[][] users, int[] emoticons) {
        // 이모티콘 개수만큼 할인율 조합이 생성되었다면 계산
        if (index == emotionsLength)
        {
            int subscribe = 0;
            int profit = 0;

            // 사용자별로 이모티콘의 할인율을 계산한 가격으로 판단
            for (int[] user : users) {
                int cost = 0; // 각 사용자가 지불할 금액

                for (int j=0; j<emotionsLength; j++) {
                    // 할인율이 사용자의 기준 비율 이상이면 이모티콘 구매
                    if (discounts[j] >= user[0]) {
                        cost +=  emoticons[j] * (100 - discounts[j])/100;
                    }
                }

                if (cost >= user[1]) subscribe++; // 사용자의 가격보다 총 합이 크면 구독 +1
                else profit += cost;  // 아니면 매출액에 포함
            }

            // 최대 값 갱신
            if (subscribe > maxSubscribeCnt) { // 가입자 수가 1순위이므로 먼저 체크
                maxSubscribeCnt = subscribe;
                maxProfit = profit;
            } else if (subscribe == maxSubscribeCnt) { // 최대 가입자 수와 계산한 가입자 수가 같으면, 매출액 갱신
                maxProfit = Math.max(maxProfit, profit);
            }
            return;
        }
        else
        {
            // 할인율 조합 생성
            for (int i=0; i<4; i++) {
                discounts[index] = percent[i];
                findMaxValue(index+1, emotionsLength, discounts, users, emoticons);
            }
        }

    }
}

www.acmicpc.net/problem/1500

문제

합이 S인 K개의 양의 정수 중 그 곱이 가장 큰 경우를 구하는 문제이다.

• 입력: 첫째 줄에 S와 K가 주어짐(K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다.
• 출력: 첫째 줄에 정답 출력. 답은 9,223,372,036,854,775,807보다 작다

풀이 과정

이 문제는 수학문제로, 곱하는 수의 차이가 가장 작은 경우를 구하면 된다.

1. S를 K로 나눠서 몫과 나머지를 각각 저장한다.

2. 몫을 K개 만큼 저장한다.

3. 나머지 수만큼 몫에 1씩 더해준다. 이외의 것들은 몫으로 남겨둔다.

4. 수를 모두 곱해서 결과를 출력한다.  

예시

입력: S=52, K=9

1. S/K = 5, S%K = 7

2. 5,5,5,5,5,5,5,5,5

3. 나머지가 7이므로 7번 반복하여 몫에 1씩 더해준다

4. 6,6,6,6,6,6,6,5,5를 곱한 곱은 6,998,400

JAVA 소스코드

출력은 9,223,372,036,854,775,807보다 작으므로 변수는 모두 long형으로 선언한다.

※ 자바의 기본 자료형(primitive type) 정수형의 범위

* 백준에 자바코드로 올릴경우, class이름은 반드시 Main으로 해야하고 패키지명은 제외해야한다. 아니면 런타임에러 뜬다. 본인도 처음에 몰라서 알수없는 Runtime에러때문에 당황했었다.

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        List<Long> list = new ArrayList<>();//k개의 정수를 저장할 리스트
        long result = 1; //k개의 정수를 곱한 결과
        long s = scan.nextInt();
        long k = scan.nextInt();
        long div = s/k; //s를 k로 나눈 몫
        long res = s%k; //나머지

        //몫을 k개만큼 저장
        for(int i=0;i<k;i++){
            list.add(div);
        }
        //나머지만큼만 1씩 더함
        for(int i=0;i<res;i++){
            list.set(i,(list.get(i)+1));
        }
        //result에 k개의 정수를 곱함
        for(int i=0;i<list.size();i++){
            result *= list.get(i);
        }

        System.out.println(result);
    }
}