프로그래머스 코딩테스트 Lv 1. 대충 만든 자판 문제
1. 문제설명
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.
단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.
2. 제한사항
1 ≤ keymap의 길이 ≤ 100
1 ≤ keymap의 원소의 길이 ≤ 100
keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
keymap의 원소의 길이는 서로 다를 수 있습니다.
keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
1 ≤ targets의 길이 ≤ 100
1 ≤ targets의 원소의 길이 ≤ 100
targets의 원소는 알파벳 대문자로만 이루어져 있습니다.
3. 시간 복잡도 분석
keymap의 길이가 최대 100, 각각의 keymap의 원소의 길이는 최대 100
targets의 길이가 최대 100, 각각의 targets의 길이는 최대 100
즉, 이를 중첩 반복문으로 순회하며 정답을 찾게 되면 반복횟수는
O( (100*100) * (100*100) ) = O(100,000,000) 1억
그렇기때문에, 단순하게 반복하는 것으로 문제를 해결하면 반드시 시간초과가 발생한다.
문제를 생각해보면, keymap에서 A는 여러 번 나올수도 아예 나오지 않을 수도 있다.
A가 여러 번 나올경우에는 A로 도달할 수 있는 가장 최소 값을 찾아야하고, targets에서 A를 필요로 하는데 A가 없으면, 바로 -1을 int[] answer 배열에 해당하는 index에 -1을 넣어주고 바로 다음 반복문을 실행하면 된다.
처음에 모든 keymap을 돌면서 도달할 수 있는 모든 경우의 수 중에서 최소 값을 찾고, 이를 딕셔너리 자료형에 저장한 뒤, targets을 순회하며 딕셔너리에서 값을 하나 씩 꺼내서 answer[i]에 더해주면 될 것이다.
이때 시간복잡도는 최대 O(100*100 + 100*100) = O(20,000) 2만
이 방법으로 코드를 짜면 될 것이다.
4. 실제 코드
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] solution(string[] keymap, string[] targets) {
Dictionary<char,int> key = new Dictionary<char,int>();
int[] answer = new int[targets.Length] ;
foreach(var keymaps in keymap)
{
for(int i=0; i < keymaps.Length; i++)
{
if(key.ContainsKey(keymaps[i]))
{
if(key[keymaps[i]]>i+1)
{
key[keymaps[i]] = i+1;
}
}
else
{
key.Add(keymaps[i],i+1);
}
}
}
int index=0;
foreach(var t in targets)
{
for(int i=0; i<t.Length;i++)
{
if(key.ContainsKey(t[i]))
{
answer[index] += key[t[i]];
}
else
{
answer[index] = -1;
break;
}
}
index++;
}
return answer;
}
}유니티 RigidBody
유니티에서 RigidBody를 사용하는 경우는 언제일까?
-
중력, 힘과 속도를 오브젝트에 적용하고 싶을 때
-
충돌을 처리하고 싶을 때
RigidBody의 속성
BodyType
RigidBody에는 BodyType속성을 변경하여 물리효과를 받지 않게 하면서, RigidBody를 적용할 수 있다. BodyType이Dynamic일 경우 물리효과를 받으며,Kinematic일 경우 물리효과를 받지 않는다.
2.Mass,Drag,Constraint
RigidBody에서 위의 3가지 속성은 Dynamic일 때, 조정가능하며 물리효과에 영향을 준다.
Mass: 오브젝트의 무게
Drag: 오브젝트의 저항값 (공기저항)
Constraint: 오브젝트의 움직임(회전)제한
Awake(), Start(), Update(), FixedUpdate(), LateUpdate()
위의 내용들은 이전의 유니티 생명주기 TIL에서 이미 작성한 내용이지만, 이번에는 해당 메서드들이 어떻게 사용되는 지를 알았기 때문에 TIL에 작성한다. 해당 링크는 유니티 생명주기TIL
- Awake()
Awake()는 게임이 실행되면 가장 먼저 호출되는 메서드이다. 따라서, 객체 자체적인 초기화를 할 때 이 안에서 이루어진다. 초기 위치값, 내부 변수 초기화 등. - Start()
Start()는 외부 메서드나 클래스를 참조하여 초기화하는 부분이 필요할 때 이 메서드 안에서 한다. 이유는 Awake()에서 이를 시도할 경우 객체들의 Awake()호출 순서에 따라 버그가 발생할 수도 있기 때문이다. Awake()다음으로 Start()메서드가 호출된다는 것은 자명하므로, 다른 객체들을 참조하는 초기화는 Start()에서 한다. - Update()
UPdate()는 입력이나 게임로직을 호출할 때, 사용하는 메서드들을 호출하는 용도로 쓰인다. Update()의 경우 매 프레임마다 처음으로 호출되기 때문에, 게임이 움직이는 프레임단위로 게임로직과 입력값에 따른 메서드들을 호출하는데 적합하다. - FixedUpdate()
현실시간을 기반으로 단위시간마다 호출되는 메서드이다. 물리연산의 경우 프레임단위로 이루어질때, 성능이 좋은 컴퓨터와 안좋은 컴퓨터의 연산결과가 바뀔 수 있으므로, 물리연산을 수행할때는 FixedUpdate()를 사용한다. - LateUpdate()
Update()호출된 뒤, 다음 프레임이 되기 전 반드시 호출되는 함수다. Update()뒤에 호출되는 것이 자명하기때문에 플레이어의 입력을 받은 후의 카메라 이동등의 후처리메서드를 호출하기에 적합하다.
