'알고리즘/프로그래머스 JAVA LV.1' 카테고리의 글 목록 (8 Page)

728x90

SMALL

문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

5 ≤ players의 길이 ≤ 50,000
- players[i]는 i번째 선수의 이름을 의미합니다.
- players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
- players에는 중복된 값이 들어가 있지 않습니다.
- 3 ≤ players[i]의 길이 ≤ 10
2 ≤ callings의 길이 ≤ 1,000,000
- callings는 players의 원소들로만 이루어져 있습니다.
- 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

입출력 예

players callings result

["mumu", "soe", "poe", "kai", "mine"]

["kai", "kai", "mine", "mine"]

["mumu", "kai", "mine", "soe", "poe"]

입출력 예 설명

입출력 예 #1

4등인 "kai" 선수가 2번 추월하여 2등이 되고 앞서 3등, 2등인 "poe", "soe" 선수는 4등, 3등이 됩니다. 5등인 "mine" 선수가 2번 추월하여 4등, 3등인 "poe", "soe" 선수가 5등, 4등이 되고 경주가 끝납니다. 1등부터 배열에 담으면 ["mumu", "kai", "mine", "soe", "poe"]이 됩니다.

package LV1;

import java.util.HashMap;
import java.util.LinkedList;

import org.w3c.dom.Node;

/*
얀에서는 매년 달리기 경주가 열립니다.
해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다.
예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때,
해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다.
즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와
해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때,
경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 */
public class H178871 {
	public String[] solution(String[] players, String[] callings) {
		HashMap<String, Integer> map = new HashMap<>();
		LinkedList<String> list = new LinkedList<>();

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

		for(String calling : callings) {
			int idx = map.get(calling);
			list.remove(idx);
			list.add(idx-1, calling);

			map.put(calling, idx-1);
			map.put(list.get(idx), idx);
		}

		return list.toArray(new String[0]);
	}
}

우리는 각 선수의 이름을 키로, 그들의 위치를 값으로 가지는 HashMap을 생성

그런 다음 LinkedList를 사용하여 플레이어의 순서를 유지

해설진이 선수의 이름을 부를 때마다, 해당 선수를 찾아서 LinkedList에서 선수의 위치를 하나 앞으로 이동시키고, HashMap에서도 선수의 위치를 업데이트

