dictionary 자료형을 2개 사용해서 a -> b 로 바뀐적이 있는지 없다면 b로 바뀔 수 있는지를 판단하여 풀이했다.
OO 기업의 코딩테스트를 봤는데 python 언어 제출이 불가능했다.
그래서 java로 풀었는데 평소에 java로 푸는 연습을 안 해놔서 그런지 파이썬이었으면 충분히 풀 수 있는 문제 였음에도 풀지 못했다.
이제부터 python으로 푼 코드를 java로 옮겨보면서 연습하려고 한다.
제출 코드
파이썬
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
arr = [input().rstrip() for _ in range(N)]
def isPossible(w1, w2):
dict = defaultdict(str)
used = defaultdict(int)
for i in range(len(w1)):
if dict[w2[i]] == "": # 특정단어 a가 변경 된적이 없다면
if used[w1[i]] == 1 : # 목표 단어 b로 변경된 단어가 있어서 바뀔 수 없는 경우
return False # 같은 단어를 만들 수 없음
else:
dict[w2[i]] = w1[i] # 앞으로 a 는 b 로 바뀌고
used[w1[i]] = 1 # 다른 단어는 b 로는 이제 바뀔 수 없음
else: # 기존에 바뀐 이력이 있는 단어
if dict[w2[i]] != w1[i]: # b 가 변경된 단어가 a 가 아니면
return False # 같은 단어를 만들 수 없음
return True
ans = 0
for i in range(N-1):
w1 = arr[i]
for j in range(i+1, N):
w2 = arr[j]
if isPossible(w1, w2):
ans += 1
print(ans)자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
final static Main solve = new Main();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] wordList = new String[N];
for (int i = 0; i < N; i++) {
String word = br.readLine();
wordList[i] = word;
}
int ans = 0;
for (int i = 0; i < N-1; i++) {
String word_A = wordList[i];
for (int j = i+1; j < N; j++) {
String word_B = wordList[j];
if (solve.isPossible(word_A, word_B) == true) {
ans ++;
}
}
}
System.out.println(ans);
}
public boolean isPossible(String w1, String w2) {
HashMap dict = new HashMap<Character, Character>();
HashMap used = new HashMap<Character, Integer>();
for (int i = 0; i < w1.length(); i++) {
char wA = w1.charAt(i);
char wB = w2.charAt(i);
if (dict.containsKey(wB) == false) {
if (used.containsKey(wA) == true) {
return false;
} else {
dict.put(wB, wA);
used.put(wA, 1);
}
} else {
if (dict.get(wB).equals(wA) == false) {
return false;
}
}
}
return true;
}
}
접근방법
dict 와 used
둘 다 defaultdict 로 만들었고 dict key를 value로 바꿔야 함을 의미하고 used는 key 값으로 바뀔 수 있는지 즉 dict의 value 값에 특정 단어가 있는지를 확인한다.
예제를 통해서 dict 와 used 를 설명하고자 한다.
ex_1) aab 와 acb
먼저 직관적으로 보면 두개의 단어는 유사 관계가 아니다.
이해를 쉽게 하기위해 acb 를 ACB 대문자로 표시만해서 확인할 것이다.
이제 ACB 를 aab 로 바꿀 수 있는지 확인해 볼것이다.
첫번째 단어 a 와 A
두개의 단어는 같으므로 유지해야 한다.
그전에 이전에 A가 변경된적 있는지 확인한다. ( dict[w2[i]] == "" )
없다면 유지하면 되는데 이는 A를 a로 바꾸는 것과 같다. dict에 A : a 가 저장된다.
또한 이제 A가 아니면 a로 바뀔 수 없다. used에 a:1 이 저장된다.
두번째 단어 a 와 C
C 가 변경된 적이 있는지 확인했다.
없으므로 C를 a 로 바꾼다.
그런데 a는 이미 변경된 적이 있다. ( used[a] = 1 )
그러므로 C 는 a 로 바꿀 수 없고 aab 와 acb 는 같은 단어가 될 수 없다.
