9월 3주차 문제 [ 1단계 ]

[Tokwasp]

📢 이번 주 알고리즘 스터디 문제

이번 주에는 총 4문제를 풉니다.
(정답률은 프로그래머스 기준)

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	달리기 경주	48%	🔗 바로가기
2	햄버거 만들기	56%	🔗 바로가기

---

🗓️ 발표

• 시간: 금요일 오전 10시
• 방식: 각자 풀이 공유 + 코드 리뷰

---

🚨 벌금 규칙

• 문제를 풀지 않은 경우 → 💸 1만 원

---

🔥 이번 주도 화이팅입니다!

[pia01190]

📌 달리기 경주

• List<String> <선수 이름> 사용 -> list.indexOf로 시간 초과
• List<String> <선수 이름>, Map<String, Integer> <선수 이름, 순위> -> value로 key를 찾기위해 map.entrySet()을 돎 -> 시간초과
• list.remove(), list.add() -> O(n)으로 시간 초과
• list.set() -> O(1)로 성공

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        List<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < players.length; i++) {
            list.add(players[i]);
            map.put(players[i], i);
        }
        
        for (int i = 0; i < callings.length; i++) {
            String player = callings[i];
            int rank = map.get(player);
            String frontPlayer = list.get(rank - 1);
            
            list.set(rank - 1, player);
            list.set(rank, frontPlayer); 

            map.put(player, rank - 1);
            map.put(frontPlayer, rank);
        }
        
        String[] answer = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

📌 햄버거 만들기

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• 브루트포스로 풀었지만 시간초과로 실패 (Stack + StringBuilder)
• 전체가 아닌 4자리(빵 – 야채 – 고기 - 빵)만 비교하니 성공 -> Stack 필요없고 StringBuilder만 사용

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        int count = 0;
        String hamburger = "1231";
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < ingredient.length; i++) {
            sb.append(ingredient[i]);
            
            if (sb.length() < hamburger.length()) {
                continue;
            }
            
            if (sb.substring(sb.length() - 4).equals(hamburger)) {
                sb.delete(sb.length() - 4, sb.length());
                count++;
            }
        }
        
        return count;
    }
}

[sduddla]

1️⃣ 달리기 경주

첫 번째 시도

1. players 배열을 스프레드 연산자로 복사
2. callings 배열을 반복문 돌려 indexOf로 불린 선수 현재 위치 찾기
3. 맨 앞이 아닌 경우에만 앞사람과 자리 교환 후 결과 반환

• 테스트 10, 11, 12에서 시간 초과
• indexOf가 배열을 처음부터 끝까지 탐색하다 보니, 호출 수가 많아질 경우 시간 초과 발생

두 번째 시도

1. save 객체에 이름: 위치 저장
2. callings 배열을 반복문으로 돌려서 불린 선수의 현재 위치를 save에서 조회
3. 맨 앞이 아닌 경우에만 prev 변수에 앞사람 이름 저장 후, players 배열에서 두 사람 자리 교환
4. 교환된 결과에 맞춰 save 객체의 위치 값 업데이트 후 결과 반환

function solution(players, callings) {
    let save = {};
    for(let i = 0; i < players.length; i++) {
        save[players[i]] = i; // 선수 이름과 위치 저장(mumu:0, soe:1)
    }
    
    for(let name of callings) {
        let index = save[name]; // 불린 선수 현재 위치 찾기
        
        if(index > 0) { // 불린 선수가 맨 앞이 아닌 경우
            let prev = players[index - 1]; // 불린 선수 앞 사람 이름
            
            // players 배열에서 자리 교환
            [players[index - 1], players[index]] = [players[index], players[index - 1]];
            
            // 위치 값 업데이트
            save[name] = index  - 1;
            save[prev] = index;
        }
    }
    
    return players;
}

---

2️⃣ 햄버거 만들기

1. 스택에 재료 차례대로 쌓기
2. 스택에 4개 이상 쌓였을 때, 마지막 4개 확인 ([빵-야채-고기-빵] 이므로 스택에 최소 4개 이상 있어야 햄버거 패턴 검사 가능)
3. 햄버거 패턴(1231)과 일치할 경우 스택의 마지막 4개 제거
4. 완성된 햄버거 개수 카운트

function solution(ingredient) {
    // 1 빵
    // 2 야채
    // 3 고기
    // 1 2 3 1
    
    let stack = [];
    let hamburger = 0; // 완성된 햄버거 개수
    
    for(let i = 0; i < ingredient.length; i++) {
        stack.push(ingredient[i]); // 재료 쌓기
        
        if(stack.length >= 4) { // 스택에 4개 이상 쌓였을 때
            let four = stack.slice(-4).join(''); // 마지막 4개 검사하기
            
            if(four === '1231') { // 햄버거 패턴 1231과 일치하면
                stack.splice(-4); // 스택에서 제거
                hamburger++;
            }
        }
    }
    return hamburger;
}

[Tokwasp]

🏃 [달리기 경주]