테스트 1 〉	통과 (0.18ms, 72.5MB)
테스트 2 〉	통과 (0.31ms, 77.9MB)
테스트 3 〉	통과 (0.59ms, 74.7MB)
테스트 4 〉	통과 (2.81ms, 78.6MB)
테스트 5 〉	통과 (11.48ms, 88.7MB)
테스트 6 〉	통과 (43.50ms, 107MB)
테스트 7 〉	통과 (1018.39ms, 120MB)
테스트 8 〉	통과 (4328.13ms, 141MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	통과 (0.20ms, 87.9MB)
테스트 15 〉	통과 (0.13ms, 84.4MB)
테스트 16 〉	통과 (0.14ms, 72.8MB)

런타임 에러…ㅠㅠㅠ

package LV1;

import java.util.ArrayList;
import java.util.HashMap;

import org.w3c.dom.Node;

/*
얀에서는 매년 달리기 경주가 열립니다.
해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다.
예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때,
해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다.
즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와
해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때,
경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 */
public class H178871 {
	public String[] solution(String[] players, String[] callings) {
		// 각 선수의 현재 위치를 저장하기 위한 맵을 초기화합니다.
		HashMap<String, Integer> playerToPosition = new HashMap<>();
		// 선수들의 현재 순서를 저장하기 위한 리스트를 초기화합니다.
		ArrayList<String> list = new ArrayList<>();

		// 맵과 리스트를 선수들의 초기 순서로 채웁니다.
		for(int i=0; i<players.length; i++) {
			playerToPosition.put(players[i], i);
			list.add(players[i]);
		}

		// 각 호출을 처리합니다.
		for(String calling : callings) {
			// 호출한 선수가 맵에 존재하는지 확인합니다.
			if (playerToPosition.containsKey(calling)) {
				// 호출한 선수의 현재 위치를 가져옵니다.
				int idx = playerToPosition.get(calling);
				// 호출한 선수를 현재 위치에서 제거합니다.
				list.remove(idx);
				// 호출한 선수를 이전 선수 앞에 삽입합니다.
				list.add(idx-1, calling);

				// 맵에서 호출한 선수와 이전 선수의 위치를 업데이트합니다.
				playerToPosition.put(calling, idx-1);
				playerToPosition.put(list.get(idx), idx);
			}
		}

		// 최종 선수 순서를 반환합니다.
		return list.toArray(new String[0]);
	}
}

ArrayList에서는 인덱스를 사용하여 요소에 접근하는 연산이 O(1)의 시간 복잡도를 가짐

728x90

LIST

저작자표시 비영리 동일조건

'알고리즘 > 프로그래머스 JAVA LV.1' 카테고리의 다른 글

[1차] 다트 게임 (1)	2023.05.15
푸드 파이트 대회 (0)	2023.05.15
콜라 문제 (0)	2023.05.13
가장 가까운 같은 글자 (0)	2023.05.13
크기가 작은 부분문자열 (0)	2023.05.13

728x90

SMALL

문제 설명

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.

콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?

단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

1 ≤ b < a ≤ n ≤ 1,000,000
정답은 항상 int 범위를 넘지 않게 주어집니다.

입출력 예

a b n result

2	1	20	19
3	1	20	9

입출력 예 설명

입출력 예 #1

본문에서 설명한 예시입니다.

입출력 예 #2

빈 병 20개 중 18개를 마트에 가져가서, 6병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 8(20 – 18 + 6 = 8)개 입니다.
빈 병 8개 중 6개를 마트에 가져가서, 2병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 4(8 – 6 + 2 = 4)개 입니다.
빈 병 4 개중 3개를 마트에 가져가서, 1병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 2(4 – 3 + 1 = 2)개 입니다.
3번의 교환 동안 상빈이는 9(6 + 2 + 1 = 9)병의 콜라를 받았습니다.

package LV1;
/*
<https://school.programmers.co.kr/learn/courses/30/lessons/132267>
 */
public class H132267 {
	public int solution(int a, int b, int n) {
		int answer = 0;
		while (n >= a) {
			int exchange = n / a;
			int rest = n & a;
			answer += quotient * b;
			n = exchange * b + rest;
		}
		return answer;
	}
}

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

package LV1;
/*
<https://school.programmers.co.kr/learn/courses/30/lessons/132267>
 */
public class H132267 {
	public int solution(int a, int b, int n) {
		int answer = 0;
		while (n >= a) {
			int exchange = n / a * b;
			int rest = n % a;
			answer += exchange;
			n = exchange - b + rest + a;
		}
		return answer;
	}
}

실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

package LV1;
/*
<https://school.programmers.co.kr/learn/courses/30/lessons/132267>
 */
public class H132267 {
	public int solution(int a, int b, int n) {
		int answer = 0;

		while(n >= a) {
			int exchange = (n / a) * b;
			n = (n % a) + exchange;
			answer += exchange;
		}

		return answer;
	}
}

728x90

LIST

저작자표시 비영리 동일조건

'알고리즘 > 프로그래머스 JAVA LV.1' 카테고리의 다른 글

푸드 파이트 대회 (0)	2023.05.15
달리기 경주 (0)	2023.05.15
가장 가까운 같은 글자 (0)	2023.05.13
크기가 작은 부분문자열 (0)	2023.05.13
삼총사 (0)	2023.05.13

728x90

SMALL

문제 설명

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.

예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

제한사항

1 ≤ s의 길이 ≤ 10,000
- s은 영어 소문자로만 이루어져 있습니다.

입출력 예

s result

"banana"	[-1, -1, -1, 2, 2, 2]
"foobar"	[-1, -1, 1, -1, -1, -1]

입출력 예 설명

입출력 예 #1

지문과 같습니다.

입출력 예 #2

설명 생략

package LV1;

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

/*
문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.
 */
public class H142086 {
	public int[] solution(String s) {
		int n = s.length();
		int[] answer = new int[n];
		Arrays.fill(answer, -1);
		Map<Character, Integer> map = new HashMap<>();

		for (int i = 0; i < n; i++) {
			char c = s.charAt(i);
			if (map.containsKey(c)) {
				answer[i] = i - map.get(c);
			}
			map.put(c,i);
		}
		return answer;
	}
}

문자열 **s**를 순회하면서 각 문자가 이전에 나타난 위치를 **map**에 기록

그리고 만약 맵에 현재 문자가 이미 있다면, 결과 리스트의 현재 위치를 현재 위치에서 이전 위치까지의 거리로 업데이트

그렇지 않으면 결과 리스트의 현재 위치는 -1로 유지

728x90

LIST

저작자표시 비영리 동일조건

'알고리즘 > 프로그래머스 JAVA LV.1' 카테고리의 다른 글

달리기 경주 (0)	2023.05.15
콜라 문제 (0)	2023.05.13
크기가 작은 부분문자열 (0)	2023.05.13
삼총사 (0)	2023.05.13
신고 결과 받기 (0)	2023.05.13

Part of your World