• 시간 복잡도: 호출 100만
• 접근 방법: 추월한 선수의 인덱스를 빠르게 찾기 위해 HashMap 사용
• 구현 포인트: 선수 배열에서 위치 교환 후, map 에도 인덱스 업데이트

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> nameIndexMap = new HashMap<>();
        
        // 입력 받기
        for(int i = 0; i < players.length; i++){
            String name = players[i];
            nameIndexMap.put(name, i);
        }
        
        // 추월 입력 받기
        for(int i = 0; i < callings.length; i++){
            String calling = callings[i];
            
            // 앞 뒤사람 교체
            int index = nameIndexMap.get(calling);
            String behind = players[index];
            String front = players[index - 1];
            
            String temp = front;
            players[index - 1] = behind; 
            players[index] = temp;
            
            // map에도 인덱스 업데이트
            nameIndexMap.put(behind, nameIndexMap.get(behind) - 1);
            nameIndexMap.put(front, nameIndexMap.get(front) + 1);
        }
        return players;
    }
}

---

🍔 [햄버거 만들기]

• 매번 마지막 4개 재료 확인
• 햄버거 순서와 일치시 제거
• 시간 복잡도: 4 * 100만 = 400만
• 느낀점: 생각 보다 어려움 / 항상 완전 탐색 가능 여부를 먼저 확인

class Solution {
    public int solution(int[] ingredients) {
        int[] order = {1,2,3,1};
        List<Integer> list = new ArrayList<>();
        
        int count = 0;
        for(int i = 0; i < ingredients.length; i++){
            int ingredient = ingredients[i];
            list.add(ingredient);
            
            if(list.size() < order.length) continue;
            
            // 마지막 원소 4개를 뽑는다
            List<Integer> sub = list.subList(list.size() - 4, list.size());
            boolean isEquals = true;
            
            // 재료의 순서가 일치 하는지 확인
            for(int index = 0; index < order.length; index++){
                if(order[index] != sub.get(index)){
                    isEquals = false;
                    break;
                }
            }
            
            // 일치 한다면 재료 4개 제거
            if(isEquals){
                list.subList(list.size() - 4, list.size()).clear();
                count++;
            }
        }
        return count;
    }
}

[dbrkdgus00]

햄버거 만들기

해결 방법

• 재료들을 차례대로 리스트에 쌓음
  -> 재료가 들어올 때마다 ArrayList에 추가한다.

• 리스트의 마지막 4개가 [1, 2, 3, 1]이면 햄버거 완성
  -> 마지막 4개가 빵-야채-고기-빵 순서인지 직접 비교한다.

• 맞으면 그 4개 재료를 리스트에서 제거하고 햄버거 개수를 1 증가

• 끝까지 반복하면서 포장한 햄버거 수를 센다.

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {

        // 햄버거 개수를 세는 변수
        int answer = 0;

        // 재료를 담을 리스트를 만든다 
        List<Integer> list = new ArrayList<>();

        // 배열 하나씩 보면서 처리
        for (int i = 0; i < ingredient.length; i++) {
            // 리스트에 하나씩 추가
            list.add(ingredient[i]);

            // 리스트에 재료가 4개 이상일 때만 검사 가능
            if (list.size() >= 4) {
                int size = list.size();

                // 마지막 4개의 재료가 [1,2,3,1] 순서인지 확인
                if (list.get(size - 4) == 1 &&
                    list.get(size - 3) == 2 &&
                    list.get(size - 2) == 3 &&
                    list.get(size - 1) == 1) {

                    // 햄버거 완성됐으니까 재료 4개 제거
                    list.remove(size - 1); // 뒤에서부터 하나씩 제거
                    list.remove(size - 2);
                    list.remove(size - 3);
                    list.remove(size - 4);

                    // 햄버거 하나 추가
                    answer++;
                }
            }
        }

        return answer;
    }
}

달리기 경주

해결 방법

• 선수들의 이름을 순서대로 ArrayList에 저장한다.
  -> 이 리스트가 현재 등수 순서를 나타냄 (0번 인덱스 = 1등)

• 해설자가 부른 이름을 하나씩 확인하면서,
  -> 그 이름이 리스트에서 몇 번째(index) 인지 찾는다.

• 찾은 위치의 선수와 바로 앞 선수의 자리를 바꾼다.
  -> 리스트에서 set()을 이용해 직접 바꿈.

• 이 과정을 모든 호출에 대해 반복한다.

• 마지막으로 리스트를 배열로 바꿔서 리턴한다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        // 선수들을 순서대로 리스트에 담아
        List<String> order = new ArrayList<>();
        for (int i = 0; i < players.length; i++) {
            order.add(players[i]);
        }

        // 해설자가 부른 이름을 하나씩 확인
        for (int i = 0; i < callings.length; i++) {
            String calledName = callings[i];  // 불린 선수 이름

            // 그 선수가 현재 몇 번째인지 찾아
            int idx = order.indexOf(calledName);

            // 바로 앞 선수와 자리 바꿔
            String frontPlayer = order.get(idx - 1);
            order.set(idx - 1, calledName);     // 앞자리에 내가 가고
            order.set(idx, frontPlayer);        // 나는 그 사람과 자리를 바꿈
        }

        // 리스트를 배열로 바꿔서 리턴
        String[] answer = new String[order.size()];
        for (int i = 0; i < order.size(); i++) {
            answer[i] = order.get(i);
        }

        return answer;
    }
